朱雪麗

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

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

朱雪麗

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

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

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

一、問題提出

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

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

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

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

二、模擬情境下疏散計(jì)劃的制定

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

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

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

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

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

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

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

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

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

思路：

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

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

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

第二步：計(jì)算路徑R的實(shí)際流量

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

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

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

三、結(jié)束語

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

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

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

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

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

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

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

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

X913.4

A

1008—6153（2013）03—0114—02

2013-04-18

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