基于網(wǎng)格的遺傳算法及其在公交運行計劃編制中的應(yīng)用研究

1、基于網(wǎng)格的遺傳算法及其在公交運行計劃編制中的應(yīng)用研究陳琛 洪流 陳學廣 郝語嘉（華中科技大學 系統(tǒng)工程研究所 武漢 430074）摘 要： 本文利用基于網(wǎng)格的遺傳算法解決城市公共交通運營中的運行計劃編制問題。首先應(yīng)用有序樣本聚類算法對城市公交歷史客流量樣本數(shù)據(jù)進行數(shù)據(jù)挖掘，然后在綜合考慮乘客待車成本和公交公司運營虧損等因素的前提下構(gòu)造遺傳算法的適應(yīng)度函數(shù)、編碼方式和約束條件，最后在網(wǎng)格平臺上初始化算法種群，并分配不同的子種群到網(wǎng)格的各個集群、節(jié)點上并行的進行選擇、交叉、變異及計算染色體的適應(yīng)度等進化操作，同時以一定的規(guī)律在集群和集群、節(jié)點和節(jié)點之間交換優(yōu)秀染色體，從而能快速得出滿意的運行計劃時

2、刻表；通過仿真試驗，證明了該方法的有效性和實時性。關(guān)鍵詞： 公共交通；有序樣本聚類；遺傳算法；網(wǎng)格；運行計劃 中圖分類號：TP Research on grid-based genetic algorithm and its application in public transport operation plan schedulingChen Chen Liu Hong XueGuang Chen YuJia Hao（Institute of System Engineering, Huazhong University of Science and Technology, Wuhan,

3、430074, P. R. China）Abstract: To solve the problem of public transport operation plan scheduling, this paper proposes a grid-based genetic algorithm. Firstly, we do data mining in the historical passenger flow samples of urban transportation by using sequential cluster algorithm. Secondly, we constr

4、uct the fitness function, coding method and constraint condition of genetic algorithm under considering the cost of passenger-waiting and operating loss of public transport company. Finally, we initialize the populations on the Grid platform, and then distribute the subpopulations to different Grid

5、clusters and nodes for selection, crossover, and mutation, calculate the fitness of chromosome in diverse directions simultaneously and exchange the excellent chromosome between clusters or nodes in order to get the satisfactory operation plan quickly. Experiments on real data demonstrate the benefi

6、ts of the method.Key words: public transport；sequential cluster；genetic algorithm；grid；operation plan引 言收稿日期： 最終修改稿收到日期： 本課題得到國家自然科學基金（60773188）和武漢市科技計劃（200710321090-2）資助陳琛，男，1984年生，湖南人，博士生。主要研究方向：決策支持系統(tǒng)、信息系統(tǒng)工程、網(wǎng)格計算。E-mail：datocc37洪流，男，1979年生，湖北人，博士,講師。主要研究方向：決策支持系統(tǒng)、信息系統(tǒng)工程、網(wǎng)格計算等。E-mail：newtorrent陳學廣

7、,男，1947年生，湖北人，教授，博士生導師。主要研究方向：決策支持系統(tǒng)、信息系統(tǒng)工程、網(wǎng)格計算等。E-mail：xgchen9郝語嘉，男，1985年生，湖北人，碩士研究生。主要研究方向：決策支持系統(tǒng)、網(wǎng)格計算。E-mail：yjhao2007 遺傳算法是一類借鑒生物界的進化規(guī)律(適者生存，優(yōu)勝劣汰的遺傳機制)演化而來的隨機化搜索方法。實踐證明，運行計劃編制優(yōu)化模型是一個復雜的多目標規(guī)劃問題，它必須兼顧乘客和公交公司雙方的利益，在客流量規(guī)律、線路運行條件、公交公司運輸能力和社會經(jīng)濟效益等約束條件下，優(yōu)化公交車輛在各個時段的發(fā)車時刻，才能使得整個城市公交線路有規(guī)律有節(jié)奏的運行，但是隨著公交網(wǎng)絡(luò)規(guī)

