基于改進蟻群算法的高速公路疏散路徑研究

李巧茹，張 倩，陳 亮，崔 寧

(1．河北工業大學 土木工程學院，天津 300401；2．河北省土木工程技術研究中心，天津 300401)

?

基于改進蟻群算法的高速公路疏散路徑研究

李巧茹1，2，張 倩1，陳 亮1，2，崔 寧1

(1．河北工業大學 土木工程學院，天津 300401；2．河北省土木工程技術研究中心，天津 300401)

根據高速公路應急疏散的特點，在交通分配中應用改進蟻群算法模型。首先引入路段交通量和通行時間函數作為算法轉移規則的一部分，從而在進行搜索時優先考慮容量大和通行時間較短的路徑。其次通過實驗分析蟻群算法參數對計算結果和收斂速度的影響，給出了最優的參數組合。最后將最優參數組合應用于改進蟻群算法中，并通過仿真實驗將改進蟻群算法與基礎蟻群算法的路徑搜索結果進行對比。結果表明：采用最優參數組合的蟻群算法不但加快了搜索速度，而且優化了全局最優解，通過基于GIS的高速公路應急疏散系統進行路徑分析，得到系統最優的可視化疏散路徑。

交通工程；疏散路徑；蟻群算法；參數分析

0 引 言

出行者在高速公路上進行應急疏散路徑選擇時，需要根據道路的實時信息進行疏散路線判斷，采用動態路徑分析模型，并且結合合理的路徑搜索算法以最短時間進行路徑信息分析。王旭，等[1]將蟻群算法應用于路徑規劃中，通過仿真實驗比較蟻群算法和Dijksrta算法，發現蟻群算法可以較快地找到一條近似最優路徑；劉勇[2]指出人工智能算法是模擬自然界中生物為優化其生存狀態，而進行適應環境的無意識尋優行為的優化仿生算法，這類算法具有不確定性，或理解為伴有一定的隨機性，這種不確定性體現在自然界生物的生理機制，在求解某些復雜問題時優于Floyd算法和Dijksrta算法等確定型算法；徐勛倩，等[3]將蟻群算法應用于動態交通網絡的用戶均衡配流問題，但對非平衡問題沒有做相應研究；孫華燦，等[4]提出將基礎蟻群算法引入容量限制模型中，將交通分配的確定性與用戶出行的隨機性融入路徑的搜索過程，并通過實例證明其可行性。這些文獻證明了蟻群算法進行路徑分析時有較好的隨機性、適用于大規模網絡，并且對于相同規模的網絡其比傳統路徑算法用時短。

傳統蟻群算法在求解路徑優化問題中存在收斂速度慢、容易陷入局部最優路徑等不足，然而由于蟻群算法具有正反饋、分布式計算等優勢，其參數組合問題已經成為不同應用者關注的焦點[5-7]。胡耀民，等[8]通過引入信息素更新算子并改進能見度啟發因子α，改進了蟻群算法，能準確找出滿足路徑質量約束的最優路徑，但其運行速度較慢；胡啟國，等[9]通過重新設計算法的狀態轉移規則和信息素更新規則，解決了蟻群算法容易陷入局部最優解和搜索時間過長的問題，但其旨在解決最優冗余分配問題。

綜上所述，筆者針對高速公路疏散路徑問題采用路徑分配模型在基礎蟻群算法的基礎上進行局部更新和全局更新兩種信息素更新方式，并采用和分析不同的信息素揮發系數ρ，σ。以河北省高速公路調查數據為基礎，建立容量限制動態分配模型，改進路徑搜索和交通量分配算法；在基礎蟻群算法的基礎上引入了μij變量對蟻群的轉移規則進行改進，從道路的實際情況出發，進行動態信息素分配，提高算法的收斂速度。通過多組實驗數據分析改進模型中的參數最優組合，并以ArcGIS Engine、Visual Studio+C#為開發環境，搭建高速公路應急疏散系統進行疏散路徑分析。

1 基于改進蟻群算法路徑分析模型

