基于改進(jìn)Dijkstra算法的燃?xì)鈶?yīng)急模擬演練研究

談亦豪 王亞慧

摘 要： 針對燃?xì)馔话l(fā)事件應(yīng)急處置中，應(yīng)急處置人員需第一時間到達(dá)現(xiàn)場，城市道路最短路徑搜索則是應(yīng)急處置人員第一時間到達(dá)現(xiàn)場的關(guān)鍵，但考慮到實際路況較為復(fù)雜，若只提供一條最優(yōu)路徑，可能會因為臨時交通管制等其他因素造成該條路段無法通行。通過引入時間權(quán)值及鄰接矩陣及改進(jìn)的Dijkstra算法進(jìn)行最優(yōu)路徑搜索，為應(yīng)急處置人員提供多條最短路徑，并使用Anylogic軟件對燃?xì)馔话l(fā)事件泄漏事故應(yīng)急處置情況進(jìn)行模擬仿真，驗證了Anylogic軟件在燃?xì)馔话l(fā)事件應(yīng)急處置仿真評估應(yīng)用的可行性。

關(guān)鍵詞： 燃?xì)馔话l(fā)事件； 應(yīng)急處置； Dijkstra算法； 最優(yōu)路徑； Anylogic； 時間權(quán)值； 鄰接矩陣

中圖分類號： TN913.1?34 文獻(xiàn)標(biāo)識碼： A 文章編號： 1004?373X（2018）20?0018?06

Abstract： During the emergency disposal of the gas emergency incident， the emergency disposal personnel need to arrive at the spot at the first time， and the shortest path search of the urban road is the key for the emergency disposal personnel to arrive at the spot at the first time. However， in consideration of the complexity of the actual road condition， if only one optimal path is provided， it is likely that this road section is not passable due to temporary traffic control or other factors. The optimal path search is conducted by introducing the time weight， adjacency matrix， and improved Dijkstra algorithm， so as to provide multiple shortest paths for emergency disposal personnel. The Anylogic software is adopted to conduct the emergency disposal simulation for the leakage accident of the gas emergency incident. The feasibility of applying the Anylogic software in the simulation evaluation for emergency disposal of gas emergency incidents is verified.

Keywords： gas emergency incident； emergency disposal； Dijkstra algorithm； optimal path； Anylogic； time weight； adjacency matrix

0 引 言

近年來我國發(fā)生重大及其以上的燃?xì)獍踩鹿蕯?shù)起，成為燃?xì)庑袠I(yè)面臨的嚴(yán)重問題，當(dāng)事故發(fā)生時，第一時間的應(yīng)急處置則顯得尤為重要。燃?xì)鈶?yīng)急處置人員能否在接到報警的第一時間趕到現(xiàn)場則是應(yīng)急處置的關(guān)鍵。如今的城市交通道路路況復(fù)雜，以時間最短為目標(biāo)可能存在多條最優(yōu)路徑，但基于目前燃?xì)鈶?yīng)急處置狀況，基本上只提供一條最優(yōu)路徑，這往往會造成當(dāng)所提供的最優(yōu)路徑因為臨時的交通管制等其他原因而無法通行時，燃?xì)鈶?yīng)急處置人員無法快速地選擇其余最優(yōu)路徑。所以為了避免上述情況的發(fā)生及綜合城市交通道路實際情況，本文提出采用改進(jìn)的Dijkstra最短路徑搜索算法，為燃?xì)鈶?yīng)急處置人員提供多條最短路徑，使燃?xì)馓幹萌藛T可根據(jù)實時的道路狀況進(jìn)行最佳選擇，在最短時間內(nèi)到達(dá)事故現(xiàn)場，為應(yīng)急處置爭取黃金時間。同時也使用Anylogic軟件對燃?xì)馔话l(fā)事件泄漏事故應(yīng)急處置進(jìn)行仿真模擬，驗證了Anylogic軟件在燃?xì)馔话l(fā)事件應(yīng)急處置仿真評估應(yīng)用的可行性。

