基于微粒群算法的城市公交線網(wǎng)模型研究

摘要：微粒群算法是求解組合優(yōu)化問題的一種新的群體智能進化算法，從城市公交乘客選擇出行路徑的決策因素出發(fā)，以微粒群算法進化機理為核心，結合微粒群進化算法中的局部搜索與全局搜索同時進行的優(yōu)點和運籌學旅行商組合優(yōu)化理論，系統(tǒng)地建立了規(guī)劃城市智能交通公交線網(wǎng)最短路徑的數(shù)學模型進化算法，并通過MATLAB 7.0進行了實例仿真，得到了城市公交線網(wǎng)出行選擇模型中總運輸里程權重最短的優(yōu)化目標。仿真結果也表明，該進化算法模型是解決城市公交線網(wǎng)規(guī)劃的有效方法。

關鍵詞：微粒群算法； 公交線網(wǎng)； 組合優(yōu)化； 最短路徑； 仿真

中圖法分類號：TP14；TP301文獻標識碼：A

文章編號：1001－3695(2007)01－0131－02

城市公交線網(wǎng)的最短路徑問題是運籌學和組合優(yōu)化領域的前沿與熱點問題，在交通運輸科學領域的研究和應用受到越來越多的重視，特別是在規(guī)劃與實施現(xiàn)代大城市智能交通的大環(huán)境下，更需要重點研究公交線網(wǎng)規(guī)劃的路徑問題。此前研究公交線網(wǎng)最短路徑問題多以Dijkstra算法為核心，但該算法在求解過程中將對整個路徑作大量的優(yōu)化計算，從而大大影響了優(yōu)化的速度和效率，當公交線網(wǎng)規(guī)模較大時，更難以快速搜索到最佳路徑。本文在分析微粒群進化算法原理的基礎上，結合旅行商組合優(yōu)化問題和微粒群進化算法的局部搜索與全局搜索可同時進行的優(yōu)點，研究并提出了可快速、高效搜索公交線網(wǎng)最短路徑的基于微粒群進化算法的城市智能交通公交線網(wǎng)最短路徑數(shù)學模型及其進化算法。

城市公交乘客在出行路徑?jīng)Q策中主要受三個因素的影響，即出行距離、換乘次數(shù)和出行耗時[1]。由于公交出行耗時受城市道路的交通流量、交通管制、道路質量和發(fā)車間隔等諸多因素的影響，難以精確量度，故本文選取出行距離最短作為首要考慮的因素，兼顧換乘次數(shù)較少作為優(yōu)化目標。

1微粒群進化算法原理

微粒群(Particle Swarm Optimization， PSO)算法是1995年由美國社會心理學家James Kennedy和電氣工程師Russell Eberhart共同提出的。它是基于鳥類群體在空中飛行路徑的生物群體模型的一種新的群體智能進化算法。根據(jù)微粒對環(huán)境的適應度將微粒群體中的個體移動到好的區(qū)域，PSO算法不像其他進化算法那樣對個體使用進化算子，而是將每個個體看作D維搜索空間中的一個沒有體積的微粒(點)，在搜索空間中以一定的速度飛行。這個速度根據(jù)它本身的飛行經(jīng)驗以及同伴的飛行經(jīng)驗進行動態(tài)調(diào)整[2~4]。

與其他進化算法對比可以看出，PSO在進化過程中同時保留和利用位置與速度信息，并將微粒的位置與速度模型化，得到一組顯式的進化方程，而其他進化算法僅僅保留和利用了位置信息；同時，PSO不但具有遺傳算法的全局搜索能力，還由于其微粒沒有個體的雜交、變異等運算操作，其參數(shù)的調(diào)整就變得簡單方便，很適合計算機編程，而通過各項參數(shù)的調(diào)整使PSO又具有了很強的局部搜索能力。

2城市公交線網(wǎng)最短路徑問題的數(shù)學模型

4實例仿真分析

若某城市公交線網(wǎng)上共有十個站點，編號分別為0，1，2，…，9，其任意兩個站點間的距離權重如表1所示。站點0為起點站，站點9為終點站，試合理安排一個由起點站到終點站的公交線網(wǎng)的路徑距離最短的編排序號并求其最短路徑的總運輸里程權重。

表1某城市公交線網(wǎng)十個站點相互間的距離權重表

在MATLAB 7.0的軟件編程環(huán)境下，對基于PSO進化算法的城市智能交通公交線網(wǎng)規(guī)劃最短路徑的

數(shù)學模型進行仿真時，取一個10維的向量構成每一個微粒子的位置Xi，即某一種公交線網(wǎng)路徑的初始序號編排方案；同時，微粒子種群數(shù)取為100。另外，為了便于數(shù)學模型進化算法中對每個微粒子的整數(shù)序進行規(guī)范，取其進化參數(shù)ω=1，c1=c2=2，r1=r2=0．5。

此時，城市公交線網(wǎng)出行路徑總的運輸里程權重S僅為22。

另外，最優(yōu)粒子的權重適應值隨微粒群種群進化代數(shù)的變化情況如圖1所示。整個仿真過程只需要幾十秒的時間，其仿真結果就可以快速、高效地逼近最優(yōu)解。

圖1PSO進化算法最優(yōu)解的進化情況

5結束語

實例仿真的結果證明：把PSO進化原理引入城市智能交通公交線網(wǎng)最短路徑規(guī)劃模型中，得到的最短路徑質量較高，搜索最短路徑的速度快、效率高，且該進化算法的原理新穎、編程方便，是一種有效、實用、可行的優(yōu)化方法。

參考文獻：

［1］李文勇，王煒，陳學武.公交出行路徑螞蟻算法[J].交通運輸工程學報，20-04，4(4)：103104.

［2］曾建潮，介婧，崔志華.微粒群算法[M].北京：科學出版社，20-04.1253.

［3］Kennedy J， Eberhart R C. Particle Swarm Optimization[C]. Proceedings of the IEEE International Conference on Neural Networks， Piscataway：IEEE Service Center， 1995.19421948.

［4］Shi Y， Eberhart R C.A Modified Particle Swarm Optimizer[C]. Proceedings of the IEEE International Conference on Evolutionary Computation，Piscataway：IEEE Press， 1998.6973.

［5］Kangping Wang， Lan Huang， Chunguang Zhou， et al. Particle Swarm Optimization for Traveling Salesman Problem[C]. Xi’an:Proceedings of the 2nd International Conference on Machine Learning and Cybernetics，2003.15831585.

［6］Clerc M. Discrete Particle Swarm Optimization Illustrated by the Trave￣ling Salesman Problem[EB/OL].http://www.mauriceclerc.net，2000.86123.

［7］肖健梅，李軍軍，王錫淮.求解車輛路徑問題的改進微粒群優(yōu)化算法[J].計算機集成制造系統(tǒng)，2005，11(4)：577579.

作者簡介：

張軍（1977），男，重慶人，博士研究生，主要研究方向為交通運輸規(guī)劃與管理、智能交通；

張學盡（1977），男，四川攀枝花人，講師，主要研究方向為交通工程、智能交通；

杜文（1941），男，上海人，教授，博導，主要研究方向為交通運輸規(guī)劃與管理、智能交通、系統(tǒng)工程理論；

王琳（1980），女，新疆烏魯木齊人，博士研究生，主要研究方向為交通運輸規(guī)劃與管理、智能交通。

注:本文中所涉及到的圖表、注解、公式等內(nèi)容請以PDF格式閱讀原文