李松江，張異，龔躍

（長春理工大學計算機科學技術(shù)學院，長春 130022）

基于蟻群算法的智能交通最優(yōu)路徑研究

李松江，張異，龔躍

（長春理工大學計算機科學技術(shù)學院，長春 130022）

針對車輛智能交通最優(yōu)路徑問題，提出一種實時規(guī)劃的蟻群算法。在該算法搜索過程中加入針對具體問題的局部搜索尋優(yōu)算法，在啟發(fā)函數(shù)中引入搜索方向，改進信息素更新策略，限制信息素軌跡量。利用智能交通道路模型對改進算法進行比較分析。實驗結(jié)果表明，改進后的蟻群算法能夠有效地解決車輛實時路徑誘導問題，實現(xiàn)車輛實時路徑誘導，具有良好的收斂性和尋優(yōu)性。

蟻群算法；智能交通；最優(yōu)路徑

隨著城市化進程的不斷加快，道路運輸需求的增加顯著，城市機動車保有量的快速增長，使交通情況不斷惡化，交通事故顯著增加，人們在交通上消耗的時間和費用明顯加大［1］。交通量的快速增長已導致了許多嚴重的社會問題和交通問題。為了減緩交通擁堵，提高道路的使用，節(jié)省交通消耗，使智能交通系統(tǒng)稱為ITS（Intelligent Transport Systems），將網(wǎng)絡(luò)信息系統(tǒng)、現(xiàn)代通信技術(shù)、智能化分析系統(tǒng)、定位系統(tǒng)等綜合運用于整個道路管理系統(tǒng)的總稱［2］。智能交通最優(yōu)路徑研究能夠提供駕駛?cè)藛T實時最優(yōu)路徑，在起點與終點之間根據(jù)實時道路信息，按照蟻群算法決策出最優(yōu)路徑。

1 基本蟻群算法

1.1 蟻群算法原理

意大利研究人員Dorigo M于20世紀90年代提出的蟻群算法（ant colony optimization，ACO），通過模擬螞蟻的自然覓食行為提出的一種群集智能算法［1］。螞蟻在經(jīng)過的路徑上會留下信息素，通過這條路線的其他螞蟻可以感知信息素的多少，并選擇信息素的多的路徑。更多的螞蟻選擇信息素多的路徑，形成一個正反饋機制。基于正反饋機制，螞蟻可以找到從蟻巢到食物的最短路徑。

1.2 蟻群算法基本模型

初始時刻，信息素τij(0)在各條路徑上都是相等的。在算法搜索的過程中，螞蟻決定下一步要選擇的城市，根據(jù)城市間路徑上信息素強度和城市間距離的大?。?］。t時刻時螞蟻k從城市i到城市j的轉(zhuǎn)換概率［2］：

其中，allowedk={0,1，…，n-1}表示螞蟻k下一步可以選擇的城市。與轉(zhuǎn)移概率成正比。α和β表示螞蟻在搜索過程中啟發(fā)信息多少和積累的信息素大小。

2 建立智能交通道路模型

單個交叉路口構(gòu)成城市道路交通網(wǎng)絡(luò)，用圓圈代表交叉道路路口，用直線代表路徑，如圖1所示。交通網(wǎng)絡(luò)可以抽象成為由節(jié)點、弧段和路權(quán)組合成的有向帶權(quán)圖［3］。

圖1 道路網(wǎng)圖論模型

G=(N,S,W)表示道路網(wǎng)絡(luò)的狀態(tài)圖。G為有向圖。N={Ni，i=1，2，...，8}表示交叉路口集合，S={Si=i=1，2，...，12}表示相鄰交叉路口之間的路段，Wij={i,j|1,2,…,8}表示路段Ni到Nj的權(quán)重，是指通過Ni到Nj路段的所需代價值。

路段的權(quán)重由多個變量共同決定［3］。考慮該路段車流阻塞密度KS，路段通行能力MS和路段車輛排隊長度PS,t這3個優(yōu)化目標，則：

式（2）中：vS為路段S上車輛流密度，xS,t是路段S在t時刻的交通道路負荷，LS是路徑S的長度，rS是路段S交叉路口紅燈時長，T是紅綠燈信號周期；式（3）中：n是路徑S的車道數(shù)量，Lv為路徑S阻塞情況下的平均車距［3］，Lo為路徑S上平均車身長度；式（4）中：tg表示該交叉路口紅綠燈信號周期，to表示綠燈亮時，通過停車線的車平均時間，?是折扣系數(shù)，通常取0.9。

