基于應急救援路徑規劃選擇的研究

武警警官學院信息工程系決策與指揮教研室 哈 達 劉永利 沈先耿

基于應急救援路徑規劃選擇的研究

武警警官學院信息工程系決策與指揮教研室 哈 達 劉永利 沈先耿

在突發事件發生之后,應急救援人員在規劃部署開進事發地的路線中反映出了較大的問題。針對此類情況,本文旨在研究將Dijkstra算法與層次分析法相結合,提供給救援決策者一個有效可行的路徑選擇方案,極大地提高了救援決策者在路徑選擇上的效率,從而使救援決策者能夠及時應對,妥善處置,使損失降到最低。

應急救援;路徑規劃;Dijkstra;層次分析

0 引言

當今我國在處置突發事件的過程中,應急救援隊伍雖都能在第一時間調動起來,但由于各類原因造成救援隊伍不能在第一時間到達受災地點,導致損失沒能及時控制。究其原因,不難發現,沒能選擇一條最優的路徑是造成這個被動局面的一個主要原因。所以如何選擇一條最優的路線是現在救援人員處置應急事件最需要解決的問題之一。開進路線規劃問題的研究與實現的目的就是為了解決這個問題,為今后救援人員處置應急任務時,選擇一條最優的路線提供思路及方法。

1 相關理論

Dijkstra算法是用來解決從一個起始點出發到其他各個點的最短路徑問題,主要是針對有向圖的。它解決問題的方式是從一個頂點即起始點出發,并且以這個點作為中心點,一層一層的選擇計算,最后連接到終點。它是一種具有代表性的很典型的最短路徑算法,發展較為成熟。如今,常常使用兩種表達方法,分別是永久和臨時標號方式以及OPEN,CLOSE表達方式。本文是使用第一種方式。另外Dijkstra算法還有不能有負權邊在圖中的要求。Dijkstra算法的本質是一種標號法:也就是給圖的每一個頂點記一個數,這些數被稱為這些頂點的標號,這些標號被分為臨時標號和固定標號兩種。

層次分析法(AHP)是薩蒂在上世紀70年代初在幫助美國國防部研究"根據各個工業部門對國家福利的貢獻大小而進行電力分配"課題時研究出來的。這位美國運籌學家、匹茨堡大學的教授提出的這種方法是一種在面對多目標時,用權重來分層次、以權重來排序的一種決策分析方法[3]。這種決策分析方法是將定性與定量相結合,來應對多目標的復雜問題。它是利用決策者累積的經驗也就是對事物特征的認知來確定能夠讓目標實現的要素之間的重要程度之比,是將感性認識進行定量化的過程。它給予所有決策方案的所有標準的權數,而后觀察這些權數來確定方案間的好壞,在處理那些用定量方法很難解決的問題上有很大的作用。

2 路徑選擇建模

2.1 基于Dijlstra優化算法的選擇

Dijkstra算法是找出從一個起始點到圖中任意一點的最短路徑,時間復雜度為O(n2)當其使用鄰接矩陣存儲網絡拓撲結構時,需要存儲空間為nXn。不難看出,當節點數n的增大,它所需要的存儲空間就會成倍的巨漲。這就導致存儲效率和計算效率的降低。考慮到這個情況,在查找研究了多種優化算法后,選擇了最為適合本文的研究方法。那就是:傳統的Dijkstra算法在選擇節點時重復工作過多,這就導致算法的效率降低。而選擇的優化方法就是讓算法在處理節點時是只對最短路徑上節點的相鄰點進行處理,從而不考慮到其他節點。這樣所需要的存儲空間就會減少,從而達到提高效率的目的。這樣在使用Dijkstra算法處理現實事件時,效率就會更高,就更有利于救援隊伍處理應急事件。

2.2 層次分析法最優路選擇

在處理應急事件問題時最主要考慮的問題就是找到一條最佳的路徑到達目的地。然而在現實情況里,最短不一定最優。在處理應急問題時,不能僅僅只考慮時間。還需要考慮其他影響救援的因素,比如道路的疏通程度。因此本文在用Dijkstra算法找出最短路徑后,再用層次分析法輔助決策,來確定最優路徑。思路如下:

首先要進行的是對災難等級的劃分,不同的災難程度對道路的破壞程度不同,在不同的災難情況下,救災物資的時效性、安全性、經濟性的優先等級也不相同。這里是對每段運輸路徑的破壞程度進行評定。隨著衛星地圖的發展,這些工作時可以迅速評定出來。如果衛星遭到破壞,用航拍等技術也能大致確定各條道路的破壞情況。然后根據破壞程度規劃出能夠直接使用到的道路和經過維修能夠使用的道路。這里道路的長度用時間來計算。在路況沒有受到破壞的情況下,設計時速為60km/h,對于破壞的道路等級進行劃分為不同的時速,然后加上需要維修的時間就是這路徑的長度權重。然后用Dijkstra算法找出最短路徑以及次短路徑。

然后使用層次分析法來對比最短路徑與次短路徑。根據路徑的時效性、經濟性、安全性進行評定,作為層次分析法的一個比較矩陣。最優路徑和次短路徑就是可供選擇的兩個方案,然后這兩個方案的時效性就是其上一步最短路徑算出來的時間權重,安全性指標就是對道路的破壞程度、經濟性就是需要維護道路的難度。最后對其進行層次分析法就能夠得到最優結果。

3 結束語

本文以實用的角度,從根本問題的需求出發。在研究救援隊伍現在搶險救災物資配送中遇到的實際問題,一個能夠快速選取最優路徑的方法即Dijkstra算法。為了更好的在處置突發事件時提供幫助,本文對算法的優化方式進行了選擇并找到了最好的優化方案,提高了其運算速度。然后將Dijkstra算法和層次分析法結合起來處理現實問題。該方法是針對不同的災情的實際需求和災情對路面的破壞程度做出的方法。根據需要配送到的地方的時效性、經濟性、安全性進行評定。作為層次分析法的一個成對比較矩陣。最優路徑和次短路徑就是可供選擇的兩個方案,然后這兩個方案的時效性就是其上一步最短路徑法算出來的時間權重,安全性指標就是對道路的破壞程度、經濟性就是需要維護道路的難度。然后對進行層次分析法就能夠得到最優結果。

今后對有關選擇最優路徑還可以從以下幾個方面進一步研究:(1)將數學模型與實際出現的情況相結合,如汶川、玉樹地震。研究在實際情況下是否有更加優化的路徑選擇方法解決問題。 (2)將理論實體化,設計軟件用于實現。

哈達,武警警官學院信息工程系決策與指揮教研室助教。