崔麗群，張明杰，許 堃

1.遼寧工程技術(shù)大學(xué) 軟件學(xué)院，遼寧 葫蘆島 125105

2.遼寧工程技術(shù)大學(xué) 通信學(xué)院，遼寧 葫蘆島 125105

基于改進(jìn)蟻群算法的應(yīng)急救援路線選擇

崔麗群，張明杰，許 堃

1.遼寧工程技術(shù)大學(xué) 軟件學(xué)院，遼寧 葫蘆島 125105

2.遼寧工程技術(shù)大學(xué) 通信學(xué)院，遼寧 葫蘆島 125105

1 引言

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

為此，國內(nèi)外對應(yīng)急救援路線的優(yōu)化做了大量研究。國外仿生智能優(yōu)化算法解決路徑優(yōu)化問題是一個研究熱點(diǎn)問題，蟻群算法的研究尤其突出。蟻群算法最早稱為AS（Ant System），其成功應(yīng)用于解決旅行商問題[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）受到普遍關(guān)注[5-6]。對于用蟻群算法解決應(yīng)急救援路線選擇的研究，目前還沒有成熟的理論成果。

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

2 應(yīng)急救援路線選擇的數(shù)學(xué)模型

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

2.1 影響應(yīng)急救援路線選擇的因素

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

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

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

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

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

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

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

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

按照上述原理，救援路線的選擇也就是求無向圖中節(jié)點(diǎn)到節(jié)點(diǎn)的最優(yōu)線路。因此可以將實(shí)際交通路線選擇的問題轉(zhuǎn)化為數(shù)學(xué)上的求解問題。基于蟻群算法在求解優(yōu)化問題上的優(yōu)越性，數(shù)學(xué)模型的求解應(yīng)用蟻群系統(tǒng)[13]來實(shí)現(xiàn)。

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

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

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

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

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

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

3 改進(jìn)蟻群算法對應(yīng)急救援路線選擇的過程

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

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

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

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

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

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

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

4 仿真實(shí)驗(yàn)及結(jié)果分析

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

圖1 城市交通簡化圖

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

（1）K-均值蟻群算法和改進(jìn)后算法的運(yùn)行結(jié)果

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

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

（2）實(shí)驗(yàn)結(jié)果及總結(jié)

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

圖2 K-均值算法運(yùn)行結(jié)果

圖3 改進(jìn)算法運(yùn)行結(jié)果

表1 算法結(jié)果對比

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

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

圖5 改進(jìn)算法平均時間和最短時間3次結(jié)果

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

5 結(jié)束語

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

[1]劉勇，馬欣，審志兵.基于改進(jìn)蟻群算法的應(yīng)急救援最優(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īng)急救援最優(yōu)路徑研究[D].北京：中國地質(zhì)大學(xué)，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-均值算法混合蟻群算法城市應(yīng)急救援最佳路徑?jīng)Q策[J].中國公共安全：學(xué)術(shù)版，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

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

應(yīng)急救援；蟻群算法；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.

遼寧省教育廳高等學(xué)校科研項(xiàng)目（No.2009A349）；遼寧省教育廳基金項(xiàng)目（No.2009A350）。

崔麗群（1969—），女，副教授，碩士研究生導(dǎo)師，主要研究方向?yàn)榍度胧较到y(tǒng)和軟件工程；張明杰（1987—），男，主要研究方向?yàn)榍度胧较到y(tǒng)。E-mail：zhangmj_keda@163.com

2013-01-10

2013-04-22

1002-8331（2014）23-0256-05

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