消防滅火救援最優(yōu)路徑算法研究

崔傲

摘要：消防救援最優(yōu)路徑算法是一種提高救援資源分配效率的方法。新時(shí)代科學(xué)技術(shù)飛速發(fā)展，使得消防隊(duì)在開展消防和救援工作中獲得了技術(shù)支持。然而根據(jù)目前的情況，尚未實(shí)現(xiàn)在消防隊(duì)中使用信息技術(shù)進(jìn)行實(shí)際演練，因此信息技術(shù)在消防隊(duì)的實(shí)戰(zhàn)過程中的作用尚未得到充分發(fā)揮。此外收集的可用信息和統(tǒng)計(jì)信息并不多。文章研究討論基于消防RoboCup仿真系統(tǒng)路徑規(guī)劃系統(tǒng)中的蟻群算法，簡要討論競爭算法的過程。最后，尋求一種最優(yōu)的火災(zāi)救援路徑算法。為提高滅火救援工作的效率以及最優(yōu)算路徑算法應(yīng)用提供參考。

關(guān)鍵詞：消防;滅火救援;最優(yōu)路徑;模型建設(shè)

火災(zāi)是常見的災(zāi)難，《中國火災(zāi)年鑒》表明，進(jìn)入新世紀(jì)以來的十年中，中國大火的發(fā)生率一直很高，嚴(yán)重威脅社會公共安全和國家人民財(cái)產(chǎn)安全。消防是公共安全和社會安全的重中之重?；馂?zāi)初期和火災(zāi)發(fā)展期是滅火的黃金時(shí)期。進(jìn)入猛烈燃燒階段后，撲滅火焰的難度成倍增加。消防救援是一場與時(shí)間的競賽。現(xiàn)階段，我國的城市消防建設(shè)并不完善，消防車道亂占亂停，應(yīng)急通道亂擺亂放等現(xiàn)象普遍存在。再加上城市交通不斷發(fā)展，車輛增多，都為消防救援人員快速調(diào)動造成一定苦難[1]。滅火救援最重要的是人員快速出動，攜帶消防裝備第一時(shí)間趕到滅后救援現(xiàn)場。消防滅火救援最優(yōu)路徑的研究，從小的方面講可以提高消防人員和車輛第一時(shí)間趕往現(xiàn)場參與滅火救援行動的效率;從大的方面來看，可以優(yōu)化城市消防建設(shè)以及消防資源。文章基于消防RoboCup仿真系統(tǒng)，研究消防滅火救援的最優(yōu)路徑算法。

一、消防RoboCup仿真系統(tǒng)與消防滅火救援路徑規(guī)劃

（一）消防RoboCup仿真系統(tǒng)概述

消防RoboCup仿真系統(tǒng)是一種多主體滅火系統(tǒng)，用計(jì)算機(jī)對真實(shí)的城市災(zāi)難情況進(jìn)行模擬，可以模擬火災(zāi)中的動態(tài)和復(fù)雜信息。它由內(nèi)核、監(jiān)視器、地形信息、模擬器和智能體組成[2]。模擬器包括火災(zāi)模擬器、交通模擬器、擁塞模擬器等。情報(bào)事項(xiàng)包括消防員、救援人員和執(zhí)法人員。通過人工收集信息，傳感器自動提取信息，再來由仿真器、智能體完成信息交互。

（二）最優(yōu)指標(biāo)的選取

消防滅火救援最優(yōu)路徑算法首先要解決的問題是選擇最優(yōu)目標(biāo)。

1.救援距離最短

直接將出行距離最短選為最優(yōu)目標(biāo)，則可選取路段長度作為道路權(quán)重，這樣最為簡單直觀。但是該方案只適用于暢通度極佳的路網(wǎng)，一旦路網(wǎng)不夠暢通，節(jié)點(diǎn)與可選擇路線較少、繞行路線遠(yuǎn)的路網(wǎng)，實(shí)用性較差[3]。隨著時(shí)代發(fā)展，交通復(fù)雜，路網(wǎng)密度大，道路擁堵，路網(wǎng)中里程近似路線較多，相比之下，救援距離最短參考價(jià)值與實(shí)際意義相對較小[3]。

2.救援時(shí)間最短

