基于蟻群算法的動(dòng)態(tài)路徑選擇優(yōu)化方法

安毅生，袁紹欣，趙祥模，岳 云

（長安大學(xué) 信息工程學(xué)院，西安710064）

基于蟻群算法的動(dòng)態(tài)路徑選擇優(yōu)化方法

安毅生＊，袁紹欣，趙祥模，岳 云

（長安大學(xué) 信息工程學(xué)院，西安710064）

為了確保城市路網(wǎng)交通流平穩(wěn)運(yùn)行和各路段交通流量合理分配，提出了一種基于偽隨機(jī)狀態(tài)轉(zhuǎn)移規(guī)則的動(dòng)態(tài)路徑選擇優(yōu)化方法.該方法首先計(jì)算路段上流量和路阻，利用偽隨機(jī)狀態(tài)轉(zhuǎn)移規(guī)則和路徑、路段信息素更新規(guī)則，模擬了出行者在路網(wǎng)節(jié)點(diǎn)的擇路行為，實(shí)現(xiàn)了路徑選擇過程中靜態(tài)先驗(yàn)知識(shí)、動(dòng)態(tài)交通狀態(tài)及路徑選擇隨機(jī)性的綜合.算例結(jié)果表明，該方法能夠體現(xiàn)不同OD需求下路徑選擇的疊加效果和時(shí)延效果，相對于平衡分配法可獲得更好的路網(wǎng)交通均衡性，對于時(shí)變路況環(huán)境下的路徑誘導(dǎo)系統(tǒng)也具有一定的應(yīng)用價(jià)值.

智能交通；動(dòng)態(tài)路徑選擇；蟻群算法；交通網(wǎng)絡(luò)；轉(zhuǎn)移概率

1 引 言

動(dòng)態(tài)路徑選擇[1]是指在可獲取路網(wǎng)時(shí)變路況信息前提下，為確保路網(wǎng)交通流平穩(wěn)運(yùn)行和各路段交通流量合理分配，出行者綜合考慮交通擁擠程度和路徑長度所做出的交通行為選擇.路徑選擇是智能交通系統(tǒng)研究的一項(xiàng)重要內(nèi)容，尤其是先進(jìn)的交通管理系統(tǒng)（ATMS）、先進(jìn)的出行者信息系統(tǒng)（ATIS），以及車輛路徑誘導(dǎo)系統(tǒng)都與路徑選擇密切相關(guān).與動(dòng)態(tài)路徑選擇問題相關(guān)的實(shí)證研究有：許良等[2]對不確定條件下用戶路徑選擇行為理論進(jìn)行了綜述.王譜等[3]通過模擬出行者時(shí)變的路徑選擇行為，建立OD量變化與時(shí)變路徑流量演化的關(guān)系，并分析出行行為與路徑流量的關(guān)系.肖海燕等[4]在假設(shè)出行者只根據(jù)前一時(shí)刻交通信息做出路徑選擇的基礎(chǔ)上，構(gòu)造基于馬爾科夫過程的交通流動(dòng)態(tài)演化模型，并對其穩(wěn)定性進(jìn)行分析.文獻(xiàn)[5-7]分別從基于實(shí)時(shí)路況信息的動(dòng)態(tài)路徑規(guī)劃算法，彈性工作起始時(shí)間引起的交通錯(cuò)峰出行策略，多用戶動(dòng)態(tài)交通流分配模型等不同的角度探討時(shí)變交通網(wǎng)絡(luò)中的動(dòng)態(tài)路徑選擇及其應(yīng)用問題.上述工作更多地利用數(shù)值優(yōu)化方法研究出行者路徑選擇對交通流分配與優(yōu)化的影響，盡管能夠確保模型解的收斂性和精度，但是由于假設(shè)條件多、模型構(gòu)造復(fù)雜，以及求解時(shí)間復(fù)雜度大等原因，阻礙了其在智能交通系統(tǒng)路徑誘導(dǎo)服務(wù)及動(dòng)態(tài)交通流分配中的應(yīng)用.