1 Dijkstra最短路徑算法

路徑規(guī)劃的核心是最短路徑算法，研究最短路徑的算法很多，如啟發(fā)式搜索算法、神經(jīng)網(wǎng)絡(luò)方法、基于遺傳算法、蟻群算法等的最短路徑搜索。傳統(tǒng)的最短路徑搜索算法主要有Floyd算法和Dijkstra算法等。

Dijkstra算法是典型的單源最短路徑算法，用于計算一個節(jié)點到其他所有節(jié)點的最短路徑。它的主要特點一是以起始點為中心向外層層層擴(kuò)展，直至擴(kuò)展到終點；二是有代表性的最短路徑算法，有較高的應(yīng)用價值[1]。Dijkstra算法又稱為雙標(biāo)號法。所謂雙標(biāo)號，就是對圖中的點[vi]賦予兩個標(biāo)號[Pvi，λi]：第一個標(biāo)號[Pvi]表示從起點[v1]到[vi]的最短路徑長度；第二個標(biāo)號[λi]表示在[v1]到[vi]的最短路徑上[vi]前面一個鄰接點的下標(biāo)，即用來表示路徑，從而可對終點到起始點進(jìn)行反向追蹤，找到[v1]到[vn]的最短路徑。下面是Dijkstra算法的內(nèi)容：

2 改進(jìn)Dijkstra算法

在分析Dijkstra算法的基礎(chǔ)上，可以看出Dijkstra算法默認(rèn)為最短路徑上某個頂點只有一個前置鄰接點。但實際上，最短路徑上某個頂點可能有多個鄰接點，從源點出發(fā)到某一頂點之間，可能存在多條權(quán)重相同的最短路徑。采用Dijkstra算法的改進(jìn)，以解決多條路徑最短問題。

2.1 鄰接矩陣

為了更好地實現(xiàn)Dijkstra算法，用鄰接矩陣表示無向帶權(quán)圖，設(shè)無向帶權(quán)圖[G1=V，E]（見圖1），頂點[V]的集合為[V=V1，V2，…，V5]，邊長[E=E1，E2，…，E6]，則稱5階方陣為無向帶權(quán)圖的鄰接矩陣如圖2所示。

鄰接矩陣反映的是頂點與頂點之間的關(guān)系，矩陣的每個元素表示頂點之間邊的權(quán)重。如果矩陣元素[aij]為[∞]，那么說明兩個頂點之間沒有邊直接相連；如果矩陣元素[aij]為一個正整數(shù)[ωij]，那么說明兩個頂點之間有一條邊，邊的權(quán)重為[ωij]；如果矩陣元素[aij]為0，則說明鄰接矩陣主對角線上元素全為0。

采用鄰接矩陣表示帶權(quán)圖較為直觀，并且Dijkstra算法需要多次修改頂點最短路徑長度，用鄰接矩陣表示帶權(quán)圖，矩陣中的元素也容易修改。

2.2 算法改進(jìn)

本文采用的Dijkstra改進(jìn)算法為文獻(xiàn)[2]中提出的方法，主要解決了Dijkstra算法中多條最短路徑問題與多鄰接點問題，算法設(shè)計及改進(jìn)如下：

1） 初始化

對所有頂點進(jìn)行編號，并構(gòu)造鄰接矩陣。將起始點設(shè)定永久性標(biāo)號（p標(biāo)號），其余頂點都不是永久性標(biāo)號。根據(jù)起始點，求起始點鄰接點的最短路徑，前面的鄰接點及其個數(shù)。

2） 求下一個永久性標(biāo)號（p標(biāo)號）的頂點

