劉炎強(qiáng)++王堅++凌衛(wèi)青

摘要：在突發(fā)事件區(qū)域人群疏散仿真的應(yīng)用中，為快速準(zhǔn)確的建立疏散區(qū)域內(nèi)的路網(wǎng)模型，本文結(jié)合數(shù)據(jù)庫與WebGIS接口技術(shù)搭建了GIS疏散路網(wǎng)模型。在分析了傳統(tǒng)的Dijkstra算法的基礎(chǔ)上，對Dijkstra算法進(jìn)行了改進(jìn)，并應(yīng)用到已建立完成的路網(wǎng)模型中，為疏散人群提供路徑規(guī)劃。實際案例分析表明，改進(jìn)后的算法符合大規(guī)模區(qū)域人群疏散要求，具有較強(qiáng)的適用性。

關(guān)鍵詞：區(qū)域人群疏散；WebGIS；疏散路網(wǎng)模型；Dijkstra算法

中圖分類號：TP18 文獻(xiàn)標(biāo)識碼：A 文章編號：1009-3044（2016）01-0245-03

Route Planning of Emergency Regional Crowd Evacuation Based on Simulation

LIU Yan-qiang， WANG Jian， LING Wei-qing

（Tongji University， Shanghai 201804， China）

Abstract： In the application of emergency regional crowd evacuation simulation， to quickly and accurately build a road network model in the evacuation area， the database and webGIS interface technology is combined to establish the GIS evacuation road network model. The classic DijkStra Algorithm which can provide route planning to the crowd is improved in this paper by the basis of its analysis， and has been applied to the established road network model. The anysis of results demonstrates that the modified Dijkstra algorithm satisfies the requirements of large-scale regional crowd evacuation and has good practicability.

Key words： regional crowd evacuation； webGIS； evacuation road network model； DijkStra algorithm

隨著經(jīng)濟(jì)社會快速發(fā)展和城市現(xiàn)代化水平不斷提高，自然災(zāi)害和人為災(zāi)害對城市功能正常發(fā)揮的影響程度和波及范圍也越來越大。面向這些災(zāi)害建立安全有效的突發(fā)事件區(qū)域人群疏散機(jī)制是一個重要研究問題，計算機(jī)仿真技術(shù)就是一種有效的研究手段[1]。只要能夠建立合理的人群疏散仿真模型，就可以利用計算機(jī)仿真技術(shù)，研制突發(fā)事件區(qū)域人群疏散仿真系統(tǒng)，通過仿真推演的方式模擬人群的疏散過程，為城市公共安全應(yīng)急管理人員提供決策參考，有效保障公眾的生命財產(chǎn)安全。

在現(xiàn)實社會的實際疏散過程中，疏散者的一切運(yùn)動都是在道路上進(jìn)行的，所以疏散路網(wǎng)模型為整個人群疏散仿真過程提供了最為基礎(chǔ)的道路數(shù)據(jù)[2]。有了準(zhǔn)確的路網(wǎng)模型，就可以使用各種網(wǎng)絡(luò)分析算法研究人群的疏散過程。本文使用的是改進(jìn)的Dijkstra最短路算法，為疏散人群提供路徑規(guī)劃，并在GIS疏散路網(wǎng)模型中得到了應(yīng)用。

1 GIS疏散路網(wǎng)模型

在突發(fā)事件人群疏散仿真系統(tǒng)中，疏散路網(wǎng)模型起到了至關(guān)重要的作用。好的路網(wǎng)模型不僅是對現(xiàn)實世界中路網(wǎng)的客觀抽象，更真實地反映路網(wǎng)內(nèi)部結(jié)構(gòu)及關(guān)系[3]，這直接決定了人群疏散仿真的結(jié)果與實際疏散情況的偏差程度。

隨著WebGIS技術(shù)發(fā)展的愈發(fā)成熟，國內(nèi)的許多在線地圖信息服務(wù)商如百度、騰訊、高德地圖等都陸續(xù)推出了各自的地圖API接口，幫助用戶在網(wǎng)站中構(gòu)建功能豐富、交互性強(qiáng)的地圖應(yīng)用。然而這些在線地圖API提供的路網(wǎng)雖然使用方便，但是缺少路段容量、路段人群擁擠度等關(guān)鍵信息，很難保證以此為基礎(chǔ)進(jìn)行的人群疏散仿真結(jié)果的有效性。因此本文的疏散路網(wǎng)模型是通過，先使用百度地圖API提供的繪圖功能在地圖上繪制出一個路網(wǎng)框架[4]，然后將繪制出的路網(wǎng)信息保存到數(shù)據(jù)庫中得到。路網(wǎng)信息有以下三種：