蟻群算法(Ant Colony System,ACS)是根據(jù)螞蟻種群總能在巢穴與食物源之間找到最短路徑而提出的一種搜索算法[8]，具有正反饋、魯棒性和啟發(fā)式搜索等特點(diǎn)，適合于求解旅行商、二次分配、Job-shop調(diào)度等組合優(yōu)化問題.Mussone等[9,10]將ACS的元啟發(fā)式方法轉(zhuǎn)化為計(jì)算全局用戶均衡的最優(yōu)化，提出了針對DUE和SUE中多OD對、路段擁塞和彈性需求等特征的交通配流ACS求解算法.D’Acierno等[11]提出了用于大規(guī)模公共交通網(wǎng)絡(luò)仿真的蟻群優(yōu)化算法并對其收斂性進(jìn)行分析. Gallo等[12]通過模擬用戶路徑選擇行為和蟻流對信號設(shè)置的需求壓力，提出了基于ACS的城市路網(wǎng)信號設(shè)置優(yōu)化求解算法.在國內(nèi)，夏媛媛等[13]把蟻群算法與混沌優(yōu)化相結(jié)合求解動(dòng)態(tài)用戶最優(yōu)配流問題.聞?dòng)萚14]在城域交通控制實(shí)時(shí)滾動(dòng)優(yōu)化中應(yīng)用蟻群算法搜索路口的最優(yōu)信號燈相位序列.劉經(jīng)宇等[15]利用蟻群算法在城市交通路徑選擇中求解路程和時(shí)間均最優(yōu)的路徑.谷遠(yuǎn)利等[16]利用蟻群算法思想在交通控制與誘導(dǎo)協(xié)同模型中求解最佳路徑和最佳信號配時(shí)方案.

本文把蟻群算法中的狀態(tài)轉(zhuǎn)移規(guī)則、信息素更新規(guī)則與路徑選擇過程中的路段狀態(tài)方程和路段流量函數(shù)相結(jié)合，提出基于蟻群算法的動(dòng)態(tài)路徑選擇優(yōu)化方法，綜合路徑選擇的疊加效果和時(shí)延效果，通過對路段上流量和路阻的計(jì)算，實(shí)現(xiàn)了時(shí)變OD需求下動(dòng)態(tài)路徑選擇的模擬與優(yōu)化.

2 基于ACS的動(dòng)態(tài)路徑選擇方法

2.1 問題描述

城市路網(wǎng)G=(V,E)，其中V為節(jié)點(diǎn)集合，E為路段集合.G中的起迄對(r,s)構(gòu)成一個(gè)集合L，即L={(r,s)|r∈R,s∈S,R?S?V}，R為起點(diǎn)集合，S為終點(diǎn)集合.在已知時(shí)變OD需求前提下，每個(gè)出行者在進(jìn)入后繼節(jié)點(diǎn)之前均要進(jìn)行路徑選擇.非飽和路網(wǎng)條件下，出行者偏好選擇最短路徑，飽和路網(wǎng)或過飽和路網(wǎng)條件下，出行者傾向于選擇距離較短、流量較小、且行駛時(shí)間最少的路段，即出行者把出行前的路徑預(yù)測與出行過程中對實(shí)時(shí)路況的反應(yīng)進(jìn)行綜合考慮.據(jù)此，出行者路徑選擇的概率模型可用下式表示：

式中 k表示出行者；i和 j分別表示當(dāng)前節(jié)點(diǎn)及其后繼節(jié)點(diǎn)；j∈Ni，Ni是后繼節(jié)點(diǎn)的集合；表示第k個(gè)出行者選擇節(jié)點(diǎn) j的可能性且表示選擇節(jié)點(diǎn) j的效用；表示第k個(gè)出行者在節(jié)點(diǎn)i選擇節(jié)點(diǎn) j作為目的節(jié)點(diǎn)的轉(zhuǎn)移概率.

2.2 約束條件