通過鄰接矩陣，找到?jīng)]有永久性標(biāo)號、最短路徑長度最小的頂點v。如果頂點v的最短路徑長度為無窮大，退出算法，否則，將頂點v設(shè)定永久性標(biāo)號（p標(biāo)號）。通過頂點v以及鄰接矩陣，求頂點v的鄰接點x的最短路徑長度以及前面鄰接點及其個數(shù)。如果起始點經(jīng)過頂點v到鄰接點x的路徑長度小于鄰接點x現(xiàn)有的最短路徑長度，那么頂點x的最短路徑長度為起始點經(jīng)過頂點v再到頂點x的路徑長度。

3） 求下一個永久性標(biāo)號（p標(biāo)號）的頂點，如果所有頂點都有永久性標(biāo)號，退出程序[2]，否則轉(zhuǎn)步驟2）。

3 城市交通道路模型的構(gòu)建

城市動態(tài)交通路徑選擇系統(tǒng)分為兩個部分：其一是建立城市交通路徑拓?fù)浣Y(jié)構(gòu)；其二是建立城市交通道路路徑選擇的數(shù)學(xué)模型。因?qū)嶒灂r間等條件限制，模擬部分城市交通道路圖，抽象出城市交通拓?fù)浣Y(jié)構(gòu)。模擬城市交通道路圖如圖3所示。

假設(shè)模擬城市交通道路圖中道路相關(guān)信息，每條道路的相關(guān)信息主要包括：設(shè)計車速、路段名稱、路段長度、道路的擁堵系數(shù)（用0和1來表示，0表示道路正常通行，1表示道路完全擁堵，無法通行）。本文采用路段長度與路段行駛時間相結(jié)合的選擇路段的權(quán)值，若兩個節(jié)點不連通，則兩節(jié)點間距離為∞，本文采用∞來表示。其對應(yīng)的路徑拓?fù)浣Y(jié)構(gòu)如圖4所示。其中節(jié)點表示交叉路口；單實線表示道路路段。

權(quán)值是道路某些特征屬性的量化表示。因為權(quán)值是Dijkstra算法計算最短路徑的依據(jù)，尋找最短路徑即起點到終點之間的消耗最低，所以權(quán)值的確定是算法精確度的關(guān)鍵。本文設(shè)定每個路段來回方向上對應(yīng)的權(quán)值相等，即每一條邊都有且僅有一個權(quán)值。

傳統(tǒng)的Dijkstra算法中，權(quán)值僅表示2個節(jié)點之間的距離。由于城市交通道路，因受道路條件、道路繞行距離、交通條件的影響，使得不同的交通路徑中，盡管車輛行駛的距離相同，所需的時間還是有一定差異的。所以通過城市交通道路的距離長短來判斷是否是最優(yōu)路徑的方法不準(zhǔn)確。本文主要解決燃?xì)馔话l(fā)事件應(yīng)急處置中的路徑優(yōu)化，是指應(yīng)急處置人員在接到調(diào)度中心的指揮調(diào)度，由大隊所在地趕往事故現(xiàn)場這一段路的路徑優(yōu)化過程。這個問題與一般路徑優(yōu)化問題不同的是需要考慮實際的路況環(huán)境，如道路擁堵程度、行車速度等。并且從應(yīng)急的角度來講，本文的最優(yōu)路徑搜索以時間最短為目標(biāo)。故本文對權(quán)值的設(shè)定進(jìn)行改進(jìn)，以到達(dá)時間最短為準(zhǔn)則，在考慮最優(yōu)路徑時，結(jié)合道路的距離、擁堵系數(shù)等確定權(quán)值，使最優(yōu)路徑搜索結(jié)果為時間最短的路徑。經(jīng)過調(diào)研研究發(fā)現(xiàn)，在排除突發(fā)事件影響的條件下，城市主干道路的每日擁堵情況類似，擬定在下列擁堵條件下進(jìn)行算法實現(xiàn)。設(shè)定[QDi?Dj][i，j=1，2，…，17]表示道路[CDi?Dji，j=1，2，…，17]（以下簡寫為道路C）的權(quán)值，[YDi?Dj][i，j=1，2，…，17]表示道路C的擁堵系數(shù)， [LDi?Dj][i，j=1，2，…，17]表示道路C的路徑長度，[VDi?Dj][i，j=1，2，…，17]表示車輛的實際行駛速度，車輛行駛速度結(jié)合實際情況，假定每輛車正常行駛速度[V0]為60 km/h，則在不同的道路擁堵情況下，車輛行駛的速度公式為：

