朱雪麗

（山東省工會管理干部學(xué)院，山東 濟南 250100）

基于疏散計劃的最短路最大流分配算法初探

朱雪麗

（山東省工會管理干部學(xué)院，山東 濟南 250100）

隨著突發(fā)事件的不斷發(fā)生，大規(guī)模的人群疏散越來越受到人們的關(guān)注。突發(fā)事件往往伴隨著人群恐慌、擁堵等一系列現(xiàn)象，這一系列的不確定性往往導(dǎo)致疏散不利，造成不必要的財產(chǎn)損失和人員傷亡。Dijkstra算法目前被認為是求無負權(quán)網(wǎng)路最短路問題的最好方法，很多情況下，通過科學(xué)制定疏散計劃進行有效的疏散，可以減少意外事件發(fā)生時人群的疏散時間，減少人員傷亡及財產(chǎn)損失。

災(zāi)害疏散節(jié)點；容量約束；Dijkstra算法

一、問題提出

目前，人類正面臨越來越多的自然災(zāi)害威脅，如地震、海嘯、火山爆發(fā)、泥石流、颶風(fēng)等，此外，還有人為災(zāi)難，如恐怖襲擊、戰(zhàn)爭等。由于人口密度大，突發(fā)意外往往會因為疏散不利造成巨大的社會損失，帶來嚴重的人員傷亡，影響社會的發(fā)展。這些自然災(zāi)害往往讓人們措手不及，而且難以避免，但是，人類可以通過先進的技術(shù)手段，提前預(yù)測并通報這些災(zāi)害，事先制定疏散計劃并組織人員有效疏散，從而有效降低災(zāi)害損失及傷亡。因此，現(xiàn)在很多單位和學(xué)校越來越重視模擬疏散演練。

以近年來世界上發(fā)生過的意外災(zāi)害為例。1992年8月24日，“安德魯”颶風(fēng)以240公里/小時的風(fēng)速席卷邁阿密以南的霍姆斯特德一帶。颶風(fēng)所到之處，建筑物遭到嚴重損毀。在“安德魯”颶風(fēng)肆虐的幾天里造成了20多人死亡，1500萬人受傷。8月25日，“安德魯”颶風(fēng)225公里/小時的速度越過墨西哥灣，向路易斯安那州第一大城市新奧爾良市方向呼嘯而去，25日夜至26日凌晨，襲擊了路易斯安那州的沿海城鎮(zhèn)。[1]雖然在颶風(fēng)來臨之前，人們就做了許多防范措施，但損失還是非常慘重。由于沒有有效的疏散計劃，公路上車輛堵塞，寸步難行，造成了巨大的混亂，影響了道路暢通，極大的影響了受害群眾的疏散。

疏散是指將密集的人員、物資等分散轉(zhuǎn)移的行為。面對突如其來的自然災(zāi)害及人為災(zāi)難，制定有效的疏散計劃是非常有必要的。疏散大部分是在緊急事故中才有的現(xiàn)象，包括地震、海嘯、火災(zāi)、恐怖襲擊等一系列突發(fā)狀況，當(dāng)然也有非緊急狀況，如放學(xué)等。制定疏散計劃的目的就是能夠在緊急情況發(fā)生之前，或發(fā)生時能做到有條不紊的撤離，減少人員及財產(chǎn)損失。只有平時做好各項準備，遇到意外災(zāi)害時才能有效撤離，達到預(yù)期的目的。

意外災(zāi)害是無法避免的，但我們可以通過有效的疏散安排來減少財產(chǎn)損失及人員傷亡。在眾多突發(fā)事件中，由于沒有有效的進行疏散，造成了大量的人員傷亡，總結(jié)起來，失效疏散都是因為擁擠、恐慌或其他原因，沒有及時疏散到安全地帶，造成不必要的傷亡，因此，對疏散計劃的研究具有重要意義。

二、模擬情境下疏散計劃的制定

現(xiàn)給定如下參數(shù)：一個疏散網(wǎng)絡(luò)，即一個有向圖G=(N，E)；每個節(jié)點和每條邊均有容量約束(非負整數(shù))；每條邊的運行時間(非負整數(shù))；撤離人員數(shù)和他們的初始位置(源)；撤離目的地(匯)。

輸出：疏散計劃的組成包括一系列起點-終點路線和每條路線的撤離調(diào)度。路線安排應(yīng)按照各邊的容量約束，以每條疏散路線各邊的最小容量為準。

目的：盡量縮短疏散時間，即從開始疏散到最后一個疏散對象到達目的地的時間。疏散時間的減少能有效保護生命、財產(chǎn)的安全，保證穩(wěn)步、有效、危險性最小的疏散[2]。

情境描述：假設(shè)現(xiàn)有三個節(jié)點有受災(zāi)群眾，節(jié)點編號為N1、N2、N8，圖中標明各節(jié)點的最大容量。如（N1,50），表示N1節(jié)點的最大容量為50。三個節(jié)點現(xiàn)有受災(zāi)群眾分別為10、5、15。箭頭方向代表疏散路徑，圖中數(shù)據(jù)分別為（通道最大容量，通過所需時間）。如N1-N3節(jié)點為（7,1）代表本條路徑的最大通過能力為7，通過本條路徑需時1分鐘。