基于ACS的動(dòng)態(tài)路徑選擇問題求解時(shí)應(yīng)遵循以下約束條件：

（1）由于OD需求具有明確的方向性，路徑選擇過程遵循單向通行原則；

（2）路網(wǎng)中的節(jié)點(diǎn)非全連通，節(jié)點(diǎn)之間存在預(yù)設(shè)的后繼關(guān)系，因此后繼節(jié)點(diǎn)必須是當(dāng)前節(jié)點(diǎn)的鄰接節(jié)點(diǎn)，一般有二至三個(gè)；

（3）路網(wǎng)中出行者的數(shù)目隨OD需求變化，并且每個(gè)節(jié)點(diǎn)都可能產(chǎn)生新的流量，流入該節(jié)點(diǎn)的流量和此刻該節(jié)點(diǎn)新產(chǎn)生的流量之和應(yīng)與該節(jié)點(diǎn)的流出量相等；

（4）初始時(shí)刻，路網(wǎng)中既沒有流入量也沒有流出量.

2.3 優(yōu)化算法

2.3.1 路徑選擇規(guī)則

出行者路徑選擇行為基于偽隨機(jī)轉(zhuǎn)移規(guī)則實(shí)現(xiàn)，在初始化階段設(shè)置一個(gè)參數(shù)q0(0≤q0≤1)，每當(dāng)出行者需要做出路徑選擇時(shí)，生成一個(gè)均勻分布在[0,1]區(qū)間上的隨機(jī)數(shù)q，通過比較q與q0的關(guān)系使用不同的路徑選擇規(guī)則：

2.3.2 信息素更新規(guī)則

出行者選擇某個(gè)效用較高的路段后，就會(huì)在該路段上釋放一定量的信息素作為其他出行者選擇該路段的啟發(fā)因子.當(dāng)大量的出行者選擇同一路段后，該路段上的信息素就會(huì)增加，一方面會(huì)有更多的出行者選擇該路段，另一方面該路段上的流量也會(huì)增加進(jìn)而降低了選擇該路段的效用.因此，為了避免過高信息素誘使出行者聚集于某一路段降低通行效率，必須給出相應(yīng)的信息素更新規(guī)則：

（1）路徑信息素更新規(guī)則：每一時(shí)段每一O-D對間多個(gè)出行者完成路徑選擇后采用式（3）進(jìn)行信息素更新：

（2）路段信息素更新規(guī)則：每個(gè)出行者完成一步路徑選擇后，在所經(jīng)過的路段上采用式（4）進(jìn)行信息素更新：

式中 τij為路段(i,j)上的信息素；為路段(i,j)上信息素的初始值；ξ表示路段上信息素的揮發(fā)參數(shù).

2.3.3 節(jié)點(diǎn)流量更新規(guī)則

求解過程中，由于出行者逐個(gè)節(jié)點(diǎn)決策的行為呈現(xiàn)出離散化特征，因此本文將研究的時(shí)段進(jìn)行相應(yīng)的離散化，即將所考慮的時(shí)段[0,T]劃分為N個(gè)小時(shí)段，并且在每個(gè)小時(shí)段進(jìn)入任一條路段的車輛不能在同一個(gè)小時(shí)段離開該路段.

迄今為止，所有離散時(shí)間的路段狀態(tài)方程均采用以下形式：

節(jié)點(diǎn)流量更新規(guī)則用于說明節(jié)點(diǎn)的流量守恒特性，即對于任意節(jié)點(diǎn)，流入該節(jié)點(diǎn)的流量和此時(shí)該節(jié)點(diǎn)新產(chǎn)生的流量之和與此節(jié)點(diǎn)的流出量相等，離散化的節(jié)點(diǎn)流量守恒規(guī)則如式（6）所示：

2.3.4 算法

算法求解過程使用以下變量或數(shù)據(jù)結(jié)構(gòu)：

