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

2、刻表；通過仿真試驗，證明了該方法的有效性和實時性。關鍵詞： 公共交通；有序樣本聚類；遺傳算法；網格；運行計劃 中圖分類號：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年生，湖南人，博士生。主要研究方向：決策支持系統、信息系統工程、網格計算。E-mail：datocc37洪流，男，1979年生，湖北人，博士,講師。主要研究方向：決策支持系統、信息系統工程、網格計算等。E-mail：newtorrent陳學廣

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

24、數據，如表1所示： 時間段客流人數時間段客流人數時間段客流人數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 各時間段的累加客流量對上述客流量數據進行有序聚類，可得時段區間及其發車

25、間隔約束，如表2所示時段區間最大間隔最小間隔時段區間最大間隔最小間隔6:018:0012分鐘7分鐘8:0115:0011分鐘5分鐘15:0117:009分鐘4分鐘17:0120:008分鐘3分鐘20:0123:0013分鐘9分鐘表2 時段區間及其發車間隔約束接下來在網格上計算，最終可得如下時段區間發車間隔，并與該公交公司傳統制定發車間隔進行對比，節省了一定的折合成本，證明了該方法的有效性，如表3所示：時段區間使用前使用后節省平均發車間隔折合成本發車間隔折合成本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 最終發車間隔及成本對比最終可得到發車時刻表。我們對同樣的模型分別在單臺計算機和網格下計算，模型求解的時間分別為173.11秒和19.24秒，后者比前者節約了大量時間，證明了該方法的實時性。5 結 語本文探討了基于網格的遺傳算法及其在城市公交運行計劃編制中的應用，其中我們建立了綜合考慮乘客待車成本與公交公司運營成本之間的多目

27、標規劃模型以及設計了基于網格的遺傳算法計算模型。通過仿真試驗，對模型和算法的有效性進行了驗證和分析，結果表明該模型和算法能較好地滿足公交公司運行計劃編制的有效性與實時性要求，可對改進公交運營質量提供較好的決策支持。但是在實際使用過程中，還存在對乘客待車成本與公交公司運行成本間的權重因子的確定、如何克服遺傳算法的算子選擇單一以及如何選擇合適遺傳代數來進行網格節點之間優秀染色體交換等問題，尚需做進一步的研究。 參 考 文 獻：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(孫傳姣,周偉.快速公交車輛調度組合及發車間隔優化研究.交通運輸系統工程與信息,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(楊新苗,王煒.公交調度峰值曲線的優化方法.東南大學學報(自然科學版)，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