路網(wǎng)應(yīng)急疏散理想與保守疏散時間流研究

馬 毅，嚴(yán)余松

(1.西南交通大學(xué) 交通運輸與物流學(xué)院，成都610031；2.四川師范大學(xué) 計算機(jī)科學(xué)學(xué)院，成都610068)

路網(wǎng)應(yīng)急疏散理想與保守疏散時間流研究

馬 毅1，嚴(yán)余松*2

(1.西南交通大學(xué) 交通運輸與物流學(xué)院，成都610031；2.四川師范大學(xué) 計算機(jī)科學(xué)學(xué)院，成都610068)

研究應(yīng)急疏散問題的理想疏散時間流及保守疏散時間流對于估計真實突發(fā)事件下的疏散時間具有重要的指導(dǎo)意義.為此構(gòu)建了理想疏散時間流與保守疏散時間流問題的數(shù)學(xué)規(guī)劃模型，并借鑒經(jīng)典網(wǎng)絡(luò)流理論的最短路、最長路、最小費用流算法原理，設(shè)計了求解理想疏散時間流與保守疏散時間流的兩個增廣路算法.該算法不但可以求得理想疏散情況及最壞疏散情況下的流量分布，還可以計算出各自對應(yīng)的理想疏散時間和保守疏散時間，從而識別出應(yīng)急疏散總時間的范圍域.最后通過算例演示了理想疏散時間流及保守疏散時間流的求解過程，并討論了他們的變化特征.

交通工程；應(yīng)急疏散時間；時間流算法；理想疏散時間；保守疏散時間；最小費用流

1 引 言

近段時間，由于國內(nèi)各大城市突發(fā)性事件頻繁發(fā)生，使得路網(wǎng)應(yīng)急疏散問題再次成為研究人員關(guān)注的熱點.路網(wǎng)應(yīng)急疏散問題是指當(dāng)城市發(fā)生突發(fā)性事件時，將處于事件發(fā)生地點的受危人群通過路網(wǎng)中的各條道路疏散至安全地點，從而將突發(fā)性事件帶來的影響盡量降到最低.

與微觀尺度的應(yīng)急疏散研究相比[1-3]，路網(wǎng)尺度的應(yīng)急疏散研究更適合計算突發(fā)事件下疏散流量、密度、速度等重要的統(tǒng)計量，且開展起來相對容易.目前，有關(guān)路網(wǎng)尺度的應(yīng)急疏散研究，Cova[4]提出了一個在復(fù)雜路網(wǎng)中識別最優(yōu)的基于車道的疏散路徑規(guī)劃模型，該模型在本質(zhì)上是一個最小費用流模型.Tjandra等人[5]用一種動態(tài)網(wǎng)絡(luò)流模型描述了疏散問題，并建立了最快速流模型，同時設(shè)計了求解該模型的單源點算法.Campos等人[6]基于最短路算法，以路徑集內(nèi)總通行能力與旅行時間比值最大化為目標(biāo)，求得了核電站事故地點至受災(zāi)人員接收地點的k條獨立的疏散路線.Hamacher等人[7]對路網(wǎng)應(yīng)急疏散問題進(jìn)行了綜述研究，探討了路網(wǎng)應(yīng)急疏散問題的最大流、最快速流等多個數(shù)學(xué)模型.Brachman等人[8]將基于地理信息系統(tǒng)的引導(dǎo)技術(shù)應(yīng)用于路網(wǎng)疏散研究中，建立了相應(yīng)的最快速模型，并用實例驗證了引導(dǎo)技術(shù)對疏散最快速流帶來的積極作用.國內(nèi)雖然對路網(wǎng)應(yīng)急疏散的研究起步較晚，但同樣取得了豐富的研究成果，高明霞等[9]建立了考慮交叉口延誤和通行能力的最小費用流模型來描述城市內(nèi)車輛的疏散路線問題，并設(shè)計了一個最小費用路算法來對模型進(jìn)行求解.袁媛等人[10]考慮了災(zāi)害擴(kuò)散的實時影響，將疏散路網(wǎng)中各路段上的疏散速度表示為隨時間變化的連續(xù)遞減函數(shù)，并建立了對應(yīng)的疏散路徑選擇模型.寧宣熙[11]建立了考慮擁堵的情況下，基于預(yù)估時間增量比較算法的疏散路徑的最短時間流路徑選擇模型，該模型充分考慮了流量變化對疏散時間的影響.