通過上述道路權(quán)值確定公式，確定模擬的城市交通道路圖部分道路權(quán)值如表1所示。

4 Anylogic建模分析

4.1 應(yīng)急搶修大隊

應(yīng)急搶修大隊包含一般燃?xì)馔话l(fā)事件應(yīng)急處置所涉及的必需人員及車輛設(shè)備，其中包括指揮、控邊、控壓、泄漏點排查、泄漏檢測、管線定位、管線修復(fù)、防腐層修復(fù)、土方作業(yè)、環(huán)境濃度監(jiān)測幾類人員。應(yīng)急搶修大隊當(dāng)收到調(diào)度中心的搶修任務(wù)單時，需攜帶必要的搶修物資、車輛趕赴現(xiàn)場進(jìn)行搶修。

4.2 燃?xì)庑孤?yīng)急處置流程

燃?xì)庑孤?yīng)急處置過程中主要包括以下幾個步驟：濃度檢測及環(huán)境監(jiān)測、管道控壓、控邊及疏散、查漏定位、開挖亮管、制定方案、作業(yè)修復(fù)、收尾恢復(fù)等處置步驟。

4.3 Anylogic建模

在Anylogic中，對應(yīng)急搶修大隊?wèi)?yīng)急處置模式進(jìn)行建模分析，驗證應(yīng)急搶修大隊?wèi)?yīng)急處置模式的可行性。

根據(jù)燃?xì)庑孤?yīng)急處置流程，將參與應(yīng)急處置的人員及物資都分別用一個Agent代表，利用Agent理論對搶修流程進(jìn)行建模，從而在Anylogic平臺上搭建基于Multi?Agent的燃?xì)庑孤?yīng)急處置模型。以檢測定位人員模型建立為例，概括模型建立過程。建立檢測定位人員模型，首先需明確在燃?xì)庑孤?yīng)急處置流程中檢測人員的職責(zé)及標(biāo)準(zhǔn)動作。職責(zé)及標(biāo)準(zhǔn)動作如下：

1） 接到搶修任務(wù)單后，跟隨應(yīng)急搶修大隊趕赴事故現(xiàn)場；

2） 對現(xiàn)場泄漏位置的管線進(jìn)行定位檢測，確定管線信息；

3） 將檢測結(jié)果報告指揮員；

4） 回到現(xiàn)場等待區(qū)域。

在Anylogic平臺中，以城市交通道路圖為背景，確定檢測人員的行動位置，再以狀態(tài)圖的形式對檢測人員進(jìn)行建模，檢測人員模型見圖5。

5 Anylogic實驗仿真

5.1 Anylogic中實現(xiàn)Dijkstra算法

為了驗證Dijkstra最優(yōu)路徑算法在燃?xì)庑孤?yīng)急處置中的有效性，在Anylogic平臺上通過Java語言實現(xiàn)Dijkstra算法。以圖3的城市交通模擬圖為實驗場景，假設(shè)D1為應(yīng)急搶修大隊所在地，D12為事故現(xiàn)場所在地。其中道路權(quán)值已經(jīng)計算完成。 圖6為城市交通道路無向帶權(quán)圖。

由圖6可以清楚地看到每條道路的權(quán)值，可以看到道路D8?D9，D6?D10權(quán)值較大，是通過道路所用時間較長的路段。為了更好地研究和編程實現(xiàn)Dijkstra算法，用鄰接矩陣表示圖6城市交通道路無向帶權(quán)圖。圖7是用鄰接矩陣表示城市交通道路無向帶權(quán)圖的部分鄰接矩陣。

