改進(jìn)的dijkstra算法在應(yīng)急救援最優(yōu)路徑問(wèn)題中的應(yīng)用

《改進(jìn)的dijkstra算法在應(yīng)急救援最優(yōu)路徑問(wèn)題中的應(yīng)用》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫(kù)。

1、改進(jìn)的Dijkstra算法在應(yīng)急救援最優(yōu)路徑問(wèn)題中的應(yīng)用摘要：本文目的于尋求最優(yōu)（時(shí)間最短）的資源配送路徑。建立時(shí)間最短的應(yīng)急資源調(diào)度最優(yōu)路徑選擇優(yōu)化模型，并在考慮距離的基礎(chǔ)上同時(shí)考慮快速通過(guò)的能力。采用最優(yōu)化方法進(jìn)行求解，獲得最優(yōu)方案。針對(duì)數(shù)值實(shí)例進(jìn)行仿真實(shí)驗(yàn)，并針對(duì)獲得的結(jié)果進(jìn)行分析與討論。關(guān)鍵詞：突發(fā)事件；應(yīng)急救援；最優(yōu)路徑；Dijstra算法DOI：10.16640/j.cnki.37-1222八.2017.01.126Dijkstra算法是經(jīng)典的最短路算法，是由荷蘭計(jì)算機(jī)科學(xué)家狄克斯特拉于1959年提出的，因此乂叫狄克斯特拉算法。是從一個(gè)頂點(diǎn)到

2、其余各頂點(diǎn)的最短路徑算法，解決的是有向圖中最短路徑問(wèn)題。迪杰斯特拉算法主要特點(diǎn)是以起始點(diǎn)為中心向外層層擴(kuò)展，直到擴(kuò)展到終點(diǎn)為止［1-3］。1數(shù)值實(shí)例假設(shè)J市突然發(fā)生自然災(zāi)害事件，S市派出人員及物資趕去救援，圖1為S市到J市的交通運(yùn)輸示意圖，vl為S市，v6為J市，v2、v3、v4、v5為途中主要城市。圖中兩點(diǎn)間數(shù)字代表得出的路徑權(quán)值（僅考慮距離上的最短）。2考慮距離及道路快速通過(guò)能力的應(yīng)用假設(shè)考慮道路快速通過(guò)的能力（綜合考慮道路等級(jí)、路面質(zhì)量、交通流量、車輛限制、氣象條件、實(shí)時(shí)路況等），可以用系數(shù)0.5-1區(qū)間值來(lái)表示快速通過(guò)的能力，具體難易程度如下表1

3、所示。各路徑具體系數(shù)：vl-v2系數(shù)為0.8，vl-v4系數(shù)為0.5，vl_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所示。重新計(jì)算路徑權(quán)值得到如下圖2路徑權(quán)值圖：根據(jù)權(quán)值圖可以得出權(quán)值矩陣如下：W=[010.96inf7.517.5infinf010.56.9infinfinfinf0inf15.5416.65infinf24.7109.6623.45infinfinfinf0

4、16infinfinfinfinf0]；通過(guò)matlab仿真分析，在考慮道路快速通過(guò)的能力的情況下，從起點(diǎn)vl（S市）到v6（J市）的最短路徑經(jīng)過(guò)點(diǎn)V4，路徑總長(zhǎng)度（權(quán)值）為30.95。3總結(jié)經(jīng)過(guò)MATLAB程序的計(jì)算可以得出，在路程上最短的路徑不一定是最優(yōu)的路徑，事發(fā)時(shí)的道路等級(jí)、路面質(zhì)量、交通流量、車輛限制、氣象條件、實(shí)時(shí)路況等條件對(duì)救援效率有著關(guān)鍵影響，考慮道路快速通過(guò)的能力可能得出不同的路徑，因此我們?cè)谕话l(fā)事件的應(yīng)急救援中要綜合考慮各方面因素，得出最優(yōu)路徑，不能只追求距離上的最短，有利于我們更好的進(jìn)行救援。由于時(shí)間的原因，木文主要探討的是單源最短

5、路徑問(wèn)題，在實(shí)際救援中，不可能僅僅是兩點(diǎn)之間的救援，多源點(diǎn)單目標(biāo)點(diǎn)的模型更加適合實(shí)際情況，在多源點(diǎn)的情況下，計(jì)算出來(lái)的最短路徑可能有交叉路徑。此時(shí)，不論從時(shí)間沖突上還是道路通行量上面都需要仔細(xì)平衡，如果不同源點(diǎn)的救援車輛都按照其最短路徑向受災(zāi)點(diǎn)前進(jìn)的話，很有可能造成道路交通擁擠等問(wèn)題。在表示道路快速通過(guò)能力的系數(shù)計(jì)算方法上，需要根據(jù)考慮道路等級(jí)、路妞質(zhì)量、交通流量、車輛限制、氣象條件、實(shí)時(shí)路況等條件設(shè)計(jì)出一種較為合適的計(jì)算方法［4-5］。參考文獻(xiàn)：［1］樂(lè)陽(yáng)，龔健雅.Dijkstra最短路徑算法的一種高效率實(shí)現(xiàn)［J］.武漢測(cè)繪科技大學(xué)學(xué)報(bào)，1999,24

6、(03)：219-222.［2］黃緯.基于平面圖的改進(jìn)Dijkstra算法研究［J］.江蘇大學(xué)學(xué)報(bào)(自然科學(xué)版)，2003,24(06)：70-72.［3］吳必軍，李利新，雷小平.基于城市道路數(shù)據(jù)庫(kù)的最短路徑搜索［J］.西南交通大學(xué)學(xué)報(bào)，2003，38(01)：80-83.［4］趙惠良等.城市交通非常規(guī)突發(fā)事件的應(yīng)急資源調(diào)度最優(yōu)路徑研宄［JL北京理工大學(xué)學(xué)報(bào)，2010，12(06).［5］劉茂.應(yīng)急資源優(yōu)化管理研宄的主要問(wèn)題［J］.中國(guó)應(yīng)急管理，2007.基金項(xiàng)目：2015沈陽(yáng)航空航天大學(xué)生創(chuàng)新創(chuàng)業(yè)訓(xùn)練計(jì)劃項(xiàng)目項(xiàng)目編號(hào)：DX504308