容量限制分配是非平衡模型中的一種動態分配模型，這種分配模型在考慮路段路阻的前提下，可以通過對路徑搜尋方法以及交通量加載方法進行改進，并且在交通分配模型中將最優分配與用戶隨機分配兩種方式分配相結合。筆者在孫華燦，等[4]的研究基礎上對蟻群算法的轉移規則和信息素更新方式進行改進，以提高算法的收斂性和收斂精度。

1.1 交通路阻

在公路上出行者所花費的時間與該路段上的交通流量成正比，其時間與交通量之間的關系可表達為：

ta=f(qa)

(1)

式中：ta為通過路段a所花費的時間；qa為路段a上的交通量。

對于行駛在公路上的時間函數模型有基于交通3參數的路阻函數模型，我國學者將非機動車因素考慮進BPR函數中而提出的路阻函數模型，但是使用最為普遍的還是由美國聯邦公路局開發的路阻函數，BPR模型表達式為：

(2)

1.2 適用于路徑分析的蟻群算法

蟻群算法中的基本變量為[10]：m為蟻群中的螞蟻數量；n為交通網絡中的節點數；τij為邊(i,j)上蟻群釋放的信息軌跡強度；Δτij(t)為螞蟻在邊(i,j)上留下的單位長度的信息素含量(信息素增量)；α2為信息啟發因子，可以表示運動軌跡的重要程度，α2值越大說明螞蟻趨向于其他螞蟻所走路徑的概率越大；β2為期望啟發式因子，反映能見度的重要程度，β2值越大說明轉移概率越接近于貪心規則。

1.2.1 轉移規則的改進

在基本蟻群算法中，螞蟻根據隨機比例規則進行下一步路徑選擇，而在改進后的蟻群系統中使用的是偽隨機比例規則。第k只在某節點選擇下一個允許到達的節點j的規則如式(3)：

(3)

(4)

(5)

(6)

式中：p為螞蟻k由節點i轉移到節點j的轉移概率；q為[0,1]上均勻分布的隨機數；q0∈[0,1]，為一個參數；allowedk表示螞蟻k下一步能選擇的城市或節點，且allowedk={1,2,3, …,n}-tabuk，tabuk為螞蟻設置的禁忌表，它記錄了當前時刻螞蟻所搜索過的城市(節點)，約束螞蟻不能在此次循環中第二次訪問這些城市；dij為節點i到節點j之間的距離；tij為從節點i到節點j的行駛時間；qij為節點i到節點j之間的交通容量；μij為路阻的函數，它的引入保證了算法在路徑搜索時更傾向于通行時間短和交通容量較大的路段。

在算法的開始階段，初始化參數時，各路段的初始信息素相差不大，使得ηij和μij可以提供有助于在循環初期算法快速收斂的局部信息。在迭代進行的過程中，信息素會隨著路徑的搜索而不斷改變，這時ηij和μij在體現解信息方面的重要性在不斷提高。鑒于此，提出對ηij和μij設計一種倒指數關系曲線以體現其重要性，同時由于在算法迭代過程中行駛時間和交通量對路徑影響較大，所以在設計中μij的權重比ηij的權重相對要大一些，故而關系曲線如式(7)、式(8)：

(7)

(8)

式中：NC=1，2，…，NC_max，為當前迭代。

1.2.2 信息素更新方式的改進

由概率選擇公式可知，當在一個選擇交叉點上時，若其中一個選擇的信息素濃度高于其他選擇時，螞蟻選擇這個解的概率大，隨著循環的不斷進行，這條路徑上的信息素濃度不斷加強，則會導致螞蟻不斷地重復選擇同一條路徑而出現停滯現象。同時若是某條路徑上的信息素濃度過低對進行全局搜索也是不利的。因此根據最大-最小蟻群系統的優化思想，將信息素濃度的取值設定在[τmin, τmax]范圍內，要求每一次循環過后，信息素濃度必須符合這個限制：若τij(t)>τmax，取τij(t)=τmax；若τij(t)<τmin，則取τij(t)=τmin。對信息素濃度進行上限設置，避免在路徑搜索過程中各路段之間的信息素濃度差異過大；對信息素濃度進行下限設置，避免當某些選擇的概率非常小時信息素不至于為0，盡量降低停滯現象發生的機率。τmin和τmax的計算如式(9)、式(10)：

(9)

(10)

式中：Lnn為采用最鄰域算法求解初始路徑的最短距離。