運行最優(yōu)路徑算法起始頂點為D1，目標(biāo)頂點為D12，得出兩條最優(yōu)路徑，分別為：D1?D13?D12；D1?D3?D11?D12。

5.2 Anylogic燃?xì)庑孤?yīng)急處置模擬演練

將燃?xì)庑孤?yīng)急處置流程利用Anylogic平臺進(jìn)行模擬演練，驗證了應(yīng)急搶修大隊及Anylogic軟件在燃?xì)馔话l(fā)事件應(yīng)急處置仿真評估應(yīng)用的可行性，并為燃?xì)馔话l(fā)事件應(yīng)急處置標(biāo)準(zhǔn)化工作提供支持。

Anylogic中燃?xì)庑孤?yīng)急模擬演練的城市交通地圖即為圖3模擬城市交通地圖。圖8為Anglogic軟件中進(jìn)行燃?xì)庑孤?yīng)急處置模擬的3D視圖。

6 實驗結(jié)果分析

在Anylogic軟件中，以城市交通道路模擬圖為背景，建立交通道路模型。根據(jù)道路長度、擁堵系數(shù)等參數(shù)確定道路的權(quán)值屬性。確定屬性后將城市交通道路圖轉(zhuǎn)換為無向帶權(quán)圖，并用鄰接矩陣表示無向帶權(quán)圖。將鄰接矩陣編入改進(jìn)的Dijkatra算法程序中，在Anylogic軟件中實現(xiàn)改進(jìn)的Dijkstra算法。

在Anylogic中實現(xiàn)改進(jìn)的Dijkstra算法，得出以下兩條權(quán)值相同的最短路徑，分別是：D1?D13?D12；D1?D3?D11?D12。圖9中紫色所標(biāo)示的為兩條權(quán)值相同的最短路徑。

為燃?xì)鈶?yīng)急處置人員提供了兩條最優(yōu)路徑，當(dāng)D1?D3?D11?D12其中一段道路因臨時交通管制或其余突發(fā)狀況造成道路較平常擁堵時，此時通過此段道路就要花費比平時要多的時間，這樣燃?xì)鈶?yīng)急處置人員可根據(jù)實時路況選擇最佳道路即D1?D13?D12出行。圖10為Anylogic軟件運行中燃?xì)鈶?yīng)急處置人員結(jié)合實際路況后沿著最優(yōu)路徑出發(fā)。

在Anylogic中運行改進(jìn)的Dijkstra算法，得到兩條權(quán)值相同的最優(yōu)路徑，而傳統(tǒng)的Dijkstra算法默認(rèn)一個最短路徑上只有一個前置鄰接點，只能得出一條最短路徑的結(jié)果，若是遇到上述情況，則無法再給出其余最短路徑結(jié)果。

在Anylogic軟件中對應(yīng)急搶修大隊到達(dá)現(xiàn)場后的處置進(jìn)行了模擬演練，證明了燃?xì)庑孤?yīng)急處置流程的可行性，也驗證了Anylogic軟件在燃?xì)馔话l(fā)事件應(yīng)急處置仿真評估應(yīng)用的可行性。具體搶修過程如圖11所示。

7 結(jié) 論

針對燃?xì)庑孤?yīng)急處置最優(yōu)路徑及基于Anylogic燃?xì)庑孤?yīng)急處置模擬仿真，本文建立模擬城市交通道路的數(shù)學(xué)模型。引入時間權(quán)值及鄰接矩陣的方法，采用對傳統(tǒng)Dijkstra算法的改進(jìn)，為燃?xì)鈶?yīng)急處置人員提供多條權(quán)值相同的最短路徑，并利用改進(jìn)后的Dijkstra算法結(jié)合燃?xì)庑孤?yīng)急處置仿真模擬演練進(jìn)行驗證，規(guī)劃了燃?xì)鈶?yīng)急處置人員到達(dá)事故現(xiàn)場前的多條最優(yōu)路徑?？梢允谷?xì)鈶?yīng)急處置人員結(jié)合當(dāng)時的路況情形進(jìn)行最優(yōu)路徑的選擇，同時驗證了Anylogic在燃?xì)馔话l(fā)事件應(yīng)急處置仿真評估應(yīng)用的可行性。

