基于改進蟻群算法的應急救援路線選擇

崔麗群，張明杰，許 堃

1.遼寧工程技術大學 軟件學院，遼寧 葫蘆島 125105

2.遼寧工程技術大學 通信學院，遼寧 葫蘆島 125105

基于改進蟻群算法的應急救援路線選擇

崔麗群，張明杰，許 堃

1.遼寧工程技術大學 軟件學院，遼寧 葫蘆島 125105

2.遼寧工程技術大學 通信學院，遼寧 葫蘆島 125105

1 引言

隨著我國經(jīng)濟的快速發(fā)展，城市規(guī)模迅速擴大，人民生活水平顯著提高，由此帶來的交通問題和社會安全問題日益突顯出來。自然災害、公共衛(wèi)生事件、生產(chǎn)安全事故和恐怖襲擊等緊急、突發(fā)事件時有發(fā)生，應急救援已成為社會生活方面不可缺少的一個部分。為實現(xiàn)快速高效的應急救援，路線的選擇問題不容回避。應急救援路線是指在當時的交通條件下，為實現(xiàn)快速高效的應急救援如何選擇交通線路的問題。應急救援最突出的要求是時間，因為面對突發(fā)事件和災害，救援人員和物質如能在最短的時間到達，才能發(fā)揮其作用，最大限度地減少災害后果[1]。

為此，國內(nèi)外對應急救援路線的優(yōu)化做了大量研究。國外仿生智能優(yōu)化算法解決路徑優(yōu)化問題是一個研究熱點問題，蟻群算法的研究尤其突出。蟻群算法最早稱為AS（Ant System），其成功應用于解決旅行商問題[2-3]。隨后又出現(xiàn)了精英策略螞蟻系統(tǒng)（Elitist Strategy Ant System，ESAS）、基于排列的螞蟻系統(tǒng)（A-ant SystemRank，ASR）、最大最小螞蟻系統(tǒng)（MAX-MIN Ant System，MMAS）[4]。1996年 Gambardella和 Dorigo提出的蟻群系統(tǒng)（Ant Colony System，ACS）受到普遍關注[5-6]。對于用蟻群算法解決應急救援路線選擇的研究，目前還沒有成熟的理論成果。

國內(nèi)關于路徑優(yōu)化問題的研究主要借鑒國外成果，理論研究已經(jīng)很成熟，但實際應用不多。國內(nèi)的蟻群算法研究始于1998年末，主要圍繞TSP（旅行商問題）及相關問題進行研究，以及應急救援路線的選擇和蟻群算法在連續(xù)系統(tǒng)的應用。本文針對蟻群算法的缺陷和應急救援路線選擇的特點，主要研究了改進蟻群算法在應急救援路線選擇中的應用，為城市應急救援路線選擇提供了有效的解決方案。

2 應急救援路線選擇的數(shù)學模型

應急救援線路的選擇[7-9]，強調(diào)的是時間，因為在越短的時間內(nèi)做出救援，挽救生命和財產(chǎn)的概率就越大。這個問題同最短路線的選擇有很大的不同，路線最短并不能代表所用時間是最少的。影響時間的因素[10]有很多，比如道路等級、路面質量、交通流量、車輛限制、氣象條件、道路實時信息等等，都對救援時間產(chǎn)生影響，在救援行動時都要考慮在內(nèi)，因此應急救援線路的選擇要考慮更多的情況，比求解最短路線有更大的復雜性。

2.1 影響應急救援路線選擇的因素

應急救援路線選擇是基于城市交通路線的[11-12]，因為相比較于鄉(xiāng)村的路線，城市交通路線有很大的復雜性，鄉(xiāng)村道路比較單一，救援相對簡單易行。鑒于城市交通的特點，影響應急救援路線選擇的因素概括為以下幾個方面。

（1）實際路線距離d。路線距離的長短，顯著的影響著路線行駛時間，對于現(xiàn)有的交通工具來說，其速度v取值波動范圍不是很大，故路線行駛時間受路線長短的制約。

（2）道路狀況θ。這里所講的道路狀況包含所有的路面情況，如道路等級、路面質量等。道路狀況分為不通（1）、凹凸土路（0.9）、窄土路（0.8）、寬土路（0.7）、窄磚路（0.6）、寬磚路（0.5）、窄水泥路（0.4）、窄柏油路（0.3）、寬水泥路（0.2）、寬柏油路（0.1）。