每一次迭代完成后找出新的最優解Lgb，則τmax按式(11)更新：

(11)

考慮到在迭代不斷進行的過程中，信息素濃度的變化，將各路徑的初始值設為τmax，可以避免信息素濃度相對之間差異的不斷增加，還可以提高算法在初期的尋優能力，改善螞蟻系統求解最優值的性能。

1)在搜索過程中，若某一條道路上的信息素濃度過高，則會引起路徑算法早熟，出現局部最優的情況，因此有必要引入局部更新規則。在局部更新規則中，當螞蟻k完成某一個路段的搜索后，其所經過路段的信息素按局部更新規則更新。信息素更新規則如下：

(12)

(13)

式中：τ0為初始信息素濃度；N為路網中的節點個數；Lnn為初始最短路徑的長度；ρ為信息素局部揮發系數，取值在[0，1]之間，表示信息素揮發的快慢。

2)對信息素進行全局更新是指當所有螞蟻均完成對所有路徑搜索之后，在全局信息素更新中僅允許生成最優解的螞蟻對信息素進行釋放。公式如下：

(14)

(15)

式中：δ∈[0,1]，表示全局信息素衰減系數；R為常數；Lgb為目前迭代中找出的全局最優解。

2 模型的參數分析

由于在算法進行過程中，螞蟻在選擇下一個行駛路段時會根據信息素信息進行判斷，因此在每次實驗中只改變一個參數，其他參數不變，重復對每一組做20次試驗，然后比較所得結果的平均值，目的是消除偶然因素對算法參數的影響。根據高速公路道路網的規模，選取76個節點(最優解108 159)，在ArcGIS中讀取這些點狀物的坐標，作為算法分析的基礎數據，選定起始點和終點不變，根據經驗將初始參數設置為α2=1、ρ=0.1，δ=0.1、m=10，NC_max=5 000。筆者提出的改進算法中，大多數變量參數是隨著迭代過程中信息素、交通量、路段通行時間的變化而改變。由于沒有精確的公式進行初始設置，部分參數根據應用領域的不同而采用不同的取值，因此筆者對α2，ρ，σ，m這4個參數進行實驗分析，從而獲得參數的最優組合。

2.1 啟發因子的實驗分析

筆者對α2以0.5為間隔取10個不同的值進行結果比對。α2反映的是在算法進行過程中信息素對螞蟻進行路徑選擇的相對重要程度，而當其取值較小時，會減弱信息素對螞蟻的影響，這時螞蟻主要受啟發信息的影響，容易過早的收斂于局部最優解；當α2的取值較大時，信息素在螞蟻的移動過程中發揮主要作用，有時會淹沒啟發信息，所以此時螞蟻選擇已走過路徑的概率增大，使得算法結果變差。

圖1為算法搜索的迭代次數與全局最優解隨α2變化的趨勢。由圖1可知全局最優解以及算法的迭代次數隨著α2不斷增大呈近似線性增長的趨勢。當α2較小時，算法過早收斂，且容易陷入局部最優解；當α2較大時，收斂速度較慢，由于正反饋作用，使得全局最優解比較大。綜合考慮全局最優解及迭代次數，當α2∈[1,2]時，算法的求解性能較好，本研究取α2=1.5。

圖1 α2對算法運行結果的影響

2.2 局部信息素揮發系數的實驗分析

ρ是局部信息素揮發系數，反映某一只螞蟻完成一次循環后信息素消失的快慢，它是在某一只螞蟻完成所有節點訪問后，對該螞蟻所走過的路徑上的信息素濃度進行調整。當ρ較小時，該螞蟻所走過的路徑上信息素殘留較大，容易吸引其他螞蟻向同一條路徑行駛，使算法收斂于局部最優解；當ρ較大時，這條路徑上的信息素揮發較快，降低其中某些路段的被選中概率，使得算法收斂速度降低。

圖2為ρ的不同取值引起的迭代次數和全局最優解的變化。從圖2可知全局最優解在ρ較小或較大時比較敏感，變化趨勢較大，因此從最優解的角度取值在區間[0.15，0.5]時，算法比較穩定；若將迭代次數考慮進去，ρ=0.15比較合適。