（1）路 段 容 量 向 量 Q=(Q1,Q2,…,Qn)：Qa=la×eam，其中a為任意路段，la為路段a的長度，eam為路段a的最大車流密度；

（3）當(dāng)n≠0時(shí)，n時(shí)段各路段上的阻抗向量，其中 xa(n)為n時(shí)段a路段上的流量，Qa為a路段上的容量，α'和β'為調(diào)節(jié)參數(shù).

算法基于ACS的動(dòng)態(tài)路徑選擇優(yōu)化算法（ACS-DRC,Ant colony system based dynamic route choiceAlgorithm）.

輸入OD需求矩陣、路網(wǎng)信息、阻塞密度、自由流速、q0、K(=1)等.輸出各時(shí)段（K=1,2,…,N）各路段上的流量.

Step1根據(jù)路網(wǎng)獲取起訖點(diǎn)和相應(yīng)OD需求量，按照交通量確定用于搜索的出行者數(shù)目；

Step2設(shè)置各路段上的信息素的初值及流量，計(jì)算各路段長度的倒數(shù)，將出行者置于起始節(jié)點(diǎn)；

Step3當(dāng)出行者需要擇路時(shí)，按照式(2)所示路徑選擇規(guī)則產(chǎn)生一個(gè)隨機(jī)數(shù)q，比較q與q0的大小，確定出行者選擇的下一路段；

Step4對所選路段按照式(4)對其路段信息素進(jìn)行更新，并按照離散時(shí)間路段狀態(tài)方程式(5)對該路段上的流量進(jìn)行更新；

Step5轉(zhuǎn)至Step3，直到該OD對上出行者全部完成路徑選擇到達(dá)終點(diǎn)；Step6根據(jù)式(3)對路徑上的信息素進(jìn)行更新；Step7轉(zhuǎn)Step2繼續(xù)執(zhí)行，直到所有OD對上的出行者均完成路徑選擇；

Step8若OD矩陣中全部時(shí)段的交通量均分配完，則結(jié)束.否則K=K+1，轉(zhuǎn)至Step1.

2.3.5 算法可靠性

算法的可靠性分析分為兩部分：

①確定路段上信息素的上界.在式（2）中，啟發(fā)式信息主要由路段上時(shí)變的流量和距離確定，因而只要能夠給出信息素的上界，對于具體的路網(wǎng)實(shí)例，基于路徑選擇規(guī)則的擇路行為是可解的.

②在算法可解的基礎(chǔ)上，通過與增量分配法、平衡分配法計(jì)算結(jié)果的比較進(jìn)一步確定算法是有效的.

命題1在ACS-DRC問題中，結(jié)合算法中的路徑和路段信息素更新規(guī)則，對于任意路段(i,j)上的信息素τij，有下式成立：

式中 g(s*)表示任意路段(i,j)上的信息素的最大增量.

證明：在ACS-DRC算法的擇路過程中，出行者沒完成一步路徑選擇后用式（4）更新路段信息素，每一時(shí)段每一O-D對多個(gè)出行者完成路徑選擇后將采用式（3）更新路徑信息素.兩種信息素更新規(guī)則形式相同，可以用如下的統(tǒng)一形式?k+1=(1-φ)·?k+φ·b表示.?k+1和?k分別代表τij(k+1)和τij(k)，φ代表α或ξ，b代表Δτij，這里Δτij的最大值為g(s*).所以每次擇路后各路段上信息素的增量最多為g(s*)，其中s*為最優(yōu)的分配方案.

各時(shí)段的最大信息量分別為

由此，可以確定路段上信息素的上界為g(s*)，進(jìn)而可以確定算法描述的擇路行為是可解的.

3 算 例

算例路網(wǎng)如圖1所示，其中路網(wǎng)節(jié)點(diǎn)集合為{①,②,③,④,⑤,⑥,⑦,⑧}，路段集合為{1,2,3,4, 5,6,7,8,9,10,11}，路段號后括號內(nèi)的數(shù)字為路段長度.節(jié)點(diǎn)①、③為起始節(jié)點(diǎn)O1和O2，節(jié)點(diǎn)⑥、⑧為終止節(jié)點(diǎn)D1和D2，以上起訖點(diǎn)共組成了4個(gè)OD對及12條路徑，路徑組成如表1所示.各個(gè)時(shí)段OD對間產(chǎn)生的交通需求如表2所示.