綜上所述，現(xiàn)有關(guān)于路網(wǎng)應(yīng)急疏散的研究，其建模及求解思想基本上都是在經(jīng)典最小費用流問題基礎(chǔ)上衍生而來的，但實際上疏散所需的總時間并不是“時間費用”的總和，而是其中受危人員通過時間最長的可行路徑時所需要的通過時間，也就是說，用“最小費用流”來表達(dá)最短疏散時間是有限制的.此外，現(xiàn)有大部分研究只考慮了理想情況下的最短疏散時間情況，但在某些情況下，我們需要知道將全體受危人員疏散完畢所需要的最長疏散時間，即保守疏散時間.一方面用以明確疏散過程的時間范圍，另外也可為制定疏散引導(dǎo)措施提供一定的理論支撐.

鑒于此，本文通過研究理想疏散情況下的最短疏散時間流與最壞疏散情況下的保守疏散時間流，并設(shè)計算法來求解對應(yīng)的流量分布及疏散時間，以此來達(dá)到明確應(yīng)急疏散時間范圍，合理制定疏散方案的目的.

2 路網(wǎng)應(yīng)急疏散的理想疏散時間流與保守疏散時間流問題

2.1 問題的提出

疏散路網(wǎng)可以用圖論的方法來表示，現(xiàn)將疏散路網(wǎng)記為G(V,A,C,T).其中V表示路網(wǎng)G的節(jié)點集；A={(vi,vj)|vi,vj∈V}為弧集，代表各節(jié)點之間的道路；C={cij|(vi,vj)∈A}為容量集；T={tij|(vi,vj)∈A}為時間集，tij表示流 fij通過弧(vi,vj)時所需要的通過時間，因各條道路上的通行條件各異，使得各弧(vi,vj)上的通過時間tij不盡相同.針對該疏散網(wǎng)絡(luò)G，則疏散過程可表示為將位于緊急事件發(fā)生地點vs的受危人員疏散到安全地點vt.

路網(wǎng)應(yīng)急疏散問題具有以下基本定義及基本定理[11]：

定義1（疏散基本路） 疏散基本路Pk是指疏散路網(wǎng)中任意一條由事故發(fā)生地點至安全地點的可行通路.

定義2（單位基本流） 單位基本流是指沿任意疏散基本路上的單位流動，即單位逃生者在任意基本路上的流動.

定義3（基本路的通過時間） 指基本流通過該基本路所需要的通過時間總和，表達(dá)式為

在疏散過程中，同一基本路通行時間的動態(tài)變化不容忽視，因為隨著受危人員在路段上的不斷聚集，造成通行時間受聚集人數(shù)的影響越來越顯著，一般情況下，路段聚集人數(shù)對通行時間的影響呈如下函數(shù)關(guān)系：

定理1（疏散流的分解定理） 若疏散流 f是無環(huán)流，則它可由基本流線性表示為

式中 ξi(i=1,2,…,m)是 m條單位基本流；αi(i=1,2,…,m)為各單位基本流的量級.

定義4（疏散流的通過時間） 假設(shè)疏散流 f可由m條基本流組成，則該疏散流通過網(wǎng)絡(luò)的所需時間并不是各條基本流通過時間的總和，而是其中通過時間最長的基本流的通過時間，即

定義5（理想疏散時間） 理想疏散情況下，將待疏散量疏散完畢所需要的最少通過時間.

定義6（保守疏散時間） 最壞疏散情況下，將待疏散量疏散完畢所需要的最少通過時間.

現(xiàn)以圖1中的簡單疏散網(wǎng)絡(luò)為例，說明理想疏散時間與保守疏散時間的概念，路段旁邊的數(shù)字分別表示該路段的通行時間和通行能力.

圖1 疏散示例網(wǎng)絡(luò)Fig.1 Demonstration network for evacuation

要將受危人員由事故地點v1疏散至避難地點v3.考慮到緊急事件造成的恐慌，造成人群在逃生過程中往往會隨機(jī)地選擇逃生路線，即路徑的選擇具有隨機(jī)性，這種隨機(jī)性就有可能造成兩種極端的疏散情況：(1)理想情況，受危人員隨機(jī)選擇了時間最短路徑v1→v3作為逃生路線，總的疏散時間為8，即理想疏散時間；(2)最壞情況，受危人員隨機(jī)選擇了時間最長路徑v1→v2→v3作為逃生路徑,總的疏散時間為13，即保守疏散時間.