圖2 ρ對算法運行結果的影響

2.3 全局信息素揮發系數的實驗分析

δ的取值大小對蟻群算法的全局搜索能力和收斂速度有著重要的影響，王穎，等[11]指出δ對蟻群算法的影響是具有雙重性的。當δ較小時，將使得未被搜索過的路徑上的信息軌跡強度減弱，減小算法的搜索空間，加大陷入局部最優解的可能性，反而增強收斂速度；當δ較大時，搜索過的路徑上的信息軌跡強度減弱，擴大了蟻群的搜索范圍，從而減低了算法的收斂性，但同時也減小了陷入局部最優解的可能性。

圖3是全局揮發系數對算法結果的影響。當δ值較小時，全局最優解較大，且迭代次數也較多；當δ值較大時，全局最優解呈線性增長，這說明δ的增大使得螞蟻再次選擇已搜索過路徑的可能性增大，降低了算法的隨機性和進行全局搜索路徑的能力。從圖3中可知當δ在[0.1，0.4)和(0.4,0.5]區間內算法的計算性能穩定，收斂速度和收斂性較好。而且通過對20組值進行最優解及最優解出現次數的分析，可知當δ=0.2時，算法的性能最好。

圖3 δ取值對算法運行結果的影響

2.4 螞蟻數量的參數分析

蟻群算法是從多個候選解組成的群體在不斷進化的過程中尋找到最優解的，它的優勢即為并行搜索[12]。螞蟻數目較多時，可以增強算法的全局搜索能力和其穩定性，然而當數目過多時，會出現已搜索過的路徑上的信息素濃度變化較為接近，降低算法的正反饋作用，使得收斂速度減慢；而當螞蟻數目過少時，使得已搜索和未被搜索的路徑上的信息素濃度差異較大，尤其是當路網規模較大時，將會減弱算法的全局搜索能力和隨機性，雖然可以提高算法的收斂速度，但卻導致算法穩定性變差。

圖4 m取值對算法運行結果的影響

表1 螞蟻數量m與搜索時間的關系

因此通過設定初始值對算法中的參數進行分析，可得到蟻群算法的最優組合為α2∈[1,2]，ρ∈[0.15，0.5]，δ∈[0.1，0.4)∪(0.4,0.5]，m∈ [10，40]。根據實驗對最優值與初始值進行對比，最優組合參數為：α2=1.5，ρ=0.15，δ=0.2，m=30；初始設置參數：α2=1，ρ=0.1，δ=0.1，m=10；迭代次數均為5 000。圖5是參數更新前后對算法運行結果的影響，參數更新前后的分析結果見表2。

圖5 參數更新前后對算法運行結果的影響

表2 參數更新前后的分析結果

對圖5和表2分析可知，對蟻群算法的參數采用最優組合后，不但提高了算法的收斂速度，同時也提高了全局搜索能力和算法的穩定性。因此進行路徑分析時模型參數的初始值采用最優組合參數。

3 實例分析

3.1 GIS平臺及系統設計的基本原理

ArcGIS 10.1是美國環境系統研究公司(Environmental Systems Research Institute, Inc. 簡稱ESRI)開發的地理信息系統軟件，ArcGIS Engine是一個簡單的并且可以脫離應用程序ArcObjects編程環境，是建立嵌入式GIS組件的自定義應用程序的類庫。Microsoft Visual Studio 2010是面向組件模型COM使用C#語言的一種開發工具，在Visual Studio中新建一個Windows窗體應用程序，可以添加TOCControl、ToolbarControl、MapControl、LicenseControl控件和相關引用。

高速公路應急疏散路徑分配以ArcGIS 10.1、ArcGIS Engine以及C#為分析及開發平臺。主要技術為：①根據河北省交通圖制作ArcGIS的路網矢量圖，設置路網屬性；②使用ArcCatalog構建網絡數據集，為路徑分析做準備；③使用C#語言于Visual Studio 2010軟件平臺編寫模型算法程序；④借助ArcGIS Engine進行系統設計，調用ArcGIS 10.1服務引用，實現路徑分配。

3.2 高速公路應急疏散路徑分析

