CS算法在應急救援中最佳路徑的應用研究

鄭洪清

摘 要：應急救援中時間是關鍵，而最佳路徑的選擇直接影響救援時間。本文在分析影響應急救援的基本因素上，利用隨機生成鄰接點的編碼方式，將布谷鳥搜索算法應用于應急救援路徑優化問題。仿真實驗表明該方法大大提高了算法的收斂速度和解的質量，為應急指揮中心決策提供了可靠的方法。

關鍵詞：應急救援；布谷鳥搜索算法；最佳路徑

DOI：10.16640/j.cnki.37-1222/t.2018.15.213

1 引言

近幾年來，自然災害頻發，在災后，時間就是生命，如何在第一時間到達救災點進行施救，最佳路路徑的選擇起著至關重要的作用，它可以最大限度的挽救人的生命和財產。突發事件發生以后，決策人員必須尋求源點到目標點的最佳救援路徑，而現代交通的發達也給最佳路徑的選擇帶來困難。因此對它的研究有著重要的理論和實踐意義。目前國內外在這方面的研究文獻不多，最短路徑算法有Dijkstra算法[1]、蟻群算法[2]等算法。各算法有各自的優缺點，譬如Dijkstra算法針對大規模的問題它的運算時間呈指數級增長，而各種仿生智能算法可以快速得到最優解，由于其是一種隨機算法，收斂速度慢，解的精確度不高。本文在前人的基礎上對影響應急救援的因素進行分析，利用布谷鳥搜索算法（cuckoo search algorithm，CS）進行求解，設計隨機生成鄰接點的方法產生有效解，大大提高了算法的收斂速度。求得的最佳路徑可以為應急救援指揮中心的決策提供有效支持。

2 應急救援最佳路徑選擇的問題描述

交通路網可以用一個有向圖來表示，其中節點集。應急救援能否科學成功地進行實施涉及的因素很多，比如交通的擁擠狀態、道路服務水平、車道數和天氣狀況等。應急救援的任務是迅速到達事故發生地進行施救，救援路徑的選擇主要考慮救援車輛的行駛時間，因此其目標函數[3]修改為：

（1）

3 改進的布谷鳥搜索算法

3.1 解的表示

布谷鳥搜索算法是一種連續的智能算法，標準的布谷鳥搜索算法所具有的連續編碼不能直接用來求解突發事件下應急救援的路徑選擇問題，因此，構造從鳥巢位置矢量到車輛路線的合適映射是應用布谷鳥搜索算法求解該的問題首要工作。然而，隨機生成鳥巢位置矢量并不是一個有效的初始解，救援路線有它固有的起點和終點，而且也無須經過每一個節點，所以，本文采用隨機生成鄰接點的方法來產生有效解。

4 仿真實驗

某地區交通簡化示意圖如圖1所示，其節點坐標如表2所示，交通道路信息如表1所示。設節點1為消防救援隊伍的出發點，節點5為醫療隊伍的出發點，節點9為事故發生點，此時天氣晴朗。為了檢測所提出算法的性能，實例運行在處理器為Celeron（R）雙核CPU T3100， 1.90GHZ 、內存為2G的PC上，以Matlab R2010a編寫代碼。參數設置為：種群規模25，總迭代次數為50；（1）式計算公式中、a和b分別取值2、4和0.01；路面狀況服務等級，由一級到四級分別賦值為（0.25、0.5、0.75、1）。編程實現改進后的布谷鳥搜索算法，得出如圖2所示最佳路徑選擇的結果，其中的藍色線表示消防隊伍救援的路線圖，紅線表示醫療隊伍救援的路線圖。

由圖2可以看出消防救援的最佳路徑為：1→7→2→ 3→9；其距離為：22.9km，行程時間為：1.8619h，并未選擇距離較短這條路線：1→2→3→9；醫療救援的最佳路徑為：5→7→2→3→9。其距離為：24.4km，行程時間為：1.9759h；也未選擇距離較短這條路線5→6→8→9。實驗結果表明算法的有效性，最短路徑不一定是最佳路徑。

5 結論

本文研究了應急救援最佳路徑選擇問題，綜合考慮了實際交通路網中影響救援車輛行駛的時間，并設計隨機生成鄰接點的方法來產生有效解，將改進后的布谷鳥搜索算法引入最佳路徑搜索中。仿真實驗表明所提出的算法大大提高了收斂速度和解的質量，為政府決策部門提供有效支持，為災后救援爭取更多的時間，提高救援效率，從而減小災后對人們生命財產的損失。由于影響救援車輛行駛的因素很多，如何建立一個合理的模型，開發一款應用軟件供決策人員使用，將是下一步研究的方向。

參考文獻：

[1]Liang Dai.Fast Shortest Path Algorithm for Road Network and Implementation[R].COMP4905.Carlenton：Carletion University School of Computer Science，2005.

[2]高尚，楊靜宇.群智能算法及應用[M].北京：中國水利出版社，

2006.

[3]吳正偉，吉文來，陳偉佳，盧扣.地理信息與物聯網論壇暨江蘇省測繪學會2010學術年會.

[4]YANG X S，DEB S.Cuckoo search via Levy flights[C]// proceedings of World Congress on nature & Biologically Inspired Computing，India：IEEE Publications，2009：210-214.

基金項目：廣西高校科研項目（KY2015YB539）