2.2 路網(wǎng)應(yīng)急疏散理想疏散時間流與保守疏散時間流的數(shù)學(xué)模型

根據(jù)以上定義，設(shè)待疏散流量為q，用xij表示疏散過程中弧(vi,vj)上的流量，則可將應(yīng)急疏散的最短時間流問題歸納為下面的數(shù)學(xué)規(guī)劃模型：

(1)理想疏散時間流目標(biāo)函數(shù).

(2)保守疏散時間流目標(biāo)函數(shù).

約束條件如下：

(1)容量限制條件.對G中每條弧(vi,vj)，有

(2)平衡條件.

對于起點vs，滿足

對于終點vt，滿足

對于中間節(jié)點，流入量應(yīng)等于流出量，即對每個vi(vi≠vs,vt)

3 理想疏散時間流的求解算法

眾所周知，經(jīng)典網(wǎng)絡(luò)流理論中的最小費用流算法是解決含權(quán)網(wǎng)絡(luò)流問題最有效的算法之一，如果把最小費用流問題中的弧權(quán)由“費用”改為“時間”，那么只需要對最小費用路算法作適當(dāng)?shù)男拚?，即在流量加載過程中，每次均以單位基本流為流量加載單元加載于路網(wǎng)，更新路段通行時間，直到加載完全部疏散流量q，即可求解出理想情況下的最短疏散時間流，最后一次流量加載時，相應(yīng)加載路徑的通行時間即為理想疏散時間，現(xiàn)給出該算法的基本步驟.

設(shè)待疏散量為q，用k表示流量加載的次數(shù).

第0步 置k=0，并設(shè)初始流量為 f(k)=0.

第1步 構(gòu)造當(dāng)前流 f(k)的增量網(wǎng)絡(luò)N(f(k))，其構(gòu)造方法同最小費用流算法.

第2步 在增量網(wǎng)絡(luò)N(f(k))中搜索通行時間最短的增廣路，可應(yīng)用Ford算法進(jìn)行搜索，如果增量網(wǎng)絡(luò)不存在增廣路徑則算法停止.否則，在該時間最短路上加載一個單位的基本流(注：正向弧增加，反向弧減少)，并更新流量 f(k+1)=f(k)+1.

如果流量 f(k+1)的流值等于q，算法停止，表示人群疏散完畢；否則，利用式(2)更新各條路段的通行時間，置k=k+1，轉(zhuǎn)第1步.

4 保守疏散時間流的近似求解算法

應(yīng)急疏散的最壞情形是受危人員隨機(jī)選擇了時間最長路徑作為逃生路線，因此求解保守最短疏散時間流的關(guān)鍵是搜索時間最長路，但是，一般網(wǎng)絡(luò)圖的最長路徑問題是NP-Hard問題，不存在有效的多項式算法，而如果是有向無環(huán)圖，則可以通過改進(jìn)Dijkstra算法進(jìn)行求解.現(xiàn)借鑒Dijkstra算法的遞推原理，給出一種基于Dijkstra算法的變種算法來搜索時間最長路，其基本步驟如下.

對于有向無環(huán)網(wǎng)絡(luò)，將節(jié)點分為兩種類型：P標(biāo)號點和T標(biāo)號點，P標(biāo)號標(biāo)注已經(jīng)正確得到最長路的點；T標(biāo)號標(biāo)注未得到最長路的點，T標(biāo)號值表示最長路的下限，弧(vi,vj)的長度為wij.

第0步 令P(vs)=0，T(vi)=0，i=1,2,…t.

第1步 更新T標(biāo)號值，假定vi是新產(chǎn)生的P標(biāo)號，對vi指向的節(jié)點vj，進(jìn)行如下修改：

式中 右邊的T(vj)表示vj點舊的T標(biāo)號值.

第2步 產(chǎn)生新的P標(biāo)號點，其方法是：將P標(biāo)號點vi所關(guān)聯(lián)的邊都刪掉后，將入度為0的點標(biāo)記為新的P標(biāo)號點.

重復(fù)上述步驟直至終點由T標(biāo)號變?yōu)镻標(biāo)號，回溯即可找出起點到終點的最長路.