選取河北省域內交通局域網作為研究對象，其中包含的高速公路與國省干線有G4京港澳高速、G18榮烏高速、G5京昆高速、S52保阜高速(保滄高速)、G107國道、S232省道、S331省道、S335省道、S334省道、S382省道、S241省道、S237省道。通過ArcGIS的網絡分析工具條，設置停靠點如圖6，假設S52上從P2點向東方向與G107之間出現單向斷交情況。根據道路的屬性信息，在界面右側設置需要進行疏散的交通量，疏散點為P1，事故點為P2，目的地為P3，然后進行分析求解。蟻群算法的參數設置見表3，路徑分配結果見圖6和表4。

表3 蟻群模型參數設置

圖6 系統分配結果顯示

表4 分配結果

3.3 蟻群算法在應急疏散路徑中的分析

取路網中節點坐標為基礎數據進行計算，比較采用最優參數組合的改進蟻群算法和基礎蟻群算法的性能。圖7是兩種蟻群算法的分析結果。

圖7 兩種蟻群算法的分析結果

對圖7進行分析可知，改進蟻群算法在迭代次數為40次與120次之間保持穩定，不再更新最優解，但在140次迭代之后再次開始全局更新直至接近160次時搜索到全局最優解，待全局最優解不再更新之后停止迭代，算法結束；而基礎蟻群算法在100次與140次循環之間保持穩定，從第160次迭代開始最短路徑長度發生微小變化之后，在第200次迭代時停止，算法結束。由此可知改進的蟻群算法節省了20次迭代所用的時間，加快了算法的運行和收斂速度。

改進蟻群算法雖在蟻群開始移動初期搜索的最短距離大于基礎蟻群，但在算法進行過程中逐漸顯示優勢，蟻群搜索的最短路徑長度出現較明顯的差異。改進蟻群算法的全局最優解的路徑比基礎蟻群全局最優解的路徑長度縮短近300 m，優化了全局最優解并且提高了收斂精度。

4 結 論

在分析高速公路路段阻抗的基礎上，從路徑分配模型參數研究入手，采用改進的蟻群算法求解交通事件發生時高速公路應急疏散路徑問題，得到如下結論：

1)采用改進的蟻群算法可以提高算法的搜索速度和收斂性，本研究引入μij函數作為螞蟻的轉移規則，可以更好的體現容量限制分配中路阻的影響作用，使螞蟻在進行下一個路段選擇時更傾向于通行時間短，交通容量大的路段，更加切合駕駛員行駛過程中的路徑選擇行為。

3)以ArcGISEngine和C#作為分析及開發平臺，設計高速公路應急疏散系統，對應急疏散路徑進行分析，實現系統可視化疏散路徑，便于出行者對疏散路徑的理解和選擇，同時方便管理者決策。

[1] 王旭,崔平遠,陳陽舟．基于蟻群算法求路徑規劃問題的新方法及仿真[J]．計算機仿真,2005,22(7):60-62.WangXu,CuiPingyuan,ChenYangzhou.Anewmethodandsimulationforpathplanningproblembasedonantcolonyalgorithm[J].ComputerSimulation,2005,22(7):60-62.

[2] 劉勇．基于蟻群算法的應急救援最優路徑研究[D]．武漢:中國地質大學,2010. Liu Yong.The Research on the Optimal Path of Emergency Rescue Based on Ant Colony Algorithm[D].Wuhan:China University of Geosciences,2010.

[3] 徐勛倩,黃衛．螞蟻算法處理動態交通網絡用戶均衡配流問題[J]．公路交通科技,2005,1(1):111-114. Xu Xunqian,Huang Wei.Ant algorithm for users equilibrium assignment model of dynamic traffic network[J].Journal of Highway and Transportation Research and Development,2005,1(1):111-114.

[4] 孫華燦,李旭宏,劉艷忠,等．容量限制分配的蟻群優化算法[J]．東南大學學報:自然科學版,2009,39(1):177-180. Sun Huacan,Li Xuhong,Liu Yanzhong,et al.Ant colony optimization arithmetic of capacity restraint traffic assignment[J].Journal of Southeast University:Natural Science,2009,39 (1):177-180.