8、模的擴大，優(yōu)化問題的搜索空間急劇擴張，利用常規(guī)方法尋找精確解已經(jīng)是一件很難或者不可能完成的任務(wù)。因此，通常人們把精力放在尋求運行計劃滿意解的上面，而遺傳算法則是尋求這種滿意解的最佳工具。目前國內(nèi)外許多學者都致力于這方面的研究。Chales J.Malmborg等1將遺傳算法引入車輛調(diào)度系統(tǒng)中； Zhang Feizhou等2提出基于混合遺傳算法的公交智能排班方法； J. Herrera等3提出了面向網(wǎng)格的遺傳算法；2007年，D. Lim等4 又提出了基于網(wǎng)格計算的多層并行遺傳算法。在國內(nèi)，時敬梁5，賈以霞等6對公交調(diào)度的遺傳算法做了改進。孫傳姣等7用遺傳算法研究解決快速公交中的調(diào)度優(yōu)化問題。

9、上述工作中，在網(wǎng)格平臺下使用遺傳算法的研究剛剛起步，而在使用傳統(tǒng)遺傳算法解決運行計劃編制問題時，要么模型過于簡單，使結(jié)果很難滿足公交公司對運行計劃的有效性要求；要么模型非常復雜，求解過程緩慢，不能滿足實時性的要求。綜合考慮以上因素，本文提出了利用基于網(wǎng)格的遺傳算法來求解運行計劃編制的新方法，其中改進的遺傳算法保證了運行計劃編制的有效性，而網(wǎng)格強大的計算平臺則保證了運行計劃編制的實時性要求。本文第二節(jié)介紹利用基于網(wǎng)格的遺傳算法解決城市公共交通運營中的運行計劃編制問題的總體思路及流程框圖；第三節(jié)闡述如何建立基于網(wǎng)格和遺傳算法的運行計劃編制模型；第四節(jié)用實驗對比驗證所提模型和方法的有效性與實時性；第

10、五節(jié)總結(jié)全文工作并展望未來研究。新方法的基本思路運用遺傳算法首選需要解決遺傳染色體的編碼問題。發(fā)車頻率的制定是公交系統(tǒng)日常運營工作的核心，它決定了運行時刻表、車輛調(diào)度以及分派司機等其它的日常調(diào)度工作。傳統(tǒng)的發(fā)車頻率確定的最為重要的依據(jù)是線路客流的每日時段分布曲線，然后對客流量相似且相鄰的時段配置相同的運力，即在這些時段內(nèi)發(fā)車間隔9固定，這里，我們對這些發(fā)車間隔進行可變長度的二進制編碼來作為遺傳的染色體，其中使用二進制符號0和1表示發(fā)車間隔的優(yōu)點在于編碼、解碼操作簡單，選擇、交叉、變異等操作便于實現(xiàn)。由于公交線路客流狀況具有一定周期性和重復性，因此我們首先對城市公交的歷史客流量樣本數(shù)據(jù)進行數(shù)據(jù)挖

11、掘，得到與算法相關(guān)的歷史樣本數(shù)據(jù)，然后使用有序聚類fisher9算法優(yōu)化公交峰值曲線的方法10合并歷史樣本數(shù)據(jù)中客流量相似且相鄰的時段，從而得到若干個時段區(qū)間。最后采用這些時段區(qū)間的最大發(fā)車間隔的二進制編碼長度作為這些時段區(qū)間對應(yīng)染色體段的長度和這些時段中的最小發(fā)車間隔和最大發(fā)車間隔作為對應(yīng)染色體段的約束條件。運行計劃的好壞在很大程度上取決于是否能夠兼顧乘客和公交公司雙方的利益：對于乘客來說待車時間越短越好，而對于公交公司來說運營虧損越低越好。這里我們以乘客待車成本和公交公司運營虧損的加權(quán)最小值作為遺傳算法的適應(yīng)度函數(shù)來評價染色體的優(yōu)異性。采用傳統(tǒng)的串行遺傳算法在計算上述適應(yīng)度函數(shù)時非常耗時，

