改進的Dijkstra算法在應急救援最優路徑問題中的應用

曹舒淮 王瀟 姜浩然 梁宵 曲芳

摘 要：本文目的于尋求最優（時間最短）的資源配送路徑。建立時間最短的應急資源調度最優路徑選擇優化模型，并在考慮距離的基礎上同時考慮快速通過的能力。采用最優化方法進行求解，獲得最優方案。針對數值實例進行仿真實驗，并針對獲得的結果進行分析與討論。

關鍵詞：突發事件；應急救援；最優路徑；Dijstra算法

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

Dijkstra算法是經典的最短路算法，是由荷蘭計算機科學家狄克斯特拉于1959 年提出的，因此又叫狄克斯特拉算法。是從一個頂點到其余各頂點的最短路徑算法，解決的是有向圖中最短路徑問題。迪杰斯特拉算法主要特點是以起始點為中心向外層層擴展，直到擴展到終點為止[1-3]。

1 數值實例

假設J市突然發生自然災害事件，S市派出人員及物資趕去救援，圖1為S市到J市的交通運輸示意圖，v1為S市，v6為J市，v2、v3、v4、v5為途中主要城市。圖中兩點間數字代表得出的路徑權值（僅考慮距離上的最短）。

2 考慮距離及道路快速通過能力的應用

假設考慮道路快速通過的能力（綜合考慮道路等級、路面質量、交通流量、車輛限制、氣象條件、實時路況等），可以用系數0.5-1區間值來表示快速通過的能力，具體難易程度如下表1所示。

各路徑具體系數：v1-v2系數為0.8，v1-v4系數為0.5，v1-v5系數為0.5，v2-v3系數為0.7，v2-v4系數為0.5，v3-v6系數為0.9，v3-v5系數為0.6，v4-v3系數為0.7，v4-v5系數0.6，v4-v6系數為0.7，v5-v6系數為0.8，得到如下表2所示。

重新計算路徑權值得到如下圖2路徑權值圖：

根據權值圖可以得出權值矩陣如下：

W=[0 10.96 inf 7.5 17.5 inf

inf 0 10.5 6.9 inf inf

inf inf 0 inf 15.54 16.65

inf inf 24.71 0 9.66 23.45

inf inf inf inf 0 16

inf inf inf inf inf 0]；

通過matlab仿真分析，在考慮道路快速通過的能力的情況下，從起點v1（S市） 到v6（J市） 的最短路徑經過點V4 ， 路徑總長度（權值）為30.95 。

3 總結

經過MATLAB程序的計算可以得出，在路程上最短的路徑不一定是最優的路徑，事發時的道路等級、路面質量、交通流量、車輛限制、氣象條件、實時路況等條件對救援效率有著關鍵影響，考慮道路快速通過的能力可能得出不同的路徑，因此我們在突發事件的應急救援中要綜合考慮各方面因素，得出最優路徑，不能只追求距離上的最短，有利于我們更好的進行救援。

由于時間的原因，本文主要探討的是單源最短路徑問題，在實際救援中，不可能僅僅是兩點之間的救援，多源點單目標點的模型更加適合實際情況，在多源點的情況下，計算出來的最短路徑可能有交叉路徑。此時，不論從時間沖突上還是道路通行量上面都需要仔細平衡，如果不同源點的救援車輛都按照其最短路徑向受災點前進的話，很有可能造成道路交通擁擠等問題。在表示道路快速通過能力的系數計算方法上，需要根據考慮道路等級、路面質量、交通流量、車輛限制、氣象條件、實時路況等條件設計出一種較為合適的計算方法[4-5]。

參考文獻 ：

[1]樂陽，龔健雅.Dijkstra 最短路徑算法的一種高效率實現[J].武漢測繪科技大學學報，1999，24（03）：219-222.

[2]黃緯.基于平面圖的改進Dijkstra算法研究[J].江蘇大學學報（自然科學版），2003，24（06）：70-72.

[3]吳必軍，李利新，雷小平.基于城市道路數據庫的最短路徑搜索[J].西南交通大學學報，2003，38（01）：80-83.

[4]趙惠良等.城市交通非常規突發事件的應急資源調度最優路徑研究[J].北京理工大學學報，2010，12（06）.

[5]劉茂.應急資源優化管理研究的主要問題[J].中國應急管理， 2007.

基金項目：2015沈陽航空航天大學生創新創業訓練計劃項目 項目編號：DX504308