CS算法在應(yīng)急救援中最佳路徑的應(yīng)用研究

鄭洪清

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

關(guān)鍵詞：應(yīng)急救援；布谷鳥搜索算法；最佳路徑

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

1 引言

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

2 應(yīng)急救援最佳路徑選擇的問(wèn)題描述

交通路網(wǎng)可以用一個(gè)有向圖來(lái)表示，其中節(jié)點(diǎn)集。應(yīng)急救援能否科學(xué)成功地進(jìn)行實(shí)施涉及的因素很多，比如交通的擁擠狀態(tài)、道路服務(wù)水平、車道數(shù)和天氣狀況等。應(yīng)急救援的任務(wù)是迅速到達(dá)事故發(fā)生地進(jìn)行施救，救援路徑的選擇主要考慮救援車輛的行駛時(shí)間，因此其目標(biāo)函數(shù)[3]修改為：

（1）

3 改進(jìn)的布谷鳥搜索算法

3.1 解的表示

布谷鳥搜索算法是一種連續(xù)的智能算法，標(biāo)準(zhǔn)的布谷鳥搜索算法所具有的連續(xù)編碼不能直接用來(lái)求解突發(fā)事件下應(yīng)急救援的路徑選擇問(wèn)題，因此，構(gòu)造從鳥巢位置矢量到車輛路線的合適映射是應(yīng)用布谷鳥搜索算法求解該的問(wèn)題首要工作。然而，隨機(jī)生成鳥巢位置矢量并不是一個(gè)有效的初始解，救援路線有它固有的起點(diǎn)和終點(diǎn)，而且也無(wú)須經(jīng)過(guò)每一個(gè)節(jié)點(diǎn)，所以，本文采用隨機(jī)生成鄰接點(diǎn)的方法來(lái)產(chǎn)生有效解。

4 仿真實(shí)驗(yàn)

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

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

5 結(jié)論

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

參考文獻(xiàn)：

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

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

2006.

[3]吳正偉，吉文來(lái)，陳偉佳，盧扣.地理信息與物聯(lián)網(wǎng)論壇暨江蘇省測(cè)繪學(xué)會(huì)2010學(xué)術(shù)年會(huì).

[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.

基金項(xiàng)目：廣西高?？蒲许?xiàng)目（KY2015YB539）