12、再加上需要不斷產(chǎn)生新一代個體，造成運行計劃的編制過程難以滿足實時性的要求，因此提高整個算法的運行速度顯得尤為重要。若對計算機硬件進行升級，則意味著投入成本增加，而網(wǎng)格計算平臺能有效利用網(wǎng)絡(luò)上閑置的計算資源（Intranet內(nèi)的計算資源），使公交公司能夠在較少的投入下獲得超級計算能力,這樣使用基于網(wǎng)格的遺傳算法將能很好地解決計劃編制的實時性問題。首先網(wǎng)格服務(wù)器利用先前確定的編碼方式將相關(guān)的歷史樣本數(shù)據(jù)編碼，形成初始種群；然后將初始種群劃分成若干個子種群并分配到各個網(wǎng)格集群上，網(wǎng)格集群再根據(jù)其網(wǎng)格節(jié)點的處理能力將子種群分配到各個節(jié)點上，此時由節(jié)點的每個處理器在約束條件下獨立對染色體進行選擇、交叉、

13、變異操作，并計算操作后的染色體適應(yīng)度；每等染色體進化一定代數(shù)后，網(wǎng)格節(jié)點與相鄰節(jié)點交換適應(yīng)度高的染色體，并淘汰適應(yīng)度低的染色體，同時將這些高的染色體形成一個新的種群提交所在集群，這個種群將會被分配到每個集群中去進行進化。等到集群內(nèi)所有的子種群進化完成后選取適應(yīng)度高的滿意染色體提交到網(wǎng)格服務(wù)器，服務(wù)器將比較所有集群提交的染色體適應(yīng)度，查看適應(yīng)度最高的染色體是否滿足終止條件，如果滿足，則此染色體則是最終染色體；如果不滿足，則重復進行上面的操作直到得到滿足終止條件的最終染色體。最后將最終染色體轉(zhuǎn)換成發(fā)車間隔，并根據(jù)始末班發(fā)車時間，得到發(fā)車時刻表，即運行計劃。整個的流程框圖如下圖所示：圖：基于網(wǎng)格的遺

14、傳算法解決運行計劃編制問題的總體流程圖運行計劃編制模型基于網(wǎng)格和遺傳算法的運行計劃編制模型構(gòu)建及其求解方法如下。.模型假設(shè)本文主要是根據(jù)獲取適應(yīng)度最大的染色體來優(yōu)化發(fā)車間隔，為了更好的進行研究工作，我們針對公交系統(tǒng)的實際情況做出如下假設(shè)：1) 只考慮單條線路，線路和線路之間不相互影響。2) 在制定計劃之前原型系統(tǒng)有相關(guān)歷史樣本數(shù)據(jù)。3) 公汽總是嚴格按照運行計劃排定的發(fā)車時刻發(fā)車。4) 各時段乘客到站符合均勻分布。5) 每次公汽到站，不會有乘客遺落。6) 公汽為單一類型，票價，可載客量以及每公里運營成本都一致。.模型輸入 為能更好地貼近公交運行實際情況，允許模型有如下的初始輸入：1) 為線路。

15、2) 為限制最大發(fā)車間隔；為限制最小發(fā)車間隔。3) 為限制最大發(fā)車總數(shù)。4) 為公汽的可載客量；為公汽的票價。5) 為時段分區(qū)精度，單位分鐘。6) 為首班發(fā)車時間；為末班發(fā)車時間。7) 為公交公司期望車輛平均滿載率。8) 為乘客每分鐘等待的時間成本。9) 為公交車的每公里平均運行成本。10) 為目標函數(shù)中公交公司運營虧損的加權(quán)系數(shù)。11) 為目標函數(shù)中乘客待車成本的加權(quán)系數(shù)。.模型變量 以下是模型中出現(xiàn)的相關(guān)變量定義：1) 為時段區(qū)間集。其中k表示第k時段區(qū)間，K表示時段區(qū)間總數(shù)。2) 為發(fā)車車次集。表示第k時段區(qū)間發(fā)的第i次車，表示第k時段區(qū)間發(fā)的第m次車，同時也表示第k時段區(qū)間的總的發(fā)車車