現(xiàn)假設(shè)本地發(fā)生意外災(zāi)害，需要人員緊急撤離。若無疏散計劃，那么在意外災(zāi)害發(fā)生的瞬間，各個節(jié)點的人群可能就會因突發(fā)意外造成的慌亂而紛紛涌至過道、出口，由于各節(jié)點及通道容量有限，若沒有合理的疏散計劃，就有可能造成擁堵甚至是踩踏事件的發(fā)生，造成疏散時間的浪費，進一步造成人員傷亡。現(xiàn)將疏散網(wǎng)絡(luò)描述如下：

先找出三個節(jié)點的疏散路線。如在本例中，N1節(jié)點的疏散路線有兩條，第一條：N1-N3-N4-N6-N10-N13，所需總時間為14分鐘。第二條：N1-N3-N5-N7-N11-N14，所需總時間為15分鐘。依次找出各節(jié)點的疏散路線。將受災(zāi)群眾分組，制定疏散計劃表如下：

注：路徑中N（T）,T表示從本節(jié)點出發(fā)的時間。

在制定疏散計劃表安排各條疏散路線的疏散人數(shù)時，必須以本條路線的最小邊容量為依據(jù)，否則將造成通道擁擠。如在D組疏散路線中，N3-N4的容量為3，所以每次疏散人數(shù)最大為3。

以N1節(jié)點為例，因為N1-N3路線的最大容量為7，在節(jié)點N1內(nèi)的10名受災(zāi)群眾可以分兩批疏散，第一批7人在第一時間撤離，第二批3人。N2節(jié)點的5名受災(zāi)群眾可在第一時間撤離到N3節(jié)點。

思路：

1、將節(jié)點容量和邊容量定義為一個時間序列，而不是一個固定的數(shù)字。對于一個給定節(jié)點Ni：可用節(jié)點容量(Ni,t)=t時刻節(jié)點Ni的可用容量。對于一條給定邊Ni-Nj：可用邊容量(Ni-Nj，t)=t時刻邊Ni-Nj的可用容量。

2、運用Dijkstra算法了解容量限制，歸納最短路徑算法。當(dāng)所有節(jié)點均有疏散對象：

第一步：基于當(dāng)前可用邊容量和可用節(jié)點容量，尋找從源到匯花費最短時間的路徑R。

第二步：計算路徑R的實際流量

流量=min{路徑R中源點的剩余疏散數(shù)量，可用邊容量(路徑R的所有邊)，可用節(jié)點容量(路徑R的所有節(jié)點)}。

第三步：保留路徑R的容量。

R上每條邊上的可用容量減少；R上每個接受節(jié)點的可用容量減少。

三、結(jié)束語

突發(fā)事件發(fā)生時，疏散往往伴隨著高密度的人群、極度驚恐的情緒和極度混亂的環(huán)境等大量不確定因素，疏散難度較大，具有挑戰(zhàn)性，因此，人們越來越關(guān)注大規(guī)模的人群疏散[3]。提前制定疏散計劃并進行演練可以建立個人和聯(lián)合的自我保護意識，可以估計撤離所需要的時間，使人們在面對突發(fā)的意外災(zāi)害時保持鎮(zhèn)定，能夠相對有條不紊的撤離，避免因疏導(dǎo)不善造成的財產(chǎn)損失及人員傷亡。

Dijkstra算法雖然目前被認為是求無負權(quán)網(wǎng)路最短路問題的最好方法，但是真正應(yīng)用到疏散計劃時卻有欠缺，容易因流量約束受到限制，就好比在實際疏散過程中，雖然找到了最短路，但是由于大量人群或車輛涌向本條最短路，結(jié)果造成擁堵，反而不利于撤離。

在疏散網(wǎng)絡(luò)中還有許多問題需要不斷的探討和研究。本例是在相對理想狀態(tài)下展開的，各節(jié)點容量、各邊最大容量是事先給出的，但是如何完善處理流量不確定的情況，仍需進一步研究。

[1]排行榜-自然大災(zāi)難集調(diào)查-記事排行榜-新榜網(wǎng).

[2]姚斌，劉乃安，李元洲.論性能化防火分析中的安全疏散時間判據(jù)[J].火災(zāi)科學(xué)，2003，（05）.

[3]孟博,劉茂,孫曉磊,王麗,劉付衍華.基于智能體模擬的結(jié)構(gòu)性疏散計劃設(shè)計研究[J].南開大學(xué)學(xué)報（自然科學(xué)版），2011，（2）.

[4]麻省理工學(xué)院,Capacity Constrained Routing Algorithms For Evacuation Planning:A Summary of Results.

（責(zé)任編輯：趙揚）

X913.4

A

1008—6153（2013）03—0114—02

2013-04-18

朱雪麗（1987-），女，山東萊蕪人，工程碩士，山東省工會管理干部學(xué)院教師。