圖1 算例路網(wǎng)Fig.1 Traffic network example

路網(wǎng)參數(shù)包括阻塞密度Kj=125 pcu·km-1；自由流速vf=40 km·h-1；通行能力為1 250veh/h；研究時(shí)段總長為20 min，算法求解時(shí)將其分解為10個(gè)時(shí)間段.采用本文所提路徑選擇優(yōu)化方法得到各時(shí)段各路段上的流量分配情況如表3所示.

表1 路網(wǎng)中的候選路徑組成表Table1 Optional routes in traffic network

表2 每個(gè)OD對間各時(shí)段交通需求Table2 Volume of traffic between each OD pairs and each time periods

表3 采用ACS-DRC算法的各路段各時(shí)段流量分配情況Table3 Traffic assignment based on ACS-DRC

表3中以K=1時(shí)段為例，四對OD需求分別是19、12、8、16，流量在除去起始節(jié)點(diǎn)和終止節(jié)點(diǎn)的節(jié)點(diǎn)集合上均保持守恒，如節(jié)點(diǎn)④的輸入流量分布在路段3和路段5上，合計(jì)為(17+24)，同時(shí)節(jié)點(diǎn)④的輸出流量分布在路段6和路段8上，合計(jì)為(18+19).此外，在節(jié)點(diǎn)②處，由于首輪迭代的原因各路段上的初始流量均為零，因此按照式(2)選擇下一節(jié)點(diǎn)時(shí)更多地選擇了長度較短的路段4.對于K=2時(shí)段，路段1上的流量為30.41，其中上一時(shí)段的流量為14，本時(shí)段由(O1,D1)產(chǎn)生的流入量為10，由(O1,D2)產(chǎn)生的流入量為9，同時(shí)路段1的流出量為2.59，該值為路段1上的流量與BPR函數(shù)計(jì)算出的路段阻抗之比，其他節(jié)點(diǎn)的流量計(jì)算方法與此類似，不作贅述.

圖2分別給出了采用本文方法和增量分配法、平衡分配法進(jìn)行路徑選擇時(shí)獲得的各時(shí)段各路段上流量的統(tǒng)計(jì)數(shù)據(jù).對比發(fā)現(xiàn)，圖2(a)中各路段的流量并不均衡，一些路段如2、4、8上的流量很小，而另一些路段如5、6、7上的流量則較大.對于K=10時(shí)段，各路段流量的均方差為43.70.圖2(b)的效果較圖2(a)有所改進(jìn)，如路段4、8上的流量明顯增加，但是路段5、6、7上的流量仍然較大.對于K=10時(shí)段，各路段流量的均方差為42.12.顯然這兩種路徑選擇策略將會(huì)導(dǎo)致交通流量主要集中于路網(wǎng)中的某一條或某幾條路段上，不同路段上流量差異較大，隨著這些路段上負(fù)荷的增大，容易引發(fā)交通擁堵.圖2(c)顯示了出行者使用ACS-DRC進(jìn)行擇路的效果，同樣K=10時(shí)段，各路段流量的均方差為41.54，該方法能夠在整個(gè)路網(wǎng)均衡地分配流量，避免了某些路段上流量的急劇增加，并且隨時(shí)間和OD需求的增長，各路段流量增加緩慢，有助于減少車輛在道路上的旅行時(shí)間.

圖2 流量分配詳情Fig.2 Detail of traffic assignment

4 研究結(jié)論