[5] 詹士昌,徐婕,吳俊.蟻群算法中有關算法參數的最優選擇[J].科技通報,2003,19(5):381- 386. Zhang Shichang,Xu Jie,Wu Jun.The optimal selection on the parameters of the ant colony algorithm[J].Bulletin of Science and Technology,2003,19(5):381- 386.

[6] 徐紅梅,陳義保,劉加光,等.蟻群算法中參數設置的研究[J].山東理工大學學報:自然科學版,2008,22(1):7-11. Xu Hongmei,Chen Yibao,Liu Jiaguang,et al.The research on the parameters of the ant colony algorithm[J].Journal of Shandong University of Technology:Natural Science,2008,22(1):7-11.

[7] 葉志偉,鄭肇葆.蟻群算法中參數α,β,ρ設置的研究——以 TSP 問題為例[J].武漢大學學報:信息科學版,2004,29(7):597-601. Ye Zhiwei,Zheng Zhaobao.Configuration of parametersα,β,ρin ant algorithm[J].Geomatics and Information Science of Wuhan University,2004,29(7):597-601.

[8] 胡耀民,劉偉銘.基于改進型蟻群算法的最優路徑問題求解[J].華南理工大學學報:自然科學版,2010,38(10):105-110. Hu Yaomin,Liu Weiming.Solving of optimal path problem based on improved ant colony algorithm[J].Journal of South China University of Technology:Natural Science,2010,38(10):105-110.

[9] 胡啟國,胡小華,吳泳龍．改進蟻群算法在系統可靠度最優冗余分配的應用[J].重慶交通大學學報:自然科學版,2013,32(3):543-546. Hu Qiguo,Hu Xiaohua,Wu Yonglong.Application of improved ant colony algorithm in system reliability optimization of redundancy allocation[J].Journal of Chongqing Jiaotong University:Natural Science,2013,32(3):543-546.

[10] Bonabeau E,Dorigo M,Theraulaz G.Swarm Intelligence:From Natural to Artificial Systems[M].New York:Oxford University Press,1999,10-32.

[11] 王穎,謝劍英.一種自適應蟻群算法及其仿真研究[ J].系統仿真學報,2002,14(1):31-33. Wang Ying,Xie Jianying.An adaptive ant colony optimization algorithm and simulation[J].Journal of System Simulation,2002,14 (1):31-33.

[12] 覃剛力,楊家本.自適應調整信息素的蟻群算法[J].信息與控制,2002,31(3):198-201. Tan Gangli,Yang Jiaben.An improved ant colony algorithm based on adaptively adjusting pheromone [J].Information and Control,2002,31(3):198-201.

Study on Highway Evacuation Route Based on Improved Ant Colony Algorithm

Li Qiaoru1,2, Zhang Qian1, Chen Liang1,2, Cui Ning1

(1. College of Civil Engineering, Hebei University of Technology, Tianjin 300401, China; 2. Civil Engineering Technology Research Center of Hebei Province, Tianjin 300401, China)

According to the characteristics of expressway emergency evacuation, improved ant colony algorithm was applied in traffic assignment models. Firstly, the function of traffic flow and capacity was introduced as a part of the algorithm state transition rules. Consequently the paths with larger capacity and shorter travel time were chosen preferentially when searching. Secondly, the influences of ant colony algorithm parameters on calculation results and the convergence speed were studied by experimental analysis, then the optimal combination of algorithm parameters were presented accordingly. Finally, the optimal parameter combination was applied to the improved ant colony algorithm, and the searching results were compared with the basic ant colony algorithm through simulation experiments. The results show that ant colony algorithm with the optimal combination parameter has advantages in accelerating the search speed and optimizing the global optimal solution. The visual emergency evacuation paths are available through the path analysis via expressway emergency evacuation system based on GIS.

traffic engineering; evacuation route; ant colony algorithm; parametric analysis

10.3969/j.issn.1674-0696.2015.03.19

2013-11-21；

2014-03-06

河北省人力資源與社會保障廳留學人員科技活動項目(D2011001)；河北省高等學校科學技術研究重點項目(ZD2014078)

李巧茹(1972—)，女，河北石家莊人，副教授，博士，主要從事交通運輸規劃管理與控制方面的研究。E-mail：qiaoruli129@126.com。

U495

A

1674-0696(2015)03-086-07