最短路徑算法在事故應(yīng)急救援中的應(yīng)用*

虞 謙 高岳毅 李 俊

江蘇省安全生產(chǎn)科學(xué)研究院

1 研究的背景與意義

在生產(chǎn)經(jīng)營(yíng)活動(dòng)中，無(wú)論是在生產(chǎn)、運(yùn)輸過(guò)程中還是在儲(chǔ)存、經(jīng)營(yíng)、使用環(huán)節(jié)，都可能發(fā)生重大安全生產(chǎn)事故，造成重大人員傷亡和財(cái)產(chǎn)損失。如2005年3月29日晚，在淮安境內(nèi)高速公路，因交通事故誘發(fā)液氯泄漏，造成29人死亡，疏散群眾1萬(wàn)多人。2010年7月，南京市地下丙烯管道泄漏爆燃，造成22人死亡，120多人受傷住院。當(dāng)發(fā)生重大事故時(shí)，如果能及時(shí)快速組織人員疏散撤離，將會(huì)減少和避免大量人員傷亡。但要做到這一點(diǎn)，需要確定最短撤離路徑和救援路徑。

本文重點(diǎn)研究了疏散及救援最短路徑的計(jì)算優(yōu)化算法，基于單源最短路徑的經(jīng)典算法—迪杰斯特拉（Dijkstra）算法，通過(guò)優(yōu)化算法節(jié)點(diǎn)，轉(zhuǎn)換道路節(jié)點(diǎn)圖層為帶權(quán)有向圖，運(yùn)用Dijkstra優(yōu)化節(jié)點(diǎn)算法并提出了事故疏散救援時(shí)最佳路徑，同時(shí)將已確定的事故模型及最短路徑的算法與地理信息系統(tǒng)（GIS）相結(jié)合，形成可視化最短路徑結(jié)果圖示化展示。

2 主要技術(shù)與方法概述

近年來(lái)，許多最短路徑算法研究已被用于解決實(shí)際問(wèn)題，例如，聯(lián)合國(guó)救援組織在2010年的海地地震中，運(yùn)用結(jié)合了最短路徑算法的地理信息系統(tǒng)制定應(yīng)急救援路線計(jì)劃[1-9]。本文分析和優(yōu)化基于Dijkstra最短路徑的算法，提出了針對(duì)節(jié)點(diǎn)優(yōu)化的Dijkstra最短路徑算法的優(yōu)化方案，并通過(guò)地理信息系統(tǒng)實(shí)現(xiàn)了最短路徑優(yōu)化算法的可視化問(wèn)題，討論了必要的證明和應(yīng)用條件。該方案已在公路信息系統(tǒng)中應(yīng)用，并取得了滿意的效果。

2.1 節(jié)點(diǎn)定義

在實(shí)際運(yùn)用中，首先需要根據(jù)現(xiàn)場(chǎng)道路情況，構(gòu)建出道路的節(jié)點(diǎn)圖層和道路圖層。

節(jié)點(diǎn)：道路的交叉點(diǎn)。

節(jié)點(diǎn)圖層的數(shù)據(jù)庫(kù)格式為：節(jié)點(diǎn)ID，X，Y

節(jié)點(diǎn)ID：表示節(jié)點(diǎn)本身。在數(shù)據(jù)庫(kù)中，一般只需要儲(chǔ)存節(jié)點(diǎn)ID和節(jié)點(diǎn)坐標(biāo)（如果不儲(chǔ)存節(jié)點(diǎn)ID，GIS系統(tǒng)可以通過(guò)空間地理查詢功能來(lái)獲得），儲(chǔ)存節(jié)點(diǎn)坐標(biāo)可以在進(jìn)行最短路徑計(jì)算和繪制路線時(shí)提高運(yùn)算速度。

在計(jì)算最短路徑的初始化階段，在儲(chǔ)存的道路圖層記錄基礎(chǔ)上，通過(guò)道路起點(diǎn)、終點(diǎn)、交叉點(diǎn)、道路長(zhǎng)度和道路路況系數(shù)建立道路的鄰接矩陣，以便計(jì)算最短路徑。使用公式來(lái)取值：