路徑選擇問題是ITS中先進(jìn)交通管理系統(tǒng)、先進(jìn)出行者信息系統(tǒng)，以及車輛路徑誘導(dǎo)系統(tǒng)關(guān)鍵共性問題，同時(shí)它也是動(dòng)態(tài)交通配流領(lǐng)域重要的理論問題.本文把蟻群算法中的概率轉(zhuǎn)移規(guī)則、信息素更新規(guī)則與路徑選擇過程中的路段狀態(tài)方程和路段流量函數(shù)相結(jié)合，提出基于蟻群算法的動(dòng)態(tài)路徑選擇優(yōu)化方法.通過對路段上流量和路阻的計(jì)算，實(shí)現(xiàn)了路徑選擇過程中靜態(tài)先驗(yàn)知識(shí)、動(dòng)態(tài)交通狀態(tài)，以及路徑選擇隨機(jī)性的綜合.本文最后利用算例對所提方法進(jìn)行了測試.結(jié)果表明，該方法能夠體現(xiàn)不同OD需求下路徑選擇的疊加效果和時(shí)延效果，相對于增量分配法和平衡分配法更易于實(shí)現(xiàn)路網(wǎng)交通的均衡性.

參考文獻(xiàn)：

[1]高自友,任華玲.城市動(dòng)態(tài)交通流分配模型與算法[M].北京:人民交通出版社,2005.[GAO Z Y,REN H L.Dynamic traffic assignment problems in urban trans?portation networks:models and methods[M].Beijing: China Communications Press,2005.]

[2]許良,高自友.不確定條件下用戶路徑選擇行為研究述評[J].燕山大學(xué)學(xué)報(bào)(哲學(xué)社會(huì)科學(xué)版),2007,8(1): 139-144.[XU L,GAO Z Y.Review on user route choice behavior model under uncertainty[J].Journal of Yanshan University(Philosophy and Social Science Edi?tion).2007,8(1):139-144.]

[3]王譜,孫會(huì)君.基于自適應(yīng)規(guī)則的擇路演化研究[J].交通運(yùn)輸系統(tǒng)工程與信息,2010,10(4):86-92.[WANG P,SUN H J.Route choice evolving under adaptive rule [J].Journal of Transportation Systems Engineering and Information Technology,2010,10(4):86-92.]

[4]肖海燕.基于馬爾科夫的動(dòng)態(tài)交通流演化模型及應(yīng)用[J].武漢大學(xué)學(xué)報(bào)工學(xué)版,2012,45(2):255-258. [XIAO H Y.Modeling of dynamic traffic flow evolution based on Markov chain and its application[J].Engineer?ing Journal of Wuhan University,2012,45(2):255-258.]

[5]雷東升，諸彤宇.一種基于實(shí)時(shí)路況信息的動(dòng)態(tài)路徑規(guī)劃算法[J].計(jì)算機(jī)科學(xué)，2008，35(4A)：28-30.[LEI D S,ZHU T Y.A dynamic route planning algorithm based on real-time traffic information[J].Computer Sci?ence,2008,35(4A):28-30.]

[6]袁紹欣,趙祥模,安毅生，等.交通錯(cuò)峰出行策略仿真模型[J].長安大學(xué)學(xué)報(bào)(自然科學(xué)版),2010,30(5):75-78.[YUAN S X,ZHAO X M,AN Y S,et al.Simulation model of travel strategies for staggered shifts[J].Journal of Chang’an University(Natural Science Edition),2010, 30(5):75-78.]

[7]何勝學(xué),范炳全.多用戶動(dòng)態(tài)交通流分配模型及算法研究[J].上海理工大學(xué)學(xué)報(bào),2006,28(5):460-464. [HE S X,FAN B Q.Multi-user dynamic traffic assign?ment model and relevant algorithm[J].Journal of Univer?sity of Shanghai for Science and Technology,2006,28 (5):460-464.]

[8]Dorigo M,Stutzle T.Ant colony optimization[M].Cam? bridge(MA):The MIT Press,2004.

[9]Mussone L,Matteucci M.An application of Ant Colony Systems for DUE and SUE assignment in congested transportation networks[C]//Proceedingsofthe 11th World Conference on Transport Research,Berkeley (CA),USA,2007.