1）節(jié)點(diǎn)：道路上的交叉口、拐點(diǎn)和終點(diǎn)。屬性有節(jié)點(diǎn)ID、節(jié)點(diǎn)經(jīng)度和節(jié)點(diǎn)緯度。

2）路段：兩節(jié)點(diǎn)之間的道路。屬性有路段ID、頭結(jié)點(diǎn)ID、尾節(jié)點(diǎn)ID、路段長度、路段容量和路段人數(shù)。

3）路段權(quán)值：路段特征屬性的量化表示，用于Dijkstra最短路算法的路徑搜索指標(biāo)。根據(jù)優(yōu)化目標(biāo)的不同可以定義相應(yīng)的權(quán)值[5]，本文以人群疏散距離最短作為最優(yōu)目標(biāo)。

2 Dijkstra最短路算法

2.1 傳統(tǒng)Dijkstra最短路算法

Dijkstra算法是GIS應(yīng)用領(lǐng)域中用于求解最短路問題的經(jīng)典算法，傳統(tǒng)的Dijkstra算法用于尋求從一個固定源節(jié)點(diǎn)到其余各節(jié)點(diǎn)的最短路徑，它是迪杰斯特拉（Dijkstra）于1959年提出的一個按路徑長度遞增的次序產(chǎn)生最短路徑的算法[6]。設(shè)G = （V ， E ， W）是賦權(quán)無向圖，式中V和E分別是G的節(jié)點(diǎn)集合和邊集合，一條連結(jié)節(jié)點(diǎn)vi ， vjV的邊記為[vi ， vj]（或[vj ， vi]），每一條邊e = [vi ， vj]，相應(yīng)地有權(quán)值w（e） = wij。當(dāng)所有邊的權(quán)值wij ≥ 0時，該算法是目前公認(rèn)最好的最短路算法[7]。

Dijkstra算法的基本思想是從源節(jié)點(diǎn)vs出發(fā)，逐步地向外探尋最短路。執(zhí)行過程中，每個節(jié)點(diǎn)都會記錄下一個數(shù)稱為這個節(jié)點(diǎn)標(biāo)號，標(biāo)號有兩種，首先是P標(biāo)號表示從vs到該節(jié)點(diǎn)的最短路的權(quán)值，另一種是T標(biāo)號表示從vs到該節(jié)點(diǎn)的所有路徑（這些路徑中該節(jié)點(diǎn)的父節(jié)點(diǎn)必須已標(biāo)注過P標(biāo)號）權(quán)值的最小值。算法的每一步是去修改T標(biāo)號，然后找到所有T標(biāo)號最小值所標(biāo)注的節(jié)點(diǎn)，將其改為具P標(biāo)號的節(jié)點(diǎn)，從而使具P標(biāo)號的節(jié)點(diǎn)數(shù)多一個。這樣如果圖G中存在n個節(jié)點(diǎn)，那么經(jīng)過n-1步，就可以求出從vs到圖G中所有節(jié)點(diǎn)的最短路[8]。

傳統(tǒng)Dijkstra算法的具體步驟如下：

P（v）：v節(jié)點(diǎn)的P標(biāo)號；

T（v）：v節(jié)點(diǎn)的T標(biāo)號；

S：具有P標(biāo)號節(jié)點(diǎn)的集合；

a（v） = m：從vs到v最短路徑上，v的前一個節(jié)點(diǎn)是vm；

Step 1 初始化，令S = {vs}，P（vs） = 0，k = s，對每一個v ≠ vs，令T（v） = +∞。

Step 2 如果S = V，算法終止，此時vs到v最短路就是P（v），遍歷a（v）即可得到最短路徑；否則轉(zhuǎn)入Step 3。

Step 3 考查每個使[vk ， vj] E且vjS的節(jié)點(diǎn)vj。如果T（vj）>P（vk）+ wkj，則令T（vj） = P（vk）+ wkj，a（vj） = k。全部考查完畢后轉(zhuǎn)入Step 4。

Step 4 假設(shè)vmS且使T（vj）取最小值的節(jié)點(diǎn)，令P（vm） = T（vm），S = S∪{vm}，k = m。轉(zhuǎn)入Step 2。

2.2改進(jìn)的Dijkstra算法