Wij=L[i, j]×P

式中：

L[i, j]—道路節(jié)點(diǎn)i到道路節(jié)點(diǎn)j間的距離，m；

P—道路路況系數(shù)。

2.2 算法優(yōu)化

Dijkstra核心算法步驟中對(duì)最小權(quán)值路徑的計(jì)算需要確定節(jié)點(diǎn)，針對(duì)此步驟，對(duì)節(jié)點(diǎn)使用情況進(jìn)行優(yōu)化，分為已標(biāo)記節(jié)點(diǎn)、臨時(shí)標(biāo)記節(jié)點(diǎn)和未標(biāo)記節(jié)點(diǎn)，在計(jì)算過(guò)程中直接選擇未標(biāo)記節(jié)點(diǎn)，可以節(jié)約大量計(jì)算時(shí)間，只需要運(yùn)算一次就可以按照權(quán)值對(duì)相關(guān)臨時(shí)節(jié)點(diǎn)進(jìn)行升序排列。

2.3 算法圖解

如圖1，以一個(gè)帶權(quán)有向圖來(lái)說(shuō)明Dijkstra優(yōu)化節(jié)點(diǎn)算法的計(jì)算過(guò)程。應(yīng)急救援的最短路徑問(wèn)題，一般是解決從應(yīng)急救援隊(duì)出發(fā)地點(diǎn)到事故發(fā)生地點(diǎn)的最短路徑問(wèn)題，因此，我們把其簡(jiǎn)化為搜尋兩個(gè)節(jié)點(diǎn)之間的最短路徑問(wèn)題。Dijkstra優(yōu)化節(jié)點(diǎn)算法，需要確定一個(gè)道路節(jié)點(diǎn)為起點(diǎn)，在事故應(yīng)急救援中，一般設(shè)應(yīng)急救援隊(duì)伍的出發(fā)點(diǎn)附近的道路節(jié)點(diǎn)為起點(diǎn)，設(shè)為s1；終點(diǎn)在事故應(yīng)急救援中，一般為離事故發(fā)生地點(diǎn)最近的道路節(jié)點(diǎn)，設(shè)為s6。

初始狀態(tài)：S是已計(jì)算出最短路徑的頂點(diǎn)集合，U是未計(jì)算出最短路徑的頂點(diǎn)的集合。

第1步：將源點(diǎn)s1放入S中。

此時(shí)，S={s1(0)},U={s2(∞),s3(2),s4(0),s5(6),s6(20)}。

注：s3(2)表示s3到起點(diǎn)s1的距離是2。

第2步：將頂點(diǎn)s3加入到S中。

圖1 帶權(quán)有向圖

上一步操作之后，U中頂點(diǎn)s3到起點(diǎn)s1的距離最短；因此，將s3加入到S中，同時(shí)更新U中頂點(diǎn)的距離。以頂點(diǎn)s2為例，之前s3到s1的距離為∞；但是將s3加入到S之后，s2到s1的距離為3=(s2,s3)+(s3,s1)。

此時(shí)，S={D(0)，s3(2)},U={s2(15),s4(12),s5(6),s6(20)}。

重復(fù)以上步驟，并不斷修正U集合中的路徑值。最后得到：S={s1(0),s2(15),s3(2),s4(10),s5(6),s6(12)}。因此，從源點(diǎn)s1到終點(diǎn)s6的最短路徑為12，見(jiàn)下表。

表 從s1到其余各頂點(diǎn)最短路徑

3 最短路徑展示技術(shù)

展示最短路徑需要結(jié)合運(yùn)用測(cè)繪、遙感、計(jì)算機(jī)模擬仿真技術(shù)、地理信息系統(tǒng)（GIS）等多種技術(shù)，主要包括以下內(nèi)容：

3.1 三維場(chǎng)景數(shù)據(jù)的制作