16、次。3) 為車站集。表示第個車站，表示第個車站，同時也表示線路的車站總數(shù)，可從系統(tǒng)里獲得。4) 為查找匹配輸入的歷史樣本數(shù)據(jù)。其中表示第條數(shù)據(jù)，表示第n條數(shù)據(jù)分鐘內(nèi)的客流量；為的配車數(shù)；為的最大發(fā)車間隔；為的最小發(fā)車間隔；為在第段時段分區(qū)內(nèi)最大發(fā)車間隔；為在第段時段分區(qū)內(nèi)的最小發(fā)車間隔；為所有歷史樣本在第段時段分區(qū)內(nèi)最大發(fā)車間隔；為所有歷史樣本在第段時段分區(qū)內(nèi)的最小發(fā)車間隔；為的首班發(fā)車時間；為的末班發(fā)車時間。為第條的車子滿載率。為第條在k時段j站點的乘客平均到達率。5) 為第j個站臺和第j+1個站臺的距離。6) 為第k時段區(qū)間的發(fā)車間隔。7) 為第k時段區(qū)間的發(fā)車數(shù)量。8) 為第k時段區(qū)間的

17、染色體編碼位數(shù)。9) 為第k時段區(qū)間的長度。10) 為第k時段區(qū)間的第一車次發(fā)車時刻，也是各時段區(qū)間的開始時刻，即為首班車發(fā)車時刻。11) 為第k時段第j站的乘客平均到達率。.模型構(gòu)建1) 從樣本數(shù)據(jù)中查找滿足以下約束的L線路歷史樣本，即： (1)2) 分別累加分鐘內(nèi)歷史樣本的客流量。即公式： (2)3) 計算類直徑有序聚類法用“類直徑”來表示段內(nèi)的差異程度,段內(nèi)差異愈小,直徑就愈小。類的直徑記為,一般多采用“離差平方和”作為直徑,即： (3)其中4) 定義損失函數(shù)有序聚類法用“損失函數(shù)”來表示分割的好壞,損失函數(shù)定義為各段直徑之和，即： (4)損失函數(shù)愈小,說明段內(nèi)的差異愈小,同時也說明段間

18、的差異愈大。當固定時,使值最小的那一種分割,就是最優(yōu)分割，即： (5)5) 確定最優(yōu)分段數(shù)，計算比值，當值比較大時,就說明分成段顯然比分為段好。而且值接近于1時即可不必再往下分。6) 劃分時段區(qū)間根據(jù)和，合并客流量類似相鄰時段，可確定時段分區(qū)7) 獲得各個時段分區(qū)的發(fā)車間隔約束取得所有歷史樣本數(shù)據(jù)的在各個時段分區(qū)的最大和最小發(fā)車間隔作為時段分區(qū)的發(fā)車間隔約束，即： (6)8) 獲得各個時段區(qū)間的到達各個站點的乘客平均到達率，即: (7)9) 確定染色體編碼長度將發(fā)車間隔的二進制編碼作為染色體編碼，編碼位數(shù)由K時段區(qū)間的最大發(fā)車間隔決定，即： (8)其中表示取整10) 確定適應(yīng)度函數(shù)第k個時段區(qū)

19、間的派車數(shù)由該時段區(qū)間的時間長度和發(fā)車間隔決定，即： (9)對于乘客來說，就是平均等待時間最少，為了方便計算，我們在這里將他折合成費用，即乘客的平均等待成本最低，即： (10)對于公交公司來說，就是運營收入最高，即客票收入減去運營成本最高，但考慮到目前中國公交公司一般都是虧本運營，則考慮運營虧損最低，即： (11)適應(yīng)度函數(shù)則是求兩者的加權(quán)值的最小值，即： (12)其中(12) 確定約束條件每個時段區(qū)間必須滿足該區(qū)間發(fā)車間隔約束，即： (13)發(fā)車總數(shù)應(yīng)不大于限制最大發(fā)車數(shù)，即： (14)車子的滿載率應(yīng)不小于期望滿載率，即： (15)3.5 模型求解 網(wǎng)格處理首先網(wǎng)格服務(wù)器根據(jù)按照染色體編碼方

20、式對進行編碼形成初始種群，再將初始種群劃分成若干個子種群并分配到各個網(wǎng)格集群上，接下來網(wǎng)格集群根據(jù)其網(wǎng)格節(jié)點的處理能力將子種群分配到各個節(jié)點上，此時由節(jié)點的處理器在模型的約束條件下獨立計算由節(jié)點分配到它的染色體的適應(yīng)度，并進行如下操作：1）選擇：此處，采用按比例的適應(yīng)度分配（proportional fitness assignment）方法，根據(jù)各個個體適應(yīng)度的概率決定其子孫遺留的可能性。若某個個體i的適應(yīng)度為,則它被選取的概率為 （16）2）重組：選擇單點交叉（One-point Crossover）作為遺傳算法的交叉運算，其基本過程如下：首先將群體中的 個體以隨機方式組成 對配對個體組，