從上節(jié)的算法描述中可以看出，傳統(tǒng)Dijkstra算法的求解過程由一個大循環(huán)嵌套小循環(huán)組成，其中外循環(huán)運(yùn)行n-1次，內(nèi)循環(huán)為兩個，第一個用來確定所有節(jié)點(diǎn)的T（v），第二個循環(huán)則用來找出所有T（v）的最小值，均至多運(yùn)行n-1次，因此算法的時間復(fù)雜度為 O（n2）。

對于城市區(qū)域疏散路網(wǎng)模型來說，它的特點(diǎn)首先是GIS節(jié)點(diǎn)數(shù)量多，可能達(dá)到成百上千個，這就對算法的計算時間提出了要求。其次當(dāng)發(fā)生突發(fā)事件時，人群大概率的分布在路網(wǎng)中的幾乎所有節(jié)點(diǎn)上，而且為保證疏散效率，人群被引導(dǎo)去往的避難區(qū)或者說是安全出口肯定不止一個，也就是說這是一個多源節(jié)點(diǎn)多目標(biāo)節(jié)點(diǎn)的最短路問題，如果每個源節(jié)點(diǎn)都運(yùn)用一次Dijkstra算法，其算法的時間復(fù)雜度將上升為O（n3）。為解決上述問題必須對傳統(tǒng)的Dijkstra算法進(jìn)行改進(jìn)。

我們知道，當(dāng)n較大時，Dijkstra 算法的效率急劇下降，如果能有效減少n值，也就是說減少參與運(yùn)算的節(jié)點(diǎn)數(shù)量或者是源節(jié)點(diǎn)的數(shù)量，那么其運(yùn)行速度將大大提升，以此優(yōu)化目標(biāo)為出發(fā)點(diǎn)，考慮以下兩點(diǎn)：

1）對于一個源節(jié)點(diǎn)來說，其目標(biāo)節(jié)點(diǎn)可能是多個，以疏散路程最短為原則，只要匹配到一個目標(biāo)節(jié)點(diǎn)，立刻退出循環(huán)，并將此路徑作為疏散路徑。

2）考慮到如果路徑L是從vs到vt的最短路徑，vi是L中的一個節(jié)點(diǎn)，那么從vi沿L到vt的路也是從vi到vt的最短路徑。利用如上事實，再加上區(qū)域疏散路網(wǎng)模型源節(jié)點(diǎn)個數(shù)多這個特點(diǎn)，運(yùn)算前對所有源節(jié)點(diǎn)到周圍目標(biāo)節(jié)點(diǎn)的直線距離從遠(yuǎn)到近進(jìn)行排序，先從較遠(yuǎn)的源節(jié)點(diǎn)開始運(yùn)算，這樣做得出的路徑中會大概率地包含許多其他源節(jié)點(diǎn)，根據(jù)結(jié)論這些源節(jié)點(diǎn)的最短路已經(jīng)找到，不用作為輸入?yún)⑴c后續(xù)運(yùn)算，以此達(dá)到減少源節(jié)點(diǎn)數(shù)量的目的。

基于上述思想，改進(jìn)的Dijkstra算法的具體步驟如下：

Y：源節(jié)點(diǎn)集合；

yi：Y中第i個集合

T：目標(biāo)節(jié)點(diǎn)集合；

Step 1 對Y中所有源節(jié)點(diǎn)到T中目標(biāo)節(jié)點(diǎn)的直線距離從遠(yuǎn)到近進(jìn)行排序。

Step 2 如果Y = ?，算法終止；否則在V中匹配y1，令vs = y1，Y = Y-{y1}，轉(zhuǎn)入Step 3。

Step 3 初始化，令S = {vs}，P（vs） = 0，k = s，對每一個v ≠ vs，令T（v） = +∞，P（v） = +∞。

Step 4 如果tT使得tS，轉(zhuǎn)入Step 5，此時vs到t最短路就是P（v），遍歷a（v）即可得到最短路徑；否則轉(zhuǎn)入Step 6。

Step 5 考查每個使yY且P（y） ≠ +∞的節(jié)點(diǎn)y，令Y = Y-{y}，此時y到t最短路就是P（y），遍歷a（y）即可得到最短路徑。全部考查完畢后轉(zhuǎn)入Step 2。

Step 6 考查每個使[vk ， vj] E且vjS的節(jié)點(diǎn)vj。如果T（vj）>P（vk）+ wkj，則令T（vj） = P（vk）+ wkj，a（vj） = k。全部考查完畢后轉(zhuǎn)入Step 7。

Step 7 假設(shè)vmS且使T（vj）取最小值的節(jié)點(diǎn)，令P（vm） = T（vm），S = S∪{vm}，k = m。轉(zhuǎn)入Step 4。