基于上述最長路徑搜索方法，將經(jīng)典網(wǎng)絡(luò)流理論中的最小費用流算法加以改造，即可用于求解近似保守最短疏散時間流.其基本步驟如下所示，并且在流量加載完畢后，重新搜索整個網(wǎng)絡(luò)的時間最長路，該最長路即為保守疏散時間.設(shè)待疏散量為q，用k表示流量加載的次數(shù).

第0步 置k=0，并設(shè)初始流量為 f(k)=0.

第1步 構(gòu)造當(dāng)前流 f(k)的增量網(wǎng)絡(luò)N(f(k))，其構(gòu)造方法類似于最小費用流算法，但不同之處在于，當(dāng)弧上實時流量時，并不構(gòu)造與原弧方向相反的“時間費用”為的反向弧，這樣做的目的是避免在增量網(wǎng)絡(luò)中尋找時間最長路徑時出現(xiàn)回路，造成無法找到有效的最長路徑；當(dāng)弧上實時流量時，將該弧凍結(jié)，設(shè)置為無效路徑.

第2步 在增量網(wǎng)絡(luò)N(f(k))中用上述Dijkstra變種算法搜索通行時間最長的增廣路，如果增量網(wǎng)絡(luò)不存在增廣路徑則算法停止.否則，在該增廣路上加載一個單位的基本流并更新流量.

如果流量 f(k+1)的流值等于q，算法停止，表示人群疏散完畢；否則，利用式(2)更新各條路段的通行時間，置k=k+1，轉(zhuǎn)第1步.

5 計算示例

下面通過一個算例來說明理想疏散時間與保守疏散時間之間的關(guān)系.示例路網(wǎng)如圖2所示，弧旁的數(shù)字分別表示路段零流下的通行時間和通行能力，節(jié)點v1為事故地點，節(jié)點v9為安全地點.現(xiàn)應(yīng)用本文設(shè)計的算法，計算不同受危人數(shù)輸入情況下的理想疏散時間與保守疏散時間.疏散人數(shù)設(shè)置為1到900，取路段擁擠參數(shù)α=1，β=1，計算結(jié)果如圖3所示.

圖2 示例網(wǎng)絡(luò)Fig.2 Demonstration network

圖3表明了該應(yīng)急疏散網(wǎng)絡(luò)在疏散人數(shù)不大于900的情況下，疏散時間的范圍域，即理想疏散時間曲線與保守疏散時間曲線之間的區(qū)域.其中，理想疏散時間曲線代表了疏散時間的理論下限，即全體受危人員最快可以在該理論下限時間內(nèi)疏散完畢；保守疏散時間曲線代表了疏散時間的理論上限，即在受危人員在網(wǎng)絡(luò)中不作停留的情況下，必可在該該時間理論上限內(nèi)疏散完畢.

而對于理想疏散時間與保守疏散時間隨不同疏散人數(shù)的變化趨勢，由圖3表明，隨著疏散人數(shù)的不斷增加，二者的差值呈現(xiàn)先增加再減少的趨勢，并在末尾處近乎相等.這是由于隨著疏散人數(shù)的不斷增多，路網(wǎng)的擁擠效應(yīng)越來越明顯，這也會使得理想疏散時間變得越來越不“理想”.

表1列出了當(dāng)疏散人數(shù)設(shè)定為900時的理想疏散流量分布情況與保守疏散流量分布情況，此時對應(yīng)的理想疏散時間為23.72，即受危人群最短可以在23.72個單位時間內(nèi)到達(dá)安全地點；對應(yīng)的保守疏散時間為24.87，即受危人群到達(dá)安全地點的最長時間不會超過24.87個單位時間.

圖3 不同疏散人數(shù)下理想疏散時間與保守疏散時間Fig.3 The ideal and conservative evacuation time by different evacuee numbers

表1 理想及保守疏散情況下的流量分布情況(疏散人數(shù)設(shè)定為900)Table 1 Distribution in ideal and conservative evacuation situation（input numbers:900）

6 研究結(jié)論

(1)探討了路網(wǎng)應(yīng)急疏散理想疏散時間流問題與保守疏散時間流問題.理想疏散時間流和保守疏散時間流是應(yīng)急疏散時受危人群流動分布的兩種極端狀態(tài).求解理想疏散時間流與保守疏散時間流，可以明確疏散過程的時間范圍，也能夠在一定程度上揭示哪些路徑是疏散時的關(guān)鍵路徑，哪些是不合理路徑，從而為制定合理的應(yīng)急疏散方案提供必要的理論依據(jù).