21、然后對每個個體組以概率進行交叉運算，先在個體編碼串中隨機設(shè)置一個交叉點，然后在該點相互交換兩個配對個體的部分染色體。交叉點的選擇必須保證新的個體符合約束條件。如果隨機選取的交叉點不能使新的個體滿足約束條件，即新產(chǎn)生的個體基因可能不完全是按升序排列的。則將交叉點向某個方向移動，直到可以產(chǎn)生符合條件的新個體為止。為加快收斂速度，采用局部選擇策略，將交叉產(chǎn)生的新個體和原個體進行比較，選擇適應(yīng)度最大的兩個作為交叉運算的結(jié)果。3）變異：變異運算采用均勻變異(Uniform Mutation)操作。依次指定個體編碼串當中的個體基因座為變異點，對每個變異點以很小的變異概率從對應(yīng)基因的取值范圍內(nèi)取一個均勻分布

22、的隨機數(shù)來代替原來的基因。從可見決策變量的約束條件已經(jīng)包含在遺傳算子的設(shè)計過程中，經(jīng)過選擇、交叉、變異產(chǎn)生的新一代群體中的所有個體的表現(xiàn)型都是滿足約束條件的。當染色體進化到十的倍數(shù)代后，網(wǎng)格節(jié)點與相鄰節(jié)點交換適應(yīng)度高的染色體，并淘汰適應(yīng)度低的染色體，同時將這些高的染色體形成一個新的種群提交所在集群，這個種群將會被分配到每個集群中去進行進化。等到集群內(nèi)所有的子種群進化完成后選取適應(yīng)度高的滿意染色體提交到網(wǎng)格服務(wù)器，服務(wù)器將比較所有集群提交的染色體適應(yīng)度，查看適應(yīng)度最高的染色體是否滿足終止條件，如果滿足，則此染色體則是最終染色體，如果不滿足，則重復進行上面的操作直到得到滿足終止條件的最終染色體。

23、染色體解碼根據(jù)將最終染色體分為若干個區(qū)間，并利用以下二進制轉(zhuǎn)換成轉(zhuǎn)化成十進制的計算公式可得到各區(qū)間的發(fā)車間隔，即：= = (17)再根據(jù)始末班時間和計算得到發(fā)車時刻表，即： (18) 4 仿真試驗為了驗證上述模型和算法的有效性和可靠性，我們在基于網(wǎng)格的城市公交信息管理與決策支持系統(tǒng)上實現(xiàn)了該模型和算法，并進行了仿真試驗。根據(jù)我們掌握的某市公交公司的歷史樣本數(shù)據(jù)及其運營實際特點，給出了如下模型輸入條件：為536線路；為20分鐘；為3分鐘；為100次；為80人；為1.2元；為60分鐘；為6：00；為23：00；為75%；為2.3133元/分鐘；為3.2元/公里。根據(jù)輸入條件，可得用于有序聚類的客流

24、數(shù)據(jù)，如表1所示： 時間段客流人數(shù)時間段客流人數(shù)時間段客流人數(shù)6:007:0030617:018:0033128:019:0045599:0110:00422610:0111:00443211:0112:00415712:0113:00399113:0114:00396314:0115:00437315:0116:00345616:0117:00369517:0118:00510818:0119:00499019:0120:00471220:0121:00312421:0122:00276522:0123:002542表1 各時間段的累加客流量對上述客流量數(shù)據(jù)進行有序聚類，可得時段區(qū)間及其發(fā)車

25、間隔約束，如表2所示時段區(qū)間最大間隔最小間隔時段區(qū)間最大間隔最小間隔6:018:0012分鐘7分鐘8:0115:0011分鐘5分鐘15:0117:009分鐘4分鐘17:0120:008分鐘3分鐘20:0123:0013分鐘9分鐘表2 時段區(qū)間及其發(fā)車間隔約束接下來在網(wǎng)格上計算，最終可得如下時段區(qū)間發(fā)車間隔，并與該公交公司傳統(tǒng)制定發(fā)車間隔進行對比，節(jié)省了一定的折合成本，證明了該方法的有效性，如表3所示：時段區(qū)間使用前使用后節(jié)省平均發(fā)車間隔折合成本發(fā)車間隔折合成本6:018:0011.2分鐘86336.129分鐘71321.8717.39%8:0115:008.6分鐘239481.346分鐘182

