改進蟻群算法的多約束質(zhì)量最優(yōu)路徑選擇

馬榮貴,崔 華,薛世焦,郭 璐,袁 超

(長安大學(xué)信息工程學(xué)院,陜西西安 710064)

改進蟻群算法的多約束質(zhì)量最優(yōu)路徑選擇

馬榮貴,崔 華,薛世焦,郭 璐,袁 超

(長安大學(xué)信息工程學(xué)院,陜西西安 710064)

在交通擁堵日益嚴(yán)重的形勢下,當(dāng)今大眾對行車過程中的道路質(zhì)量評定標(biāo)準(zhǔn)發(fā)生了重大變化,如何避開擁堵,尋找最優(yōu)的出行路徑,已成為智慧城市建設(shè)大力推進背景下亟待解決的重要科學(xué)問題和社會問題.首先,定義了質(zhì)量最優(yōu)路徑的概念,并構(gòu)建了多約束質(zhì)量最優(yōu)路徑模型;然后,為更有效求解該模型實現(xiàn)最優(yōu)路徑選擇,在基本蟻群路徑尋優(yōu)算法的基礎(chǔ)上,通過增加算法對道路通暢度、道路舒適度、道路費用等路徑質(zhì)量信息的實時感知,改進了狀態(tài)轉(zhuǎn)移規(guī)則中的啟發(fā)函數(shù)和信息素更新算子,提高了算法自適應(yīng)于路徑質(zhì)量信息的動態(tài)調(diào)整能力.實驗結(jié)果表明:文中改進的蟻群算法與其他蟻群路徑尋優(yōu)算法相比,明顯提高了路徑尋優(yōu)的正確率和收斂速度,能夠更加快速、準(zhǔn)確地進行路徑選擇.

多約束路徑選擇;質(zhì)量最優(yōu)路徑;蟻群算法;信息素更新;啟發(fā)函數(shù)

隨著私家車的日益增多,交通安全及交通擁堵問題也越來越嚴(yán)重,如何誘導(dǎo)車輛在出行時選擇“高質(zhì)量”的路線是一個普遍的難題[1-2].把“最優(yōu)路徑”定義為只考慮最短路徑或者最少費用等單一約束的最優(yōu)問題已經(jīng)不能滿足大眾的需求,而最優(yōu)路徑搜索本質(zhì)上是在路網(wǎng)中尋找能夠同時滿足駕駛者期望的多個約束條件且某個單項目標(biāo)值最小的路徑.在路徑尋找中具有兩個以上限制的路徑問題是非確定多項式(Nondeterministic Polynomial,NP)問題,采用傳統(tǒng)的搜索算法無法解決,而蟻群算法是一種具有正反饋機制、分布式并行機制、自組織機制等特征的優(yōu)化方法,能夠在道路搜索過程中感知周圍環(huán)境的實時變化,用于尋找最優(yōu)路徑具有極大的優(yōu)勢.文獻[3]采用基本蟻群算法解決最優(yōu)路徑導(dǎo)航問題;文獻[4]引入路徑權(quán)值矩陣改進了基本蟻群問題的轉(zhuǎn)移規(guī)則,提高了向最優(yōu)路徑轉(zhuǎn)移的概率,改善了最優(yōu)路徑導(dǎo)航效果;文獻[3-5]中研究的最優(yōu)路徑僅與行車距離有關(guān);文獻[6]考慮了螞蟻的動態(tài)變異,并對基本蟻群算法的信息素濃度更新規(guī)則進行了改進,實現(xiàn)了對動態(tài)最短路徑的實時導(dǎo)航,該改進方法更有利于螞蟻找到最優(yōu)路徑,其最優(yōu)路徑僅與行車距離有關(guān).

以上文獻利用蟻群算法構(gòu)建路徑優(yōu)化選擇算法時,不僅蟻群算法本身的路徑搜索性能有待改善,而且路徑導(dǎo)航的約束條件也不能滿足當(dāng)今實際應(yīng)用的要求.文獻[7-9]提出了“路徑質(zhì)量”概念和“可靠路徑”概念,但這些定義大都限定在未飽和的交通狀態(tài)下選擇最優(yōu)路徑,這顯然與當(dāng)今日益擁堵的交通狀況不相適宜.筆者考慮到交通擁堵、道路舒適性等諸多影響駕駛者選擇行車路徑的因素,結(jié)合當(dāng)今大眾對最優(yōu)路徑的評定標(biāo)準(zhǔn),將最優(yōu)路徑的概念重新定義為“多約束質(zhì)量最優(yōu)路徑”,即一條好的路徑應(yīng)是滿足行車距離、到達時限、行駛費用、實時道路交通狀況、行車舒適性等多約束條件的距離最短道路,并通過改進蟻群算法,在車輛出發(fā)地和目的地之間的路網(wǎng)中快速準(zhǔn)確地求解出按照多約束條件選定的一條質(zhì)量最優(yōu)路徑.

1　質(zhì)量最優(yōu)路徑模型

傳統(tǒng)意義上的最優(yōu)路徑指的是車輛在起點和終點間選擇一條距離最短的路徑,這時質(zhì)量最優(yōu)路徑僅與行車距離有關(guān).考慮到當(dāng)今道路交通狀況比較擁堵,駕駛者希望避開擁堵路段,另外,駕駛者在選擇路徑時會考慮多方面的因素,如選擇從起始點到目的地距離最短的道路,希望花費時間在預(yù)期范圍內(nèi),希望過路費、燃油費等成本不太高,希望道路通暢而不希望道路限行或由交通事故、施工等引起的交通擁堵,希望道路舒適度高.道路舒適度取決于道路級別、道路寬度(車道數(shù))、路面平整度、光滑度、附著度等指標(biāo)以及路邊環(huán)境的美化狀況、交通事故發(fā)生率、道路限速、鄰接交叉口的信號配時等.文中依據(jù)當(dāng)今大眾對路徑質(zhì)量的評定標(biāo)準(zhǔn),將質(zhì)量最優(yōu)路徑模型定義為如下的多約束優(yōu)化問題:

其中,cij表示道路節(jié)點i與節(jié)點j之間的長度;s為連接o和d之間的一條路徑,o代表起始點,d代表終止點;如果t時刻弧cij在路徑s上,則;否則,;NS表示路網(wǎng)的節(jié)點集;T表示所選路徑實際花費的總時間;Tb表示出行允許的時間上限;cfij為路段cij的舒適度,cfij∈(0,1),越接近1表示該道路的舒適度越好;cfb表示駕駛員能接受的道路舒適度的下限;jij為路段cij的實時道路交通情況,jij在(0,1)之間取值,越接近1表示交通暢通情況越好;jb表示駕駛者能接受的道路暢通度的下限,當(dāng)函數(shù)值為0時,表示該道路嚴(yán)重擁堵或者該道路禁止通行;C表示所選路徑的總費用;為所走路徑的收費;(1+為所走路徑需要的燃料費用;fij為路段cij的收費金額;k表示平均每公里的燃料費用;g表示車輛行駛在不同暢通狀態(tài)路段的耗油量增加的百分比;fmax表示駕駛員能容忍的道路費用的最大值.

2　改進的蟻群算法

在基本蟻群算法中[10],螞蟻依據(jù)狀態(tài)轉(zhuǎn)移規(guī)則選擇下一個道路節(jié)點,即

2.1改進的啟發(fā)函數(shù)

基本的蟻群算法不考慮螞蟻遍歷節(jié)點的方向性,所以將啟發(fā)函數(shù)ηij(t)設(shè)置為螞蟻在t時刻在道路節(jié)點i與待選節(jié)點j的距離dij的倒數(shù).這種啟發(fā)函數(shù)會導(dǎo)致路徑尋優(yōu)問題中的螞蟻貪圖單步最短而偏離行進方向,尋找到的路徑未必是總體最短路徑.為此,文中綜合考慮了當(dāng)前位置與轉(zhuǎn)移后位置之間的距離、螞蟻已走過的路徑距離以及轉(zhuǎn)移后位置與目的地之間的距離,將啟發(fā)函數(shù)修改為

其中,L(i)表示從起點到節(jié)點i螞蟻已經(jīng)走過的道路長度;Djd為j點到目標(biāo)點d的距離.式(4)所示的改進的路徑選擇啟發(fā)函數(shù),有效加強了路徑搜索的方向性和準(zhǔn)確性,可引導(dǎo)螞蟻在行進過程中有目的地不斷向目標(biāo)點靠近,保證了螞蟻所走過的總路程是最短的,滿足文中尋求多約束條件下最短路徑的目標(biāo).

2.2改進的信息素更新規(guī)則

為誘導(dǎo)螞蟻更快更準(zhǔn)地找到滿足約束的質(zhì)量最優(yōu)路徑,構(gòu)造函數(shù)F(b)將質(zhì)量最優(yōu)路徑模型的多約束條件有效融合到蟻群算法中,讓蟻群實時感知道路的舒適度、暢通度等質(zhì)量狀況,指導(dǎo)蟻群及時調(diào)整路徑搜索策略,即

其中,p和q表示從起點到終點經(jīng)過的路段的數(shù)目;F1、F2、F3和F4分別表示路徑b上的費用、行駛時間滿足駕駛者時間要求的程度、平均暢通情況和道路平均舒適度;χ、γ、λ和μ為正實數(shù),分別表示駕駛者對道路費用、時間、暢通度和舒適度的重視程度.為誘導(dǎo)螞蟻以較大概率選擇質(zhì)量最優(yōu)路徑,在信息素全局更新時,考慮了路徑質(zhì)量狀況,并通過強化最優(yōu)路徑上的信息素和弱化最差路徑上的信息素,促使螞蟻選擇最好路徑而放棄最差路徑.改進的信息素濃度更新公式為

其中,ρ是信息素揮發(fā)程度因子,F(b)是式(5)所述的反映路徑質(zhì)量狀況的函數(shù),Lbest和Lworst分別表示算法找到的最好路徑s*和最差路徑s′的長度,ε為信息素強化因子.為有效避免各個路段信息素濃度差異過大,而導(dǎo)致算法陷入局部最優(yōu),信息素濃度進行如下限制:

3　仿真與分析

圖1為道路網(wǎng)絡(luò)拓撲圖,每條邊某時刻的屬性用一個5元組(len,spe,f,j,cf)來表示,依次代表邊上的距離(km)、允許速度(km/h)、通行費用(元)、實時道路暢通度和道路的舒適度,并假設(shè)車輛在行駛過程中,當(dāng)接近任何路口時可及時獲得待選路網(wǎng)各路段未來15 min的交通信息預(yù)測值.實驗參數(shù)設(shè)定如下:允許的行車時間Tb≤7 h道路的暢通度j>0.4,所走道路舒適度cf>0.3;基本蟻群和半改進蟻群算法中,α=1,β=3,m=14,n=14,Q=10,ρ=0.55,Nmax=100;改進的蟻群算法中,α=2,β=5,m=14,n=14,Q=10,ρ=0.55,Nmax=100,Tb=7,k=0.5,τmax=20,τmin=1,ξ=0.01,χ=0.01,γ=1,λ=5,μ=5,τ0=τmax.

圖1　道路拓撲圖

為驗證文中提出的基于改進蟻群算法的質(zhì)量最優(yōu)路徑選擇方法的性能,進行了如下實驗.實驗結(jié)果如表1和圖2所示.表1是100次Monte Carlo仿真實驗得到的各算法性能結(jié)果.從表1可以看出,基本蟻群算法和半改進蟻群算法找到的最優(yōu)路徑在圖1中由箭頭標(biāo)注,此路徑也是從起點到終點的總體最短路徑,但是此路徑途徑擁堵路段及個別路段的舒適度很低,不滿足文中定義的多約束質(zhì)量最優(yōu)路徑.改進蟻群算法找到了文中定義的多約束質(zhì)量最優(yōu)路徑1-5-7-11-14,避開了擁堵路段,途徑的每個路段的舒適度都很高,而且尋優(yōu)率和尋優(yōu)時間都有很大的改善.說明在文中基于質(zhì)量最優(yōu)路徑模型對信息素更新準(zhǔn)則和啟發(fā)函數(shù)的改進是有效的,使得文中提出的改進蟻群算法具有良好的路徑尋優(yōu)性能,在路網(wǎng)擁堵情況下成功選擇了暢通或較低擁堵度的路段,而避開了擁堵更嚴(yán)重的路段.從圖2可知,文中改進的蟻群算法經(jīng)過約80次迭代便可找到最優(yōu)路徑,而基本蟻群算法、半改進蟻群算法則需要更多的迭代次數(shù)才能收斂到最優(yōu)路徑,說明了文中對基本蟻群算法在啟發(fā)函數(shù)和信息素更新準(zhǔn)則兩方面所進行的改進的有效性,增強了算法依據(jù)道路屬性實時變化而產(chǎn)生的正反饋作用,提高了算法的收斂速度和路徑尋優(yōu)速度.而表1所示的3種蟻群算法的運行時間同樣體現(xiàn)了改進蟻群算法具有最快的尋優(yōu)速度.

圖2　3種算法的收斂曲線

表1　蟻群算法的路徑尋優(yōu)結(jié)果

4　結(jié)束語

針對最優(yōu)路徑選擇問題,根據(jù)當(dāng)今大眾對路徑質(zhì)量的評定標(biāo)準(zhǔn),文中定義了質(zhì)量最優(yōu)路徑模型,進一步地,為更高效求解多約束條件下的質(zhì)量最優(yōu)路徑問題,通過定義新的信息素更新因子和新的狀態(tài)轉(zhuǎn)移啟發(fā)因子對基本蟻群算法進行了改進,并對提出的改進蟻群算法的路徑尋優(yōu)性能進行了實驗驗證.實驗結(jié)果表明,文中提出的導(dǎo)航算法較基本蟻群算法在路徑尋優(yōu)速度和正確率方面有較大提高.

[1]YAO E J,LANG Z F,YANG Y.Vehicle Routing Problem Solution Considering Minimising Fuel Consumption[J]. IEEE Transactions on Intelligent Transportation Systems,2015,9(5):523-529.

[2]LIN X,LO H K.Adaptive Vehicle Navigation with EN Route Stochastic Traffic Information[J].IEEE Transactions on Intelligent Transportation Systems,2014,15(5):1900-1912.

[3]HAMZHEEI M,FARAHANI R Z,RASHIDI-BAJGAN H.An Ant Colony-based Algorithm for Finding the Shortest Bidirectional Path for Automated Guided Vehicles in a Block Layout[J].The International Journal of Advanced Manufacturing Technology,2013,64(4):399-409.

[4]HUANG M,DING P.An Improved Ant Colony Algorithm and Its Application in Vehicle Routing Problem[J]. Mathematical Problems in Engineering,2013,2013:1-9.

[5]SCHYNS M.An Ant Colony System for Responsive Dynamic Vehicle Routing[J].European Journal of Operational Research,2015,245(3):704-718.

[6]LISSOVOI A,WITT C.Runtime Analysis of Ant Colony Optimization on Dynamic Shortest Path Problems[C]// Proceedings of the 2013 Genetic and Evolutionary Computation Conference,Association for Computing Machinery.New York:ACM,2013:1605-1612.

[7]REED M,YIANNAKOU A,EVERING R.An Ant Colony Algorithm for the Multi-compartment Vehicle Routing Problem[J].Applied Soft Computing,2014,15:169-176.

[8]MAVROVOUNIOTIS M,YANG S X.Ant Algorithms with Immigrants Schemes for the Dynamic Vehicle Routing Problem[J].Information Sciences,2015,294:456-477.

[9]NIE Y,WU X.Shortest Path Problem Considering on-time Arrival Probability[J].Transportation Research Part B: Methodological,2009,43(6):597-613.

[10]MAHI M,BAYKAN O K,KODAZ H.A New Hybrid Method Based on Particle Swarm Optimization,Ant Colony Optimization and 3-Opt Algorithms for Traveling Salesman Problem[J].Applied Soft Computing,2015,30:484-390.

(編輯:齊淑娟)

Improved ant colony algorithm for the optimal-quality-path routing problem with multi-constraints

MA Ronggui,CUI Hua,XUE Shijiao,GUO Lu,YUAN Chao
(School of Information Engineering,Chang’an Univ.,Xi’an 710064,China)

As the traffic congestion becomes more and more serious,the public evaluation standard for the road quality during driving changes greatly.How to avoid congestion to find the best way to travel has become an important scientific issue and social issue urgent to address in the context of building a smart city.Thus this paper first defines the novel concept of optimal path with multi-constraints and models it. Then,in order to solve the proposed model more efficiently,we improve the state transition rules of the heuristic function and pheromone update operator based on the classical ant colony algorithm by increasing the path optimization algorithm’s awareness of real-time path quality information,such as traffic conditions,resulting in the strong dynamic adjustment ability of our proposed path optimization algorithm to path information.Simulation results show that our proposed ant colony algorithm can find the optimal path with multi-constraints more accurately and more quickly than other ant colony algorithms.

multi-constraint path routing;optimal quality path;ant colony algorithm;pheromone update;heuristic function

TP751

A

1001-2400(2016)03-0185-05

10.3969/j.issn.1001-2400.2016.03.032

2015-08-24

國家“863”計劃資助項目(2012AA112312);中央高校基本科研業(yè)務(wù)費專項資金重點資助項目(310824152009)

馬榮貴(1967-),男,教授,博士,E-mail:rgma@che.edu.cn.