基于蟻群算法的智能交通最優路徑研究

李松江，張異，龔躍

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

基于蟻群算法的智能交通最優路徑研究

李松江，張異，龔躍

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

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

蟻群算法；智能交通；最優路徑

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

1 基本蟻群算法

1.1 蟻群算法原理

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

1.2 蟻群算法基本模型

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

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

2 建立智能交通道路模型

單個交叉路口構成城市道路交通網絡，用圓圈代表交叉道路路口，用直線代表路徑，如圖1所示。交通網絡可以抽象成為由節點、弧段和路權組合成的有向帶權圖［3］。

圖1 道路網圖論模型

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

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

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

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

3 改進的蟻群算法

3.1 期望啟發式函數的改進

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

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

3.2 信息素更新策略的改進

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

其中，引入參數ε，在［0，1］之間；Lworst是為最差路徑長度；Lbest是最優路徑長度；τ（r,s）表示城市r和城市s之間的信息素軌跡量大小［5］。

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

其中，引入參數σ，在［0，1］之間；Lworst是最差路徑長度；Lbest是最優路徑長度；τ（r,s）表示城市r和城市s之間的信息素軌跡量大小；Wrs表示邊（r，s）權重［5］。

局部更新規則如下：

其中，ρ為一個參數，0＜ρ＜1。按以上公式進行一次更新每當蟻群完成一次循環構造出一條路徑后。

3.3 信息素軌跡量限制

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

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

3.4 狀態轉移規則的改進

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

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

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

3.5 算法步驟

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

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

（2）螞蟻構造路徑，每只螞蟻依據表達式（11）選擇下一個結點。

（3）應用局部更新規則。螞蟻k完成一次循環路徑構造，局部更新螞蟻k構造的路徑上一條邊的信息素軌跡量。

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

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

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

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

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

（9）當循環次數滿足Ncmax結束，否則跳轉到（2）。

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

4 仿真實驗

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

車輛行駛起點為N1，終點為N18。設置參數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中路段狀況實時變化用線段加粗表示，最優路徑用加粗線段箭頭表示。算法運行一段時間后找出初始當前最優路徑，如圖4所示。當車輛從N1行駛到交叉路口N5時，初始最優路徑上N5到N10的密度及延時明顯增大。此時算法進行局部更新。車輛選擇N6繼續前進。其他路徑不變，有效的提高了效率。

圖3 網絡格局圖

圖4 重新規劃網格格局圖

表1 兩種算法的性能比較

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

5 結論

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

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

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

［3］文孟飛，彭軍，劉偉榮，等.一種增量式多目標優化的智能交通路徑誘導方法［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］.哈爾濱：哈爾濱工業大學出版社，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］孫勇，李妮，龔光紅，等.基于知識庫的動態蟻群算法［J］.北京工業大學學報：自然科學版，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］趙飛，吳航，龔躍.蟻群算法解決網格環境下任務調度問題的研究［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