改進的Dijkstra算法在應(yīng)急救援最優(yōu)路徑問題中的應(yīng)用

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

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

關(guān)鍵詞：突發(fā)事件；應(yīng)急救援；最優(yōu)路徑；Dijstra算法

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

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

1 數(shù)值實例

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

2 考慮距離及道路快速通過能力的應(yīng)用

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

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

重新計算路徑權(quán)值得到如下圖2路徑權(quán)值圖：

根據(jù)權(quán)值圖可以得出權(quán)值矩陣如下：

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市） 的最短路徑經(jīng)過點V4 ， 路徑總長度（權(quán)值）為30.95 。

3 總結(jié)

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

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

參考文獻 ：

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

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

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

[4]趙惠良等.城市交通非常規(guī)突發(fā)事件的應(yīng)急資源調(diào)度最優(yōu)路徑研究[J].北京理工大學學報，2010，12（06）.

[5]劉茂.應(yīng)急資源優(yōu)化管理研究的主要問題[J].中國應(yīng)急管理， 2007.

基金項目：2015沈陽航空航天大學生創(chuàng)新創(chuàng)業(yè)訓練計劃項目 項目編號：DX504308