消防滅火救援最優路徑算法研究

崔傲

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

關鍵詞：消防;滅火救援;最優路徑;模型建設

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

一、消防RoboCup仿真系統與消防滅火救援路徑規劃

（一）消防RoboCup仿真系統概述

消防RoboCup仿真系統是一種多主體滅火系統，用計算機對真實的城市災難情況進行模擬，可以模擬火災中的動態和復雜信息。它由內核、監視器、地形信息、模擬器和智能體組成[2]。模擬器包括火災模擬器、交通模擬器、擁塞模擬器等。情報事項包括消防員、救援人員和執法人員。通過人工收集信息，傳感器自動提取信息，再來由仿真器、智能體完成信息交互。

（二）最優指標的選取

消防滅火救援最優路徑算法首先要解決的問題是選擇最優目標。

1.救援距離最短

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

2.救援時間最短

根據前人研究，對于運行于道路上的車輛來說，交通行程時間是主要阻抗因素。因此在緊急情況下，救援時間最短的路線對于滅火救援來說是最優的一種路線，相應的道路權重標定也是一個非常重要的問題，確定以出行時間度量的道路權重主要有以下三種方案。

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

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

方案三：引進表征路段行程時間與交通流量之間關系的路阻函數為第一要素，計算當前時段路程時間與交叉口延誤。

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

3.受約束條件

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

（三）消防滅火救援路徑規劃

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

蟻群算法是通過個體之間的信息傳遞，探索從蟻巢到食物間最短路徑的一般優化策略。在滅火救援中，蟻群算法通過獲取火災的信息來規劃到達火場的最佳路徑[5]。蟻群算法中每個螞蟻都是規劃路徑的可行方案，根據實際情況有必要通過轉移概率，以及及時更新信息素及算法關鍵詞來計算出最優路線。

可采用轉移狀態概率公式表示：

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

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

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

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

在消防路線規劃方法中，每個地圖都具有建筑物、道路、路障和庇護所等元素。在制圖中，每個元素都具有ID和其他屬性，在可通過道路的起始點和交叉點構建節點。如節點沒有相互連接說明道路阻塞，并且道路必須經過清理才能通過。從起點到目標節點，代理程序路由計劃成為上文中方案三的路由。

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

二、GIS環境下消防滅火救援最優路徑搜索的實現

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

（一）最優路徑搜索實現平臺

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

（二）最優路徑搜索的實現

1.實現算法的基本思路

用優化算法求解消防人員的最優調度方案，基本思想是通過選擇不同的菜單命令來調用不同的函數或程序。確定火災地點后，從數據分析菜單中選擇最佳路徑分析，并將事故點值傳輸到特定功能以計算最佳路徑[8]。計算出的路線結果顯示在地圖上，最后生成到達查詢單元的最佳路線。

該算法實施例包括三個模塊，即初始化模塊、計算模塊和顯示模塊。

初始化模塊：該模塊執行程序的初始工作，在工作范圍內打開圖形，設置圖形菜單命令，并計算節點表中的節點號。一旦用戶選擇了火災事故點，則從數據表中檢索火災小隊點作為起點，并從數據表中檢索火災事故點作為終點。

最佳路線計算模塊：由于該小隊位于道路網的頂部，因此無需進行判斷，只需確定火災事故現場的位置即可。然后，根據文章提出的分層空間推理方法，使用基于二進制堆棧優先級隊列的最短路徑算法來計算兩點之間的最短路徑。

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

2.最優路徑求解的模擬實例

以北京海淀區五棵松消防中隊轄區為例，到4個地點計算模擬最優路線。如圖3示，分別是到目的地終點站、火災點以及兩個模擬火災現場紅色線條即為滅火救援的最佳路徑。

三、結論

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

四、展望

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

參考文獻：

[1]龍威棟.基于網絡層次拓撲結構的公路網多目標最優路徑算法[J].西部交通科技，2019（10）：174-178.

[2]胡正華，王尚媛.基于多細節路網Voronoi層次模型的最優路徑算法[J].華南師范大學學報（自然科學版），2019，51（03）：88-93.

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

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

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

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

[7]馬慧慧，盧昱，陳興凱.兼顧帶寬和開銷的網絡最優路徑算法[J].計算機與數字工程，2018，46（11）：2201-2205+2248.

[8]臧超，孫晴晴.基于路徑狀態的可動態調節A～*路徑優化算法[J].工業控制計算機，2018，31（07）：101-102.

[9]劉雷.概率弧Petri網及其在路徑尋優中的應用[D].青島：山東科技大學，2019.