參考文獻(xiàn)

[1] 袁琳，王淵，孫建蕓，等.基于權(quán)值的Dijkstra停車路徑規(guī)劃算法的優(yōu)化與實現(xiàn)[J].湖北大學(xué)學(xué)報（自然科學(xué)版），2017，39（3）：279?284.

YUAN Lin， WANG Yuan， SUN Jianyun， et al. Optimizing Dijkstra algorithm design and accomplishment for parking routing programming based on weight calculation [J]. Journal of Hubei University （Natural science）， 2017， 39（3）： 279?284.

[2] 王樹西，李安渝.Dijkstra算法中的多鄰接點與多條最短路徑問題[J].計算機(jī)科學(xué)，2014，41（6）：217?224.

WANG Shuxi， LI Anyu. Multi?adjacent?vertexes and multi?shortest?paths problem of Dijkstra algorithm [J]. Computer science， 2014， 41（6）： 217?224.

[3] 王宏.集裝箱海鐵聯(lián)運最優(yōu)路徑算法設(shè)計與仿真[D].北京：北京交通大學(xué)，2017.

WANG Hong. Design and simulation of optimal path algorithm for container sea?rail transport [D]. Beijing： Beijing Jiaotong University， 2017.

[4] 段汝東，侯至群，朱大明.基于Java的Dijkstra最短路徑算法實現(xiàn)[J].價值工程，2016，35（21）：208?210.

DUAN Rudong， HOU Zhiqun， ZHU Daming. Implementation of Dijkstra shortest path algorithm based on Java [J]. Value engineering 2016， 35（21）： 208?210.

[5] 閆倩.燃?xì)饩S搶修中的模擬演練和輔助決策關(guān)鍵因素及其相關(guān)性研究[D].北京：北京建筑大學(xué)，2015.

YAN Qian. Study on key factors and correlation of simulation drilling and aided decision?making in gas dimension rush repair [D]. Beijing： Beijing University of Civil Engineering and Architecture， 2015.

[6] 張旭鳳.第三方物流企業(yè)配送網(wǎng)絡(luò)演化規(guī)律及路徑優(yōu)化研究[D].北京：北京工業(yè)大學(xué)，2012.

ZHANG Xufeng. Research on evolution law and path optimization of distribution network of third party logistics enterprises [D]. Beijing： Beijing University of Technology， 2012.

[7] 劉超.燃?xì)廨斉鋺?yīng)急管理模擬系統(tǒng)研究[D].北京：北京建筑大學(xué)，2014.

LIU Chao. Study on emergency management simulation system for gas transmission and distribution [D]. Beijing： Beijing University of Civil Engineering and Architecture， 2014.

[8] MCNALLY P， MINYARD E. Emergency preparedness for oil and gas exploration and production [C]// Proceedings of SPE E&P; Health， Safety， Security and Environmental Conference. Denver： Society of Petroleum Engineers， 2015： 1?6.

[9] TERESCO J D. A Dijkstra′s algorithm shortest path assignment using the Google maps API： poster session [J]. Journal of computing sciences in colleges， 2010， 25（6）： 253?255.

[10] 詹淑慧，楊光.城鎮(zhèn)燃?xì)獍踩芾韀M].北京：中國建筑工業(yè)出版社，2007：60?66.

ZHAN Shuhui， YANG Guang. Safety management of town gas [M]. Beijing： China Architecture & Building Press， 2007： 60?66.