[10]Matteucci M,Mussone L.An ant colony system for trans?portation user equilibrium analysis in congested net?works[J].Swarm Intelligence,2013,7(4):255-277.

[11]D’Acierno L,Gallo M,Montella B.Ant colony optimisa?tion approaches for the transportation assignment prob?lem[J].WIT Transactions on the Built Environment 111, 2010,37-48.

[12]Gallo M,D’Acierno L,Montella B.An ant colony optimi?sation algorithm for solving the asymmetric traffic assign?ment problem[J].European Journal of Operational Re?search,2012,217(2):459-469.

[13] 夏媛媛，馬立云，王曉原.基于混沌蟻群算法的動(dòng)態(tài)用戶最優(yōu)配流方法[J].山東理工大學(xué)學(xué)報(bào)(自然科學(xué)版),2011,25(3):17-21.[XIA Y Y,MA L Y,WANG X Y.Dynamic users optimum traffic assignment method based on chaos ant colony algorithm[J].Journal of Shan?dong University of Technology(Natural Science Edi?tion),2011,25(3):17-21.]

[14]聞?dòng)?，吳鐵軍.基于蟻群算法的城域交通控制實(shí)時(shí)滾動(dòng)優(yōu)化[J].控制與決策，2004，19(9)：1057-1063. [WEN Y,WU T J.Real-time rolling horizon optimiza?tion of urban traffic control based on ant algorithm[J]. Control and Decision,2004,19(9):1057-1063.]

[15] 劉經(jīng)宇，方彥軍.蟻群算法在城市交通路徑選擇中的應(yīng)用[J].西南交通大學(xué)學(xué)報(bào)，2009，44(6)：912-917. [LIU J Y,FANG Y J.Urban vehicle routing based on ant colony algorithm[J].Journal of southwest jiaotong university.2009,44(6):912-917.]

[16] 谷遠(yuǎn)利，李善梅，邵春福.基于蟻群算法的交通控制與誘導(dǎo)協(xié)同研究[J].系統(tǒng)仿真學(xué)報(bào)，2008，20(10)：2754-2761.[GU Y L,LI S M,SHAO C F.Study on co?operation of traffic control and route guidance based on ant algorithm[J].Journal of System Simulation,2008,20 (10):2754-2761.]

Optimization of Dynamic Route Choice Based on Ant Colony Algorithm

AN Yi-sheng，YUAN Shao-xin，ZHAO Xiang-mo，YUE Yun
（School of Information Engineering,Chang’an University,Xi’an 710064,China）

To ensure the stable operation of urban traffic flow and the rational traffic flow assignment for each road section,this study develops a pseudo-random state transition rules based on dynamic route choice optimization method.The traffic flow and impedance on each road section are calculated,and then the individual traveler’s route choice behaviors on network nodes are simulated by applying the pseudo-random state transition rules,route and section pheromone update rules.It implements the synthesizing of static prior knowledge,dynamic traffic state and the randomness of route choice.Test example shows that the method is capable of reflecting the overlay and delay effect of route choice under different OD demands.In addition, this method can obtain better network equilibrium compared with the equilibrium assignment method,which will also benefit for achieving the route guidance system with time-varying traffic conditions.

intelligent transportation;dynamic route choice;ant colony algorithm;traffic network;transition probability

1009-6744（2014）03-0097-07

U491.265

A

2013-08-27

2014-03-01錄用日期：2014-03-10

國家自然科學(xué)基金（50978030，51278058）；長江學(xué)者和創(chuàng)新團(tuán)隊(duì)發(fā)展計(jì)劃（IRT0951）；中國博士后科學(xué)基金（2012M521729）；陜西省自然科學(xué)基礎(chǔ)研究計(jì)劃項(xiàng)目（2014JZ019）.

安毅生（1972-），男，陜西西安人，教授，博士后.*通訊作者：aysm@chd.edu.cn