26、455.1023.81%15:0117:007.0分鐘99034.678分鐘89141.309.99%17:0120:005.3分鐘118934.517分鐘104729.3211.94%20:0123:0012.5分鐘99211.7010分鐘77431.9521.95%表3 最終發(fā)車間隔及成本對比最終可得到發(fā)車時刻表。我們對同樣的模型分別在單臺計算機和網(wǎng)格下計算，模型求解的時間分別為173.11秒和19.24秒，后者比前者節(jié)約了大量時間，證明了該方法的實時性。5 結(jié) 語本文探討了基于網(wǎng)格的遺傳算法及其在城市公交運行計劃編制中的應(yīng)用，其中我們建立了綜合考慮乘客待車成本與公交公司運營成本之間的多目

27、標規(guī)劃模型以及設(shè)計了基于網(wǎng)格的遺傳算法計算模型。通過仿真試驗，對模型和算法的有效性進行了驗證和分析，結(jié)果表明該模型和算法能較好地滿足公交公司運行計劃編制的有效性與實時性要求，可對改進公交運營質(zhì)量提供較好的決策支持。但是在實際使用過程中，還存在對乘客待車成本與公交公司運行成本間的權(quán)重因子的確定、如何克服遺傳算法的算子選擇單一以及如何選擇合適遺傳代數(shù)來進行網(wǎng)格節(jié)點之間優(yōu)秀染色體交換等問題，尚需做進一步的研究。 參 考 文 獻：1 Chales J.Malmborg. A genetic algorithm for service level based vehicle scheduling. Eu

28、ropean Journal of Operational Research,1996,93:121-1342 Zhang Feizhou,Yang Dongkai,Chen Xiuwan. Intelligent scheduling of public traffic vehicles based on hybrid genetic algorithm. Intelligent Transportation Systems,2003.Proceedings 2003 IEEE Volume 2:1674-16783 J. Herrera, E. Huedo, R. Montero, and

29、 I. Llorente. A grid-oriented genetic algorithm. In Advances in Grid Computing- EGC, 2005: 3153224 D. Lim, Y. Ong, Y. Jin, B. Sendhoff, and B. Lee. Efficient hierarchical parallel genetic algorithms using grid computing. Future Gener. Comput. Syst., 2007,23(4):6586705 Shi Jing-Liang, Tian shi-feng.I

30、ntelligent dispatch for public traffic vehicles based on genetic algorithm. Pattern Recognition and Artificial Intelligence.2007(5): 1679-1681(5): 1679-1681)6 Jia Yi-Xia.The application of synthetically improved genetic algorithm in public traffic dispatch system.Dalian university of technology Mast

31、er's Thesis.2007()7 Sun Chuan-Jiao, Zhou Wei, Wang Yuan. Scheduling combination and headway optimization of Bus rapid transit. Journal of transportation systems engineering and information technology,2008(10): 5-11(孫傳姣,周偉.快速公交車輛調(diào)度組合及發(fā)車間隔優(yōu)化研究.交通運輸系統(tǒng)工程與信息,2008(10): 5-11)8 Sun Fu-Ling.The research

32、of methods for determining Bus headway. Journal of Xian highway university,1997.17(2):44-48()9 Massimo G,Annamaria N.The Kalman Fisher Approach For Time-Varying Estimation.Systems Analysis Modeling Simulation.2003,43(8):1033-104210 Yang Xin-Miao, Wang Wei.A new method for transit peak value curve op

33、timization. Journal of southeast university(natural science edition).2001,31(3)：40-43(楊新苗,王煒.公交調(diào)度峰值曲線的優(yōu)化方法.東南大學學報(自然科學版)，2001,31(3)：40-43)CHEN Chen, born in 1984, Ph.D. His research interests include decision support system, information system and grid computing.HONG Liu, born in 1979, Ph.D, lecturer. His research interests include decision support system, information system and grid com