（3）交通狀況ω。這里的交通狀況也是包含了所有的交通信息，比如道路上交通車輛的多少、道路管制情況、交通實時信息等。交通狀況可分為阻塞不通（1）、嚴重阻塞（0.9）、車輛擁擠（0.8）、交通混亂（0.7）、人車混合（0.6）、過飽和（0.5）、車輛飽和（0.4）、車輛適中（0.3）、稍有車輛（0.2）、車輛稀少（0.1）、道路空閑（0）。

（4）實時天氣情況w。實時天氣信息對于應急救援路線的選擇也是一個比較重要的因素，實時天氣狀況分為暴雨或雪（0.8）、中雨或雪（0.6）、小雨或雪（0.4）、陰（0.2）、晴（0）。

2.2 應急救援交通網(wǎng)的數(shù)學描述

交通路線從地圖上看，是點和線的交織。對應到數(shù)學上為一無向圖G(V，E)，其中V是點的集合，E是線的集合，也就是點和線構成了無線圖。根據(jù)這一相似性，將交通路線網(wǎng)中的道路交點看成無向圖中的點，道路交點間的路線看成無向圖中的線，這樣交通網(wǎng)抽象到數(shù)學上就是一個無向圖。

城市應急救援是從一個地點到另一個地點的救援，但從一個地點到路口的那段距離是必須要走的，不管那段路線狀況如何，救援車輛必須經(jīng)過，因此，在尋求最優(yōu)路線時，這段路程可以不予考慮，直接是路口到路口間的路線選擇，在數(shù)學實現(xiàn)上，也就是求無向圖中點到點的最優(yōu)路線。

按照上述原理，救援路線的選擇也就是求無向圖中節(jié)點到節(jié)點的最優(yōu)線路。因此可以將實際交通路線選擇的問題轉化為數(shù)學上的求解問題?；谙伻核惴ㄔ谇蠼鈨?yōu)化問題上的優(yōu)越性，數(shù)學模型的求解應用蟻群系統(tǒng)[13]來實現(xiàn)。

2.3 應急救援線路選擇數(shù)學模型的建立

應急救援路線選擇的數(shù)學模型的目標函數(shù)是求城市中兩點之間用時最少的行駛路線，即TAB=min∑tij，其中i，j為所選路線上的點，A，B分別為出發(fā)點和終點。

在求出發(fā)點到達終點之間用時最少的路線時，考慮到影響應急救援選擇的因素，在進行算法循環(huán)迭代過程中，分別引入 wij、θij、ωij等“狀態(tài)參數(shù)”表示實時天氣情況、道路狀況、交通狀況等不確定因素對救援線路選擇的影響?？紤]到這些影響后，本文使用當量長度Dij來代替實際路徑長度dij：

其中 wij、θij、ωij這些影響因素系數(shù)的計算如下：設某一影響因素的影響程度的系數(shù)為β，且有該影響因素時通過i、j之間的路徑的時間為Tij，無此影響因素時通過i、j之間路徑的時間為tij，則通過此路徑時的影響因素系數(shù) β為：

假設當前路段車輛所占車道的交通流量為φ，i、j之間路段當前理想流量為?ij，當前車輛行駛速度為v，則可計算出當前i、j之間路段(dij)上的平均行車速度vij為：

那么救援路線行駛時間t為：

3 改進蟻群算法對應急救援路線選擇的過程

比較于基本蟻群算法[14]的求解步驟，改進蟻群算法求解具體的求解步驟如下：

（1）選取k個較差救援路線。根據(jù)路線已知的屬性信息，利用TOP-K排序算法輸出k個較差路線。算法模型中涉及的路線屬性有4個，分別為路線距離d、道路狀況θ、交通狀況ω以及實時天氣情況w，相關的打分函數(shù)為：

（2）算法參數(shù)的初始化。算法參數(shù)的初始化按經(jīng)驗實驗值選取，在算法模型里k個較差邊的信息素初值給予很小的數(shù)值，以區(qū)別于其他的路線。

（3）人工螞蟻的初始分布。利用應急救援路線數(shù)學模型，是求解兩點間的時間最優(yōu)路線，故螞蟻的初始分布是所有的螞蟻都位于出發(fā)點或終止點。

（5）進行信息素更新，并清空禁忌表。信息素更新分為兩部分，全局更新和局部更新，分布按下式進行，信息素更新完畢，一輪搜索結束，將禁忌表清空，為下一輪搜索做好準備。

信息素揮發(fā)因子ρ的大小直接影響著蟻群算法的全局搜索能力及其收斂速度，ρ過大會降低全局搜索能力，ρ過小會降低算法的收斂速率。信息素揮發(fā)因子ρ按下式進行更新。