(2)設(shè)計了求解理想疏散時間流問題與保守疏散時間流的網(wǎng)絡(luò)增流算法.通過該算法，不但可以求解得到理想疏散情況及最壞疏散情況下的流量分布，還可以計算出分別對應(yīng)的理想疏散時間和保守疏散時間，為研究應(yīng)急疏散時疏散時間問題提供了一種重要的工具.

[1]Chen C K,Li J,Zhang D.Study on evacuation behaviors at a T-shaped intersection by a force-driving cellular automata model[J].Physica A:Statistical Mechanics and its Applications,2012,391(7):2408-2420.

[2]Zheng Y,Jia B,Li X G,et al.Evacuation dynamics with fire spreading based on cellular automaton[J].Physica A:Statistical Mechanics and its Applications,2011,390 (18):3147-3156.

[3]Wang L,Liu M,Meng B.Incorporating topography in a cellular automata model to simulate residentsevacuation in a mountain area in China[J].Physica A: Statistical Mechanics and its Applications,2013,392 (3):520-528.

[4]T J Cova,J P Johnson.A network flow model for lanebased evacuation routing[J].Transportation Research Part A:Policy and Practice,2003,37(7):579-604.

[5]Stevanus A，Tjandra.Earliest arrival flow with time dependent capacity approach to the evacuation problems[C].Pedestrian and Evacuation Dynamics 2002,Berlin,Springer press,2002:267-276.

[6]Campos V B G,da Silva.Evacuation transportation planning:A method of identifying optimal independent routes[C]//Proceedings of Urban Transport V:Urban Transport and the Environment for the 21st Century, Southampton,WIT press,2000:555-564.

[7]H W Hamacher,S A Tjandra.Mathematical modelling of evacuation problems:A state of art[C].Pedestrian and Evacuation Dynamics 2002,Berlin,Springer press, 2002:227-266.

[8]Brachman M L,Dragicevic S.A spatially explicit network science model for emergency evacuations in an urban context[J].Computers,Environment and Urban Systems,2014,312(44):15-26.

[9]高明霞,賀國光.考慮交叉口延誤和通行能力優(yōu)化疏散救援路線的最小費用流模型[J].系統(tǒng)工程,2006,24(9):6-10.[GAO M X,HE G G.Using minimum cost flow model to optimize evacuation routes considering delays and capacity at intersections[J]. Systems Engineering,2006,24(9):6-10.]

[10]袁媛,汪定偉.災(zāi)害擴(kuò)散實時影響下的應(yīng)急疏散路徑選擇模型[J].系統(tǒng)仿真學(xué)報,2008,20(6):1563-1566. [YUAN Y,WANG D W.Route selection model in emergency evacuation under real time effect of disaster extension[J].Journal of System Simulation,2008,20(6): 1563-1566.]

[11]寧宣熙.阻塞流理論及其應(yīng)用(第二版)[M].北京:科學(xué)出版社,2009.[NING X X.Blocking flow theory and its application(the second edition)[M].Beijing:Science press,2009.]

Research on Ideal and Conservative Time Flow for Emergency Evacuation on Road Network

MAYi1,YAN Yu-song2
(1.School of Transportation and Logistics,Southwest Jiaotong University,Chengdu 610031,China;2.School of Computer Science,Sichuan Normal University,Chengdu 610068,China)

Studying ideal evacuation time flow and conservative evacuation time flow for emergency evacuation problem is significant to predict the evacuation time in the situation of emergency.In view of this objective,a mathematical programming model for ideal and conservative time flow is built,meanwhile,two flow-augmenting algorithm to solve this model is developed by means of theory of the shortest path,the longest path and the minimum profit flow,the algorithm can not only calculate the flow assignment in ideal and worst evacuation situation,but also can calculate the corresponding value of evacuation time respectively,further,identify the range of total evacuation time.Finally a demonstration example is used to demonstrate the calculation process of ideal and conservative time flow,as well as discussing its evolution properties.

traffic engineering;emergency evacuation time;time flow algorithm;ideal evacuation time; conservative evacuation time;minimum profit flow

1009-6744（2015）01-0167-06

：U491;O157.6

：A

2014-06-30

：2014-12-16錄用日期：2014-12-22

國家自然科學(xué)基金(61104175).

馬毅（1986-），男，重慶合川人，博士生. ＊

：414580215@qq.com