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

朱雪麗

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

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

朱雪麗

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

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

災害疏散節點；容量約束；Dijkstra算法

一、問題提出

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

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

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

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

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

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

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

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

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

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

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

注：路徑中N（T）,T表示從本節點出發的時間。

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

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

思路：

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

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

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

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

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

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

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

三、結束語

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

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

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

[1]排行榜-自然大災難集調查-記事排行榜-新榜網.

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

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

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

（責任編輯：趙揚）

X913.4

A

1008—6153（2013）03—0114—02

2013-04-18

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