（6）計算最優(yōu)路線，判斷是否滿足結束條件。如滿足結束條件，輸出最優(yōu)路線；否則，轉入第（3）步，開始新一輪的搜索。

4 仿真實驗及結果分析

用Matlab7.0在Windows XP平臺上對本文改進算法的效果進行驗證，為進一步驗證算法的有效性，同時與文獻[15]中提供的K-均值算法的結果進行了比較，文獻中的參數(shù)與本文改進的算法的參數(shù)一樣。在算法模型里k個較差邊的信息素初值給予較小的數(shù)值，具體參數(shù)設置：m=50，τ=α=β=1，ρ=0.4，γ=3，最大搜索次數(shù)為100，距離取實際值。實驗選取具有20個節(jié)點（道路交叉點）的城市交通圖進行分析，圖1表示該城市的交通簡化圖。

圖1 城市交通簡化圖

依據(jù)算法理論編寫應用程序，分別用K-均值蟻群算法和改進后的算法求解節(jié)點1到節(jié)點14的應急救援路線，并對實驗結果進行對比。

（1）K-均值蟻群算法和改進后算法的運行結果

K-均值蟻群算法運行20次所得最優(yōu)結果如圖2所示，路線為1→2→4→8→13→14，所用時間為0.415 5 h，路線長度為23.120 6 km。

改進算法運行20次所得最優(yōu)結果如圖3所示，路線為1→7→8→13→14，用時為0.414 8 h，路線長度為23.120 5 km。

（2）實驗結果及總結

通過圖2和3比較，改進的算法得到了最優(yōu)結果，K-均值蟻群算法沒有得到最優(yōu)結果。算法改進前后各自運行10次所得結果對比見表1，表中數(shù)據(jù)顯示，改進算法的尋優(yōu)能力增強，能找到全局最優(yōu)路線，而K-均值蟻群算法收斂到了局部最優(yōu)，沒有找到最優(yōu)結果。

圖2 K-均值算法運行結果

圖3 改進算法運行結果

表1 算法結果對比

對K-均值算法和改進算法分別運行3次的平均時間和最短時間的對比如圖4和5所示。K-均值算法運行3次，如圖4所示，只有1次穩(wěn)定到了最優(yōu)解，穩(wěn)定到最優(yōu)解時的迭代次數(shù)為58，其余2次都未能最終收斂到最優(yōu)路線，其波動性大，具有不穩(wěn)定性；改進后的算法3次全部穩(wěn)定到了最優(yōu)解，如圖5所示，系統(tǒng)穩(wěn)定性強，穩(wěn)定到最優(yōu)解時的最少迭代次數(shù)為15，比K-均值算法提前43次。

圖4 K-均值算法平均時間和最短時間3次結果

圖5 改進算法平均時間和最短時間3次結果

實驗結果對比研究分析，在改進后的蟻群算法求解應急救援路線在仿真實驗中，證明了改進后的算法不論在收斂速度、全局最優(yōu)，還是穩(wěn)定性方面都得到了顯著的改善，為解決實際問題提供了可行的方法和思路。但改進的算法還存在有不足之處，比如尋找全局最優(yōu)解的能力還不穩(wěn)定等，針對大規(guī)模問題的研究還沒有實驗驗證等。還有待進一步的研究和學習。

5 結束語

本文在基本蟻群算法的基礎之上，分析了其特點，在提高蟻群算法的收斂速率和算法穩(wěn)定性方面給出了改進方案，并結合現(xiàn)有的研究成果將改進后的蟻群算法應用到應急救援路線選擇問題上。提出了應急救援路線選擇的蟻群算法的數(shù)學模型，并給出了改進蟻群算法求解模型的方法和步驟。實驗驗證了該數(shù)學模型可以很好地應用到求解應急救援路線選擇問題上，能為應急救援指揮提供決策依據(jù)。本文所研究的改進蟻群算法求解應急救援路線選擇的問題取得了初步成果，但應急救援路線的選擇是一個很復雜的問題，下一步要研究的問題主要有：實時性的應急救援路線選擇的問題以及大規(guī)模的應急救援路線選擇及多個應急救援的組合問題等。

[1]劉勇，馬欣，審志兵.基于改進蟻群算法的應急救援最優(yōu)路徑選擇[J].工業(yè)安全與環(huán)保，2009，35（11）：56-57.

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

[3]Dortgo M，Gambardella L M.Ant colony system：a cooperative learning approach to the traveling salesman problem[J].IEEE Trans on Evolutionary Computation，1997，1（1）：53-56.

[4]Stutzle T，Belgium B.Max-min ant system[J].Elsevier Sci，1999，17.

[5]Dorigo M，Gambardella L M.Ant colony system：a cooperative learning approach to the traveling salesman prob-lem[J].IEEE Trans on Evolutionary Comp，1997，1（1）：53-66.

[6]Le Louarn F X，Gendreau M，Potvin J Y.GENI ants for the traveling salesman problem[J].Annals of Operations Research，2004，131（10）：187-201.

[7]Li Ziyao.Fuzzy clustering analysis of emergency rescue route[C]//2011 2nd International Conference on Artificial Intelligence and Electronic Commerce，2011：1148-1151.

[8]Li Baojie，Gu Hehe，Ji Yazhou.Selection of optimal emergency rescue route based on improved ant colony algorithm[C]//2010 18th International Conference on Geoinformatics，2010：1-4.

[9]Zhang Jie，Wang Zhiyong，Xu Weisheng，et al.Model and solution of rescue path selection in emergency[J].Application Research of Computers，2011，28（4）：1311-1314.

[10]劉勇.基于蟻群算法的應急救援最優(yōu)路徑研究[D].北京：中國地質大學，2010.

[11]Wang Qiuping，Du Yefan，Wu Jinpu.Study on traffic impedance based on grey theory[C]//The 9th International Conference of Chinese Transportation Professional，2009.

[12]Wang Qiuping，Du Yefan，Wu Jinpu.Study on the vertical optimization arrangement of nodes in comprehensive industrial pipelines[C]//International Pipelines and Trenchless Technology Conference，2009.

[13]Mullen R J，Monekosso D，Barman S，et al.A review of ant algorithms[J].Expert Systems with Application，2009，36（6）：9608-9617.

[14]吳斌，趙燕偉.蟻群算法的研究現(xiàn)狀[J].自動化儀表，2004，25（1）：1-3.

[15]喬梁，金華，李云霄，等.K-均值算法混合蟻群算法城市應急救援最佳路徑?jīng)Q策[J].中國公共安全：學術版，2011，23（2）：53-57.

CUI Liqun,ZHANG Mingjie,XU Kun

1.College of Software,Liaoning Technical University,Huludao,Liaoning 125105,China
2.College of Communication,Liaoning Technical University,Huludao,Liaoning 125105,China

The choice of emergency rescue route is related to the success or failure of emergency rescue,and it has great significance for saving lives and properties to select a reasonable and effective emergency rescue route,and it belongs to the field of combinatorial optimization.For the slow solution,poor algorithm stability,prone to premature or stagnation and other defects of ant colony algorithm and characteristics of emergency rescue route choice,this paper mainly studies the application of improved ant colony algorithm in emergency rescue route choice and provides an effective solution for city emergency rescue route choice and according to the practical application proposes mathematical model of ant colony algorithm of emergency rescue route choice.It is proved by experiments that the model which applied to solving problems of emergency rescue route choice has fast and efficient features.

emergency rescue;ant colony algorithm;Top-K sorting algorithm

應急救援路線的選擇關系到應急救援的成敗，合理有效地選擇應急救援路線對挽救生命和財產(chǎn)具有重要意義，其屬于組合優(yōu)化問題。針對蟻群算法求解速度慢、算法穩(wěn)定性差、易出現(xiàn)早熟或停滯等缺陷和應急救援路線選擇的特點，主要研究了改進蟻群算法在應急救援路線選擇中的應用并根據(jù)實際應用提出了應急救援路線選擇的蟻群算法的數(shù)學模型，為城市應急救援路線選擇提供了有效的解決方案。通過實驗證明該模型可以應用到解決應急救援路線選擇問題方面，具有快速、高效的特點。

應急救援；蟻群算法；TOP-K排序算法

A

TP301

10.3778/j.issn.1002-8331.1301-0098

CUI Liqun,ZHANG Mingjie,XU Kun.Improved ant colony algorithm for emergency rescue route choice.Computer Engineering and Applications,2014,50（23）：256-260.

遼寧省教育廳高等學?？蒲许椖浚∟o.2009A349）；遼寧省教育廳基金項目（No.2009A350）。

崔麗群（1969—），女，副教授，碩士研究生導師，主要研究方向為嵌入式系統(tǒng)和軟件工程；張明杰（1987—），男，主要研究方向為嵌入式系統(tǒng)。E-mail：zhangmj_keda@163.com

2013-01-10

2013-04-22

1002-8331（2014）23-0256-05

CNKI網(wǎng)絡優(yōu)先出版：2013-05-13,http://www.cnki.net/kcms/detail/11.2127.TP.20130513.1601.005.html