改進(jìn)的Dijkstra算法的路徑搜索流程如圖1所示。

圖1 改進(jìn)的Dijkstra算法流程圖

3應(yīng)用案例

本應(yīng)用采用B/S模式，通過網(wǎng)頁進(jìn)行瀏覽，前端主要用HTML和JavaScript語言編寫，Java語言用作后臺實現(xiàn)了改進(jìn)后的Dijkstra算法，并且采用了百度地圖API技術(shù)結(jié)合MySQL數(shù)據(jù)庫對包括路網(wǎng)模型在內(nèi)的疏散模型進(jìn)行建立。案例選取的事故地點(diǎn)為上海野生動物園，疏散路網(wǎng)模型見圖2。模型中共建立254個節(jié)點(diǎn)，295條路段，在圖2中紅色的圓點(diǎn)代表節(jié)點(diǎn)，藍(lán)色的線條代表路段，節(jié)點(diǎn)與路段的信息存于數(shù)據(jù)庫中。

上海野生動物園在節(jié)假日期間遇到的最大實時客流量大約在25000人左右，案例中人流量為24340人，分布在園區(qū)內(nèi)的眾多熱門景點(diǎn)上，具體的人群分布情況見圖3。隨后將人群分配到各個路網(wǎng)節(jié)點(diǎn)上以進(jìn)行計算得到疏散路徑，統(tǒng)計出需要疏散的源節(jié)點(diǎn)數(shù)量為95個。

圖2 疏散路網(wǎng)模型

圖3 人群分布熱力圖

圖4 使用Dijkstra算法得到的疏散路徑

圖5 從百度地圖API獲取的疏散路徑

圖4是采用改進(jìn)的Dijkstra算法得出的所有源節(jié)點(diǎn)的疏散路徑，計算用時0.086秒，計算機(jī)配置為Intel Core 2 Quad Q8300，內(nèi)存為4G。圖中路段顏色用來表示疏散時該路段的擁擠程度，綠色代表暢通、橙色代表擁擠、紅色代表非常擁擠，三個藍(lán)色圖標(biāo)表示避難區(qū)，也就是算法中的目標(biāo)節(jié)點(diǎn)。圖5是在相同的場景下，通過百度地圖API獲取到的疏散路徑，獲取全部路徑用時22.95秒。

比較圖4與圖5中的疏散路徑可以看出，百度地圖API擁有的路網(wǎng)模型更加的詳細(xì)，但是大體上兩幅圖顯示的路段分布和路段擁擠程度都比較相似，而且顯然算法的計算速度肯定要比通過網(wǎng)絡(luò)獲取的速度要快很多，最重要的是自建疏散路網(wǎng)模型靈活性大、更貼近于實際情況，可以根據(jù)需要建立起更豐富、準(zhǔn)確的路網(wǎng)模型屬性。因此結(jié)合本文建立的GIS疏散路網(wǎng)模型，改進(jìn)的Dijkstra算法完全可以用來進(jìn)行區(qū)域人群疏散的疏散路徑規(guī)劃。

參考文獻(xiàn)：

[1] 盧兆明. 基于GIS的都市應(yīng)急疏散系統(tǒng)[J]. 中國公共安全， 2005（2）： 35-40.

[2] Yosef S， Hani M， Warren BP. A transportation net-work evacuation model[J]. Transportation Research， 1982， 16A（3）： 209-218.

[3] 曹政才， 韓丁富. 基于新型路網(wǎng)模型的路徑尋優(yōu)方法研究[J]. 電子學(xué)報， 2012， 40（4）： 756-761.

[4] 百度地圖API鼠標(biāo)繪制管理類參考.

http：//api.map.baidu.com/library/DrawingManager/1.4/docs/symbols/BMapLib.DrawingManager.html. 2014.3.

[5] 白塵. 交通路網(wǎng)中最優(yōu)路徑算法的道路權(quán)重選擇[J]. 中國管理信息化， 2009， 12（15）： 54-56.

[6] Dijkstra E. A note two problems in connection with graphs[J]. Numerical Mathemat， 1959， 1： 269-271.

[7] 劉翠麗， 張思東. GIS應(yīng)用領(lǐng)域中Dijkstra算法的一種改進(jìn)[J]. 電信快報， 2005（5）： 46-48.

[8] 王樹西， 吳政學(xué). 改進(jìn)的Dijkstra最短路徑算法及其應(yīng)用研究[J]. 計算機(jī)科學(xué)， 2012， 39（5）： 223-228.