三維場(chǎng)景數(shù)據(jù)庫(kù)是最短路徑展示技術(shù)中的基礎(chǔ)和前提，而三維場(chǎng)景數(shù)據(jù)的制作是目前測(cè)繪行業(yè)先進(jìn)技術(shù)的綜合體現(xiàn)。多種類型數(shù)據(jù)的疊加形成三維場(chǎng)景數(shù)據(jù)，它包括矢量數(shù)據(jù)、影像數(shù)據(jù)、模型數(shù)據(jù)、地形數(shù)據(jù)等。在本項(xiàng)目研究的實(shí)例中，采用的是數(shù)字高程模型（Digital Elevation Modal，簡(jiǎn)稱DEM）數(shù)據(jù)，其中遙感數(shù)據(jù)采用精確到1m的IKONOS衛(wèi)星遙感影像數(shù)據(jù)，通過(guò)將數(shù)字高程模型、衛(wèi)星影像數(shù)據(jù)、三維地形數(shù)據(jù)和三維模型數(shù)據(jù)疊加，最后生成三維場(chǎng)景數(shù)據(jù)從而實(shí)現(xiàn)對(duì)真實(shí)世界的虛擬實(shí)現(xiàn)。

其中，三維地形數(shù)據(jù)的加工過(guò)程，如圖2。

圖2 三維地形數(shù)據(jù)的制作過(guò)程

除了三維地形數(shù)據(jù)外，還需要制作三維模型數(shù)據(jù)。為了清楚表現(xiàn)地表上的各種建筑設(shè)施，比如道路沿路的居民區(qū)、加油站等建筑設(shè)施，需要通過(guò)三維模型數(shù)據(jù)來(lái)建立。而融合了航空遙感、地形、三維地形、三維模型數(shù)據(jù)，并且需要使用先進(jìn)的數(shù)據(jù)打包技術(shù)才能夠最終制作成三維場(chǎng)景數(shù)據(jù)。三維場(chǎng)景數(shù)據(jù)的制作過(guò)程，如圖3。

圖3 三維場(chǎng)景數(shù)據(jù)的制作過(guò)程

3.2 三維系統(tǒng)功能集成

最短路徑展示技術(shù)發(fā)揮了GIS強(qiáng)大的空間處理能力，由傳統(tǒng)的二維空間擴(kuò)展到三維空間，使用戶能夠更直觀的感受建筑、道路、山體等三維目標(biāo)。并且實(shí)現(xiàn)了在三維空間中對(duì)目標(biāo)物體的查詢和定位。

依托GIS系統(tǒng)，在發(fā)生突發(fā)事故時(shí)，可以針對(duì)事故進(jìn)行事故影響范圍模擬，計(jì)算生成三維空間地理模型，并對(duì)事故進(jìn)行應(yīng)急救援最短路徑方案設(shè)計(jì)。例如，在某地發(fā)生泄漏事故后，可以對(duì)泄漏地點(diǎn)進(jìn)行定位查詢、泄漏發(fā)生后影響范圍在三維場(chǎng)景中的展現(xiàn)、泄漏周邊應(yīng)急救援物資及消防、醫(yī)療救援力量的查詢定位，綜合分析后自動(dòng)展示出人員撤離的最短路徑以及救援人員的最短救援路徑。如圖4展示了醫(yī)療救援最短路徑（以白色線顯示）。

圖4 事故應(yīng)急救援最短路徑展示技術(shù)

4 結(jié)論

本文研究了基于Dijkstra算法的最短路徑節(jié)點(diǎn)優(yōu)化方案，提出了在危險(xiǎn)化學(xué)品泄漏事故應(yīng)急救援中應(yīng)用最短路徑的技術(shù)手段，并將最短路徑的算法與地理信息系統(tǒng)相結(jié)合，通過(guò)圖示化展示出最短路徑。此技術(shù)手段可以有效迅速組織事故影響區(qū)域內(nèi)人員的疏散撤離，為減少和避免大量人員傷亡提供了技術(shù)支持。