在實際生活中，傳統(tǒng)算法決策出的最優(yōu)路徑并不能滿足駕駛?cè)藛T的實際要求［4］。傳統(tǒng)最優(yōu)路徑中道路權(quán)值只和行車距離有關(guān)，是指車輛在起點和終點間選擇一條距離最短的路徑。最優(yōu)路徑定義為路徑長度和時間費用綜合最小的路徑，并且在算法改進研究中將道路權(quán)值由單一距離改為由車流阻塞密度、車輛通行能力和車輛排隊長度多個優(yōu)化變量共同作用［7］。

3 改進的蟻群算法

3.1 期望啟發(fā)式函數(shù)的改進

基本蟻群算法中，起點和終點連線方向的路徑是最短的路徑［8］。由兩點之間直線最短可知。啟發(fā)式因子t時刻在結(jié)點i和節(jié)點j之間距離的倒數(shù)表示：ηij(t)=1/dij。在導航路徑問題中，算法期望螞蟻選擇向著終點方向的路徑，所以改進后的期望啟發(fā)函數(shù)：

其中，dqj表示起點到終點的距離。與基本蟻群算法相比，我們改善啟發(fā)函數(shù)的搜索路徑和方向的精度，并減少了搜索時間，并在搜索算法最后接近終點的過程中不斷接近。

3.2 信息素更新策略的改進

最優(yōu)-最差螞蟻系統(tǒng)為了加大信息素在最優(yōu)路徑和最差路徑之間的大小差別［9］。對螞蟻構(gòu)造出來的最優(yōu)解進行增強，并且對最差解進行削弱［5］。更新最差路徑上的信息素，當蟻群完成每一次循環(huán)構(gòu)造出一條路徑［10］。如果邊（r，s）不是最優(yōu)路徑的邊，是最差路徑上的邊，則這條邊上的信息素更新公式如下：

其中，引入?yún)?shù)ε，在［0，1］之間；Lworst是為最差路徑長度；Lbest是最優(yōu)路徑長度；τ（r,s）表示城市r和城市s之間的信息素軌跡量大?。?］。

算法搜索集中在最優(yōu)解附近，用來加快算法的收斂速度，減少時間和費用消耗。且在計算機運行算法的過程中，加減法運算要比除法運算節(jié)省很多時間［11］。在實際路徑導航應用中，用戶對時間的要求比其他因素要嚴格，為了提高算法計算準確性并加快計算速度，將除法運算改為加減法運算。信息素如下式所示：

其中，引入?yún)?shù)σ，在［0，1］之間；Lworst是最差路徑長度；Lbest是最優(yōu)路徑長度；τ（r,s）表示城市r和城市s之間的信息素軌跡量大?。籛rs表示邊（r，s）權(quán)重［5］。

局部更新規(guī)則如下：

其中，ρ為一個參數(shù)，0＜ρ＜1。按以上公式進行一次更新每當蟻群完成一次循環(huán)構(gòu)造出一條路徑后。

3.3 信息素軌跡量限制

為了避免最優(yōu)最差螞蟻系統(tǒng)使信息素大小差異過大，出現(xiàn)算法停滯的現(xiàn)象。把信息素量范圍限制在[τmin,τmax]區(qū)間內(nèi)，以免信息素出現(xiàn)過大過小情況。限制信息素量的大小，可以提高算法性能，節(jié)省時間消耗，有效的解決算法停滯的情況。對所有的信息素軌跡τij(t)有：

問題的關(guān)鍵是選擇信息素軌跡界限。最大-最小螞蟻系統(tǒng)收斂，表示的是在選擇點上，一條路徑上的信息素軌跡量是τmax，而其他所有可以選擇的路徑上的信息素軌跡量是τmin［5］。螞蟻將一直選擇信息素軌跡量最大的路徑，直到最大最小螞蟻系統(tǒng)收斂。

3.4 狀態(tài)轉(zhuǎn)移規(guī)則的改進

蟻群愿意選擇路程較短而且存有很多信息素的路徑作為下一步前進的路徑。為了使狀態(tài)轉(zhuǎn)移規(guī)則有預見性，引入先驗知識。先驗知識是通過非感知理性獲取的知識，它的基礎(chǔ)不是感官世界，如：經(jīng)驗、概率知識，而是一種獨立于經(jīng)驗的知識，選擇路徑公式如下：

如果q≤q0按先驗知識選擇路徑（11）

其中，0＜q＜1；0＜q0＜1。參數(shù)q0用來選擇路徑，決定是按狀態(tài)轉(zhuǎn)移規(guī)則還是按先驗知識選擇路徑。隨機選取參數(shù)q，在螞蟻選擇下一步行動路徑之前。如果q大于q0根據(jù)式（1）狀態(tài)選擇規(guī)則選擇路徑，否則根據(jù)式（11）先驗知識選擇路徑。

3.5 算法步驟

第一只螞蟻依靠期望啟發(fā)函數(shù)創(chuàng)建的第一條路徑，而此條路徑通常并不能正確的反應最優(yōu)路徑的大致位置。由于改進的蟻群算法是對最差路徑上信息素進行削弱，對最優(yōu)路徑上信息素進行增強。所以在開始的幾次搜索路徑中，搜索到的最優(yōu)路徑中可能包含最差路徑的邊，而最差路徑中包含最優(yōu)路徑的邊。所以，如果在算法剛開始迭代時就增強所有最優(yōu)路徑上所有邊的信息素，減少最差路徑上所有邊的信息素，整個蟻群算法將會陷入局部最優(yōu)情況，影響智能交通最優(yōu)路徑算法的精確性和準確性。改進蟻群算法流程具體步驟：

（1）初始化。將m只螞蟻放置于起點；所有路徑的初始化信息素軌跡量為τij(0)；初始化循環(huán)次數(shù)Nc=0；初始化最大循環(huán)次數(shù)Ncmax。

（2）螞蟻構(gòu)造路徑，每只螞蟻依據(jù)表達式（11）選擇下一個結(jié)點。

（3）應用局部更新規(guī)則。螞蟻k完成一次循環(huán)路徑構(gòu)造，局部更新螞蟻k構(gòu)造的路徑上一條邊的信息素軌跡量。

（4）重復（2），（3）使所有螞蟻都完成路徑構(gòu)造。

（5）全局更新最優(yōu)路徑上的邊和最差路徑上的邊包含的信息素軌跡量和路徑長度。

（6）禁忌表數(shù)據(jù)清空，把所有螞蟻放置于起點。

（7）如果迭代次數(shù)小于Ncmax的1/4，重復步驟（2），（3），（4），（5），（6）。

（8）若果迭代次數(shù)大于或等于Ncmax的1/4，則按照式（8）對全局最差路徑和最優(yōu)路徑上的路徑信息素軌跡量進行更新。

（9）當循環(huán)次數(shù)滿足Ncmax結(jié)束，否則跳轉(zhuǎn)到（2）。

在蟻群算法開始搜索時并不進行路徑信息素全局更新，減少時間消耗，運行代價消耗，加大算法的全局搜索范圍。在經(jīng)過若干次迭代后，算法能夠確定最優(yōu)路徑的大致位置，再對路徑上的信息素軌跡量進行更新，加快蟻群算法的收斂速度。

4 仿真實驗

本次仿真實驗使用MATLABV7.0，運行在Win7系統(tǒng)上。選擇長春市吉林大路中段一段路網(wǎng)，構(gòu)建路網(wǎng)模型。圖2是選擇的長春市吉林大路中段某一道路，用節(jié)點與節(jié)點之間的線段表示各道路，用節(jié)點表示交叉路口。將長春市吉林大路中段一段路網(wǎng)抽象如圖3所示的網(wǎng)絡(luò)拓撲圖，設(shè)車輛在行駛過程中能接收實時路況信息調(diào)整規(guī)劃路徑。每條邊上的交通屬性由一個二元組（w，v）表示，表示邊上的權(quán)重和平均車速。

車輛行駛起點為N1，終點為N18。設(shè)置參數(shù)NC=10，M=50，a=1，ρ=2，p=0.3，Q=1，W= 4，q0=0.1，NC=100，M=50；a=1，β=2，p=0.3，Q=1，W=4，q0=0.1；NC=200，M=50，a=1，β= 2，p=0.3，Q=1，W=4，q0=0.1。

圖2 長春市吉林大路中段道路

圖3中路段狀況實時變化用線段加粗表示，最優(yōu)路徑用加粗線段箭頭表示。算法運行一段時間后找出初始當前最優(yōu)路徑，如圖4所示。當車輛從N1行駛到交叉路口N5時，初始最優(yōu)路徑上N5到N10的密度及延時明顯增大。此時算法進行局部更新。車輛選擇N6繼續(xù)前進。其他路徑不變，有效的提高了效率。

圖3 網(wǎng)絡(luò)格局圖

圖4 重新規(guī)劃網(wǎng)格格局圖

表1 兩種算法的性能比較

實驗結(jié)果表明，車輛最優(yōu)行駛路徑隨著路段權(quán)重的變化在不斷更新。以部分小型的道路路網(wǎng)作為實驗場景，實時規(guī)劃車輛調(diào)整行車路線。通過優(yōu)化算法性能，盡可能減少行車耗時。改進蟻群算法針對收斂速度慢和容易陷入局部最優(yōu)進行了性能方面的改進。減少算法時間上的浪費和增大運行的效率，能夠有效的避免算法過早陷入局部最優(yōu)情況。實驗結(jié)果如表1所示：改進后的蟻群算法在實時動態(tài)調(diào)整最優(yōu)解方面和在增加收斂速度、減少時間消耗方面，明顯優(yōu)于基本蟻群算法。

5 結(jié)論

本文建立了智能交通道路仿真模型，在狀態(tài)轉(zhuǎn)移規(guī)則中引入先驗知識提高搜索效率。限制信息素軌跡量范圍能夠有效的避免算法出現(xiàn)停滯。改進信息素更新策略，加入道路權(quán)值因子，實現(xiàn)實時調(diào)整最優(yōu)路徑，減少時間和性能的消耗，加快蟻群搜索速度。實現(xiàn)車輛路徑動態(tài)實時誘導根據(jù)實時信息變化，根據(jù)改進算法進行路徑重規(guī)劃。最后實驗結(jié)果表明，該算法能有效地實時解決車輛在行駛過程中動態(tài)路徑誘導問題。但是針對車輛在行駛中如何獲取實時交通訊息及算法中參數(shù)如何更合理的搭配，還有待于進一步學習和研究。

［1］Dorigo M，Maniezzo V，Colorni A，Ant system：Optimizationbyacolonyofcooperatingagents［J］. IEEE Trans.on Systems，1996，26（1）：29-41.

［2］宋方，汪鐳.改進的蟻群算法在智能交通中的應用［J］.數(shù)學的實踐與認知，2013，43（3）：67-72.

［3］文孟飛，彭軍，劉偉榮，等.一種增量式多目標優(yōu)化的智能交通路徑誘導方法［J］.湖南大學學報：自然科學版，2013，40（5）：56-60.

［4］Reimann M，Stummer M，Doerner K.A savings based ant system for the vehicle routing problem［J］.Proc.of the Genetic and Evolutionary Computation Conference，2012，32（12）：17-26.

［5］李士勇.蟻群算法及其應用［M］.哈爾濱：哈爾濱工業(yè)大學出版社，2004：82-89.

［6］吳啟迪，汪鐳.智能蟻群算法及應用［M］.上海：上海科技教育出版社，2004：56-60.

［7］Paola Pellegrini，Thomas Stutzle，Mauro Birattari.A study on max-min ant system for the TSP［J］.GermanyBerlinHeidelberg：Springer-Verlag，LNCS，2010（6234）：39-50.

［8］孫勇，李妮，龔光紅，等.基于知識庫的動態(tài)蟻群算法［J］.北京工業(yè)大學學報：自然科學版，2012，38（3）：74-80.

［9］Ugur A，Aydin D.An interactive simulation and analysis software for solving TSP using ant colony optimizationalgorithms［J］.AdvancedEngineering Software，2012，40（5）：341-349.

［10］趙飛，吳航，龔躍.蟻群算法解決網(wǎng)格環(huán)境下任務調(diào)度問題的研究［J］.長春理工大學學報：自然科學版，2013，36（2）：98-100.

［11］韓成，趙斌，白寶興，等.基于集群的蟻群算法在TSP中的應用研究［J］.長春理工大學學報：自然科學版，2008，31（4）：110-112.

The Research on the Optimal Path of Intelligent Transportation Based on Ant Colony Algorithm

LI Songjiang，ZHANG Yi，GONG Yue
（School of Computer Science and Technology，Changchun University of Science and Technology，Changchun 130022）

Aiming at the intelligent traffic optimal path ant colony algorithm convergence speed is slow and easy to fall into local optimum problem proposed an improved ant colony algorithm，in the ant colony algorithm to search in the process of join to solve the concrete problems of local search optimization algorithm.In the heuristic function introduced search party to improved pheromone update strategy，limiting pheromone quantity，the state transfer rules introducing a priori knowledge，make ant colony tendency to have high adaptive value of search space，reduce the ant colony algorithm in blind search path into local optimum and shorten the search time.The experimental results show that the improved ant colony algorithm has good convergence and optimization，and can effectively avoid the stagnation of the algorithm in the local optimal solution，which proved the effectiveness of the improved algorithm.

ant colony algorithm；intelligent transportation；optimal path

TP391

A

1672-9870（2015）04-0122-05

2015-06-30

李松江（1984-），男，博士，講師，E-mail：lsj84@outlook.com

龔躍（1960-），男，教授，博士生導師，E-mail：gongyue888878@sina.com