根據(jù)前人研究，對于運(yùn)行于道路上的車輛來說，交通行程時(shí)間是主要阻抗因素。因此在緊急情況下，救援時(shí)間最短的路線對于滅火救援來說是最優(yōu)的一種路線，相應(yīng)的道路權(quán)重標(biāo)定也是一個(gè)非常重要的問題，確定以出行時(shí)間度量的道路權(quán)重主要有以下三種方案。

方案一：選取車輛通過某一路段的平均行程時(shí)間作為第一要素，該方案較為簡單，不能較好地反映現(xiàn)實(shí)實(shí)際情況，但具有一定參考價(jià)值。平均行程時(shí)間可根據(jù)如下方式計(jì)算：路段的平均行程時(shí)間=路段長度/設(shè)計(jì)車速

方案二：完全以實(shí)時(shí)的路段行程時(shí)間為第一要素，對于實(shí)際效果而言，是最理想的方案，但無法大范圍實(shí)施。

方案三：引進(jìn)表征路段行程時(shí)間與交通流量之間關(guān)系的路阻函數(shù)為第一要素，計(jì)算當(dāng)前時(shí)段路程時(shí)間與交叉口延誤。

所以方案三為目前最可取的方案。

3.受約束條件

當(dāng)前，路線規(guī)劃中使用的主要算法是蟻群算法。對于一個(gè)城市來說，它的地理信息是已知的，因此應(yīng)注意，路線圖信息中的緊急情況可能會引起信息變化，例如地震災(zāi)害/山體滑坡等。在進(jìn)行具體分析時(shí)，也應(yīng)考慮到這一因素，尤其是在地震和山體滑坡頻繁的地區(qū)或國家，例如日本，那里的地震往往與火災(zāi)密切相關(guān)[4]。

（三）消防滅火救援路徑規(guī)劃

目前蟻群算法廣泛應(yīng)用于路徑規(guī)劃。某一地點(diǎn)地理信息可以查詢到，但是路線圖信息中的緊急情況可能會引起信息變化，如地震、泥石流等。具體分析時(shí)應(yīng)考慮到這方面因素，并且災(zāi)害的發(fā)生可能會引發(fā)火災(zāi)。

蟻群算法是通過個(gè)體之間的信息傳遞，探索從蟻巢到食物間最短路徑的一般優(yōu)化策略。在滅火救援中，蟻群算法通過獲取火災(zāi)的信息來規(guī)劃到達(dá)火場的最佳路徑[5]。蟻群算法中每個(gè)螞蟻都是規(guī)劃路徑的可行方案，根據(jù)實(shí)際情況有必要通過轉(zhuǎn)移概率，以及及時(shí)更新信息素及算法關(guān)鍵詞來計(jì)算出最優(yōu)路線。

可采用轉(zhuǎn)移狀態(tài)概率公式表示：

，其它=0。? ? ?（1）

當(dāng)β=0時(shí)，螞蟻AK的下一個(gè)路徑選擇不受啟發(fā)式信息素影響，依賴信息素弄孤獨(dú)，因此蟻群就能更快地聚集。一段時(shí)間后，蟻群完成了從起點(diǎn)到路徑的收縮，在到達(dá)目標(biāo)點(diǎn)時(shí)更新了每條路徑上的信息素濃度。ρ表示蟻群在路徑上留下的信息素濃度蒸發(fā)的恢復(fù)程度。為防止局部收斂過早，每次收縮都需要N來完成，每條路徑的信息素濃度在T+N處為[6]：

Tij（t+n）=（1-ρ）×Tij（t）+ΔTij? ? ? ? ? ? （2）

ΔTij==1Δ? ? ? ? ? ? ? ? ? ? ? ? ? ?（3）

在消防路線規(guī)劃方法中，每個(gè)地圖都具有建筑物、道路、路障和庇護(hù)所等元素。在制圖中，每個(gè)元素都具有ID和其他屬性，在可通過道路的起始點(diǎn)和交叉點(diǎn)構(gòu)建節(jié)點(diǎn)。如節(jié)點(diǎn)沒有相互連接說明道路阻塞，并且道路必須經(jīng)過清理才能通過。從起點(diǎn)到目標(biāo)節(jié)點(diǎn)，代理程序路由計(jì)劃成為上文中方案三的路由。

初始化參數(shù)α，β，ρQ→游戲圖節(jié)點(diǎn)的連接圖，代理起始點(diǎn)和目標(biāo)點(diǎn)→螞蟻開始釋放量米，馬克K=1→antK計(jì)算其狀態(tài)轉(zhuǎn)移概率j根據(jù)公式（1），選擇下一個(gè)移動路徑節(jié)點(diǎn)→antK修改自己的路徑表K=K>mK+1→所有螞蟻嗎？如果是，向下一步→計(jì)算總距離Sk，根據(jù)路徑表記錄方案并保存在P中→根據(jù)式（2）更新信息集中度→結(jié)束;如果沒有，則到起點(diǎn)標(biāo)記antK重新選擇路徑;是=〉下一步→輸出最優(yōu)方案→結(jié)束。根據(jù)消防RoboCup仿真系統(tǒng)，隨機(jī)選5個(gè)游戲圖，模擬訓(xùn)練用蟻群算法模擬14條路徑，74min為最短路徑所需時(shí)間，106min為最長路徑所需時(shí)間。

二、GIS環(huán)境下消防滅火救援最優(yōu)路徑搜索的實(shí)現(xiàn)

在上一部分中，我們研究了最優(yōu)路線算法，建立電子地圖。在本章中，第一部分將通過計(jì)算機(jī)進(jìn)行組合和模擬。算法仿真的目的是在收到火災(zāi)警報(bào)后在地圖上選擇一個(gè)單元的位置，然后自動生成從消防隊(duì)到火災(zāi)事故現(xiàn)場的最佳路線并將其顯示在地圖上[7]。

（一）最優(yōu)路徑搜索實(shí)現(xiàn)平臺

最佳消防救援路線查找模塊是“基于GIS的城市消防指揮與決策系統(tǒng)”的重要組成部分。算法過程使用MapBasic語言編譯，運(yùn)行平臺為MaplinfoV12。系統(tǒng)啟動后的主界面如圖1所示，運(yùn)行設(shè)置如圖2所示。

（二）最優(yōu)路徑搜索的實(shí)現(xiàn)

1.實(shí)現(xiàn)算法的基本思路

用優(yōu)化算法求解消防人員的最優(yōu)調(diào)度方案，基本思想是通過選擇不同的菜單命令來調(diào)用不同的函數(shù)或程序。確定火災(zāi)地點(diǎn)后，從數(shù)據(jù)分析菜單中選擇最佳路徑分析，并將事故點(diǎn)值傳輸?shù)教囟üδ芤杂?jì)算最佳路徑[8]。計(jì)算出的路線結(jié)果顯示在地圖上，最后生成到達(dá)查詢單元的最佳路線。

該算法實(shí)施例包括三個(gè)模塊，即初始化模塊、計(jì)算模塊和顯示模塊。

初始化模塊：該模塊執(zhí)行程序的初始工作，在工作范圍內(nèi)打開圖形，設(shè)置圖形菜單命令，并計(jì)算節(jié)點(diǎn)表中的節(jié)點(diǎn)號。一旦用戶選擇了火災(zāi)事故點(diǎn)，則從數(shù)據(jù)表中檢索火災(zāi)小隊(duì)點(diǎn)作為起點(diǎn)，并從數(shù)據(jù)表中檢索火災(zāi)事故點(diǎn)作為終點(diǎn)。

最佳路線計(jì)算模塊：由于該小隊(duì)位于道路網(wǎng)的頂部，因此無需進(jìn)行判斷，只需確定火災(zāi)事故現(xiàn)場的位置即可。然后，根據(jù)文章提出的分層空間推理方法，使用基于二進(jìn)制堆棧優(yōu)先級隊(duì)列的最短路徑算法來計(jì)算兩點(diǎn)之間的最短路徑。

顯示模塊：一旦計(jì)算出最佳路線，工作人員只能通過顯示器知道如何對最佳路線進(jìn)行編程，因此需要顯示模塊在地圖上顯示計(jì)算出的路線[8-9]。

2.最優(yōu)路徑求解的模擬實(shí)例

以北京海淀區(qū)五棵松消防中隊(duì)轄區(qū)為例，到4個(gè)地點(diǎn)計(jì)算模擬最優(yōu)路線。如圖3示，分別是到目的地終點(diǎn)站、火災(zāi)點(diǎn)以及兩個(gè)模擬火災(zāi)現(xiàn)場紅色線條即為滅火救援的最佳路徑。

三、結(jié)論

計(jì)算尋找滅火救援最優(yōu)路徑是提高消防滅火救援效率的科學(xué)管理策略。相關(guān)消防人員必須掌握相關(guān)的理論知識，努力提高自身的業(yè)務(wù)水平，并運(yùn)用國內(nèi)外先進(jìn)的公共安全管理策略進(jìn)行實(shí)踐和積累經(jīng)驗(yàn)。同時(shí)，應(yīng)該指出的是，關(guān)于火災(zāi)最優(yōu)軌跡算法的研究不僅是一個(gè)純粹的數(shù)學(xué)問題，而且是城市市政管理、公共資源社會管理、消防資源管理領(lǐng)域的綜合性工作。消防工作人員研究算法時(shí)，必須考慮好科學(xué)性與可行性，合理運(yùn)用建立的數(shù)學(xué)模型并用計(jì)算機(jī)軟件進(jìn)行運(yùn)算，為滅火救援提供合理有效依據(jù)。

四、展望

前文提到在消防RoboCup仿真系統(tǒng)運(yùn)用蟻群算法的路線規(guī)劃，僅討論了游戲地圖的簡單仿真結(jié)果。實(shí)際上，路徑優(yōu)化算法很少用于指導(dǎo)實(shí)踐。在屏幕上，有許多因素會影響路線選擇，并且可以提供給消防相關(guān)工作人員的信息有限。交通狀況信息也在不斷更新，消防滅火救援現(xiàn)場情況不斷變化等一些因素限制算法應(yīng)用。例如，高層建筑和居民區(qū)的滅火計(jì)劃的改變，起始點(diǎn)的設(shè)置很容易受到主觀因素的影響。隨著航空設(shè)備的增加，消防救援的優(yōu)化必須考慮空中交通狀況，這使得優(yōu)化算法更加復(fù)雜。除了蟻群算法，還可以使用BFS、Dijkstar和MST等算法來優(yōu)化路線。近年來，神經(jīng)網(wǎng)絡(luò)也已被用于路徑規(guī)劃研究中[9]。然而，在規(guī)劃滅火救援路線時(shí)，要考慮地理信息以及相關(guān)指標(biāo)。滅火救援最優(yōu)路徑的規(guī)劃需要非常高的效率，若效率低，即便是規(guī)劃出最優(yōu)路徑，可能無法滿足消防救援的需求，救援時(shí)間爭分奪秒，一分一秒都可能影響到滅火救援戰(zhàn)斗。此外，交通信息也會隨時(shí)變化，例如形成新的交通擁堵，使計(jì)算出的路線直接不可用。

參考文獻(xiàn)：

[1]龍威棟.基于網(wǎng)絡(luò)層次拓?fù)浣Y(jié)構(gòu)的公路網(wǎng)多目標(biāo)最優(yōu)路徑算法[J].西部交通科技，2019（10）：174-178.

[2]胡正華，王尚媛.基于多細(xì)節(jié)路網(wǎng)Voronoi層次模型的最優(yōu)路徑算法[J].華南師范大學(xué)學(xué)報(bào)（自然科學(xué)版），2019，51（03）：88-93.

[3]魏新宇.消防滅火救援最優(yōu)路徑算法研究[D].西安：西安科技大學(xué)，2006.

[4]梁青格.基于SDN多粒度光交換體系的負(fù)載均衡最優(yōu)路徑算法研究[D].秦皇島：燕山大學(xué)，2019.

[5]李波.消防滅火救援最優(yōu)路徑算法研究[J].科技展望，2016，26（36）：276.

[6]張宏利.基于Dijkstra算法的礦井突水應(yīng)急救援人員疏散路徑選擇[J].內(nèi)蒙古煤炭經(jīng)濟(jì)，2019（03）：102-103+109.

[7]馬慧慧，盧昱，陳興凱.兼顧帶寬和開銷的網(wǎng)絡(luò)最優(yōu)路徑算法[J].計(jì)算機(jī)與數(shù)字工程，2018，46（11）：2201-2205+2248.

[8]臧超，孫晴晴.基于路徑狀態(tài)的可動態(tài)調(diào)節(jié)A～*路徑優(yōu)化算法[J].工業(yè)控制計(jì)算機(jī)，2018，31（07）：101-102.

[9]劉雷.概率弧Petri網(wǎng)及其在路徑尋優(yōu)中的應(yīng)用[D].青島：山東科技大學(xué)，2019.