基于蟻群算法的實時最優(yōu)路徑算法

張水艦

摘要：在實時交通網(wǎng)絡(luò)中的路徑尋優(yōu)問題是ITS的關(guān)鍵問題之一。在該文中，構(gòu)建了實時交通網(wǎng)絡(luò)模型；并基于交通網(wǎng)絡(luò)的特點，提出了一種實時最優(yōu)路徑蟻群算法。仿真實驗表明，文中提出的算法能為出行車輛找到有效的實時最優(yōu)路徑。此算法的運用對改善擁堵的交通狀況有一定的積極意義。

關(guān)鍵詞：實時最優(yōu)路徑；蟻群算法；實時交通網(wǎng)絡(luò)

中圖分類號：TP391 文獻標識碼：A 文章編號：1009-3044（2017）30-0178-03

Real-time Optimal Path Algorithm Based on Ant Colony Algorithm

ZHANG Shui-jian

（Huzhou Vocational and Technical College， Huzhou 313000， China）

Abstract： The optimal path problem in real-time traffic networks is one of the key problems of ITS. In this paper， the real-time traffic network model was constructed. A real-time optimal path algorithm was proposed Based on the improved ant colony algorithm taking account of the traffic network characteristics. The results of simulation experiment show that the proposed algorithm can find an effective real-time optimal path for the travel vehicle. The application of this algorithm in intelligent transportation system may be significant to relieving the congestion situation in traffic network.

Key words： Real-time optimal path； Ant colony algorithm； Real-time traffic network

1 概述

在交通網(wǎng)絡(luò)中給出行者找到最優(yōu)出行路線，不僅能使出行者快捷地到達目的地，宏觀上還能起到調(diào)節(jié)交通流，提高整個交通系統(tǒng)的效率，從而緩解交通擁堵的作用。在實際交通網(wǎng)絡(luò)中，交通網(wǎng)絡(luò)上的交通狀況往往會隨著時間發(fā)生變化，比如在上下班高峰期某些路段比平時擁堵。城市交通網(wǎng)絡(luò)的規(guī)模越來越大的，最優(yōu)路徑問題面臨新的挑戰(zhàn)。對于復(fù)雜的實時網(wǎng)絡(luò)，傳統(tǒng)算法已不能滿足要求[1] [2]。而智能算法模型簡單，對目標函數(shù)的約束少，實踐證明在一些結(jié)構(gòu)復(fù)雜的優(yōu)化問題中表現(xiàn)出優(yōu)良的性能，可以運用智能算法來求解實時路徑尋優(yōu)問題[3-5 ]。

2 實時最優(yōu)路徑模型

2.1 實時路網(wǎng)模型

可用網(wǎng)絡(luò)模型[G：{V，E，Wet}]來表示一個實時交通網(wǎng)絡(luò)，其中，[V]為路網(wǎng)節(jié)點的集合，

[V=1，2，…，n|n為節(jié)點編號]；E為路段的集合，[E∈V×V=ei，j|i≠j， i，j∈V]；[Wet]表示路段[e]在時刻[t]的阻抗函數(shù)，以行程時間表示。交通網(wǎng)絡(luò)上的路段在不同的時間段交通狀況可能會發(fā)生變化，路段上的行程時間也會隨之發(fā)生變化，稱此類交通網(wǎng)絡(luò)為實時交通網(wǎng)絡(luò)。

4 仿真實驗分析

我們對以上所述算法進行了仿真實驗，以某一交通網(wǎng)絡(luò)作為實驗對象，選定某一時間段為研究時間區(qū)域（7：00AM-8：00AM），對研究時間區(qū)域進行離散化處理，以5分鐘為時間間隔，于是一個小時的時間區(qū)域可離散為12個時間段，每5分鐘更新一次交通信息，通過此方式模擬交通信息發(fā)布平臺更新實時交通信息，如模擬某路段發(fā)生交通堵塞，并給出堵塞可能持續(xù)的時間，如果已規(guī)劃好了的最短路徑正好經(jīng)過該路段上，則更新該路段上的信息素，并觸發(fā)誘導(dǎo)算法重新規(guī)劃路徑。

以地理信息系統(tǒng)軟件ArcGIS10.2為平臺的電子地圖數(shù)據(jù)庫為基礎(chǔ)，C#作為開發(fā)工具編程實現(xiàn)此算法。選取算法參數(shù)為： 蟻群數(shù)量[pop_size] =30，初始信息素量[τc=10]，每次迭代螞蟻留在路徑上的信息量[Q=100]，信息量殘留系統(tǒng)[ρ=0.8]，參數(shù)[α=1]，參數(shù)[β]=2。在實驗交通網(wǎng)絡(luò)上隨機選取了三組起終點，模擬交通狀況發(fā)生變化的情況下進行實時路徑求解實驗，每組計算了三次，計算結(jié)果如表1所示。實驗結(jié)果顯示本文提出算法有良好的收斂性和有很高的效率，比基本蟻群算法的求解性能有明顯的改善。

5 結(jié)論

交通網(wǎng)絡(luò)上的交通狀況是會隨時間發(fā)生變化，傳統(tǒng)最優(yōu)路徑算法不能適應(yīng)交通網(wǎng)絡(luò)的實時性。在交通網(wǎng)絡(luò)經(jīng)常發(fā)生擁堵的情況下研究實時最優(yōu)路徑問題具有十分重要的現(xiàn)實意義。本文分析研究了交通網(wǎng)絡(luò)的空間分布特性以及交通路狀的實時性，對蟻群算法適用于優(yōu)化問題的特點進行了分析，并根據(jù)交通網(wǎng)絡(luò)的特性提出了一種實時最優(yōu)路徑蟻群算法。為了評估所提出的算法的性能，文中給出了一個實驗來測試新算法，測試結(jié)果表明文中所提出的算法具有良好的收斂性和運行效率，說明新算法切實可行。

參考文獻：

[1] Dijkstra E W. A note on two problems in connection with graphs[J]. Numerische Mathematik， 1959， 1（1）：269-271.endprint

[2] Bellman E. On a routing problem[J]. Quarterly of Applied Mathematics， 1958，16（1）：87-90.

[3] 潘曉萌， 李冰. 蟻群算法優(yōu)化和路徑規(guī)劃問題的應(yīng)用研究[J]. 科技通報， 2016， 32（6）：99-103.

[4] 郭勝國， 邢丹丹. 一種改進蟻群算法在機器人路徑規(guī)劃中的應(yīng)用[J]. 科技通報， 2015， 31（12）：91-93.

[5] Fouad A， Boukhetala D， Boudjema F， Zenger K， Gao X Z. A novel global Harmony Search method Based on Ant Colony Optimisation algorithm[J]. Journal of Experimental & Theoretical Artificial Intelligence， 2016， 28（1-2）：215-238.

[6] Colorni A， Dorigo M， Maniezzo V， Trubian M. Ant system for job-shop scheduling[J]. Belgian Journal of Operations Research， Statistics and Computer Science， 1994， 34（1）：39-53.

[7] Dorigo M， Maniezzo V， Colorni A. Ant system： optimization by a colony of cooperating agents[J]. IEEE Transactions on Systems， Man， and Cybernetics， Part B （Cybernetics）， 1996， 26（1）：29-41.

[8] Dorigo M， Birattari M， Stutzle T. Ant colony optimization[J]. IEEE computational intelligence magazine， 2006， 1（4）：28-39.endprint