基于時間擴(kuò)展網(wǎng)絡(luò)制定的混合速度疏散算法

徐 棟，李 響

(華東師范大學(xué)地理信息科學(xué)教育部重點實驗室，上海 200241)

基于時間擴(kuò)展網(wǎng)絡(luò)制定的混合速度疏散算法

徐 棟，李 響

(華東師范大學(xué)地理信息科學(xué)教育部重點實驗室，上海 200241)

針對大規(guī)模應(yīng)急疏散過程中基礎(chǔ)設(shè)施的供給與快速產(chǎn)生的疏散交通需求之間的矛盾，提出一種基于時間擴(kuò)展網(wǎng)絡(luò)用于有組織計劃的混合速度應(yīng)急疏散算法,其主要思路是以疏散者位置及運動速度建立疏散組，通過標(biāo)記路段的時間可用性確定不同疏散組的出發(fā)時間及路徑,以達(dá)到避免交通沖突及確保疏散效率的目的。實驗表明，該方法在確保疏散過程高效、有序進(jìn)行的前提下，可獲得與理論最優(yōu)值接近的疏散結(jié)果，且疏散規(guī)模越大，逼近效果越好。

混合速度；分階段疏散；時間擴(kuò)展網(wǎng)絡(luò)

0 引言

隨著城市人口密度的進(jìn)一步增加，為提高城市容量及服務(wù)水平，其基礎(chǔ)設(shè)施結(jié)構(gòu)及各種建筑必將變得愈加復(fù)雜，與此同時，城市人居環(huán)境在面臨突發(fā)事件時也變得更加脆弱，為此，事先制定各種應(yīng)對方案成為城市管理者的重要工作，其中，通過快速地將受影響人員轉(zhuǎn)移到安全地帶的緊急疏散就是此項工作之一[1]。針對大規(guī)模疏散問題，由于通常用于應(yīng)急疏散的道路網(wǎng)絡(luò)容量有限，無法同時滿足短時間內(nèi)快速產(chǎn)生的疏散交通流，因此，需要制定一個有效的疏散計劃，以減少交通擁堵，提高疏散效率。目前疏散問題已得到廣泛地研究，其主要研究方向大概可以分為以下兩種，疏散過程模擬和優(yōu)化，本文的研究關(guān)注于疏散過程優(yōu)化。

面向疏散過程模擬方向的研究工作旨在找出不同場景下影響疏散過程的重要因素或是用來評估疏散過程的性能[2-8]。該類研究主要使用元胞自動機模型[9-10]、智能體模型[11-12]、粒子群優(yōu)化方法[8,13-14]等進(jìn)行模擬。

面向疏散過程優(yōu)化方向的研究工作的一般目的是提出一種優(yōu)化的疏散計劃。由于疏散問題通常被認(rèn)為是將受影響人員從危險區(qū)域通過網(wǎng)絡(luò)基礎(chǔ)設(shè)施(如道路網(wǎng)絡(luò))轉(zhuǎn)移到安全地帶，因此網(wǎng)絡(luò)流模型被廣泛用于建模或優(yōu)化疏散流[1]。根據(jù)應(yīng)用情景的不同，研究者已經(jīng)提出了不同的目標(biāo)函數(shù)及應(yīng)用方法。例如，以整個網(wǎng)絡(luò)為研究對象的最大流方法[15-16]和最小費用流方法[17-18]，嘗試從中觀尺度將出發(fā)地、目的地和疏散流路徑組織起來；以車道和主要交叉口為研究對象的方法[19-22]，通過優(yōu)化轉(zhuǎn)向規(guī)則來減少交通沖突。在求解上述目標(biāo)函數(shù)時，最常用到的就是整數(shù)規(guī)劃或線性規(guī)劃算法[16-17,19,23]，其作為一種精確的算法通常應(yīng)用于小尺度問題并且需要額外的參數(shù)，如，一般很難預(yù)先獲知的上下邊界。也有研究者利用啟發(fā)式算法來解決大尺度及復(fù)雜的疏散情景，例如，進(jìn)化算法[22,24]和蟻群算法[25-27]，但是其解決問題的質(zhì)量和計算時間有時難以把握。此外，調(diào)度算法也是解決大規(guī)模疏散問題的常用算法[6,20,28-30]。他們一般是精確的算法并且將目標(biāo)與約束條件整合到算法的推演過程中。在應(yīng)用到疏散問題時，雖然不同的調(diào)度算法策略選擇有所不同，但其共同的目標(biāo)都是最小化等待時間[31]。其中，大多數(shù)算法采用同時疏散的方式，如果疏散者在遇到交通沖突時會等待，直到?jīng)_突消除后繼續(xù)撤離。這種疏散策略可能與現(xiàn)實生活中每個疏散者都希望最早出發(fā)并被盡快撤離的情形相符，但其不利于疏散計劃的實施。疏散者的途中旅行時間包括在路徑上的移動時間和等待時間，并且在大規(guī)模疏散過程中，后者花費的時間通常更長，從現(xiàn)實層面來說，在路徑上花費的時間越多，越容易引起不確定事件的發(fā)生，而且增加了組織者維持疏散者有序地通過交叉路口的難度。有鑒于此，Li[30]提出將途中等待時間轉(zhuǎn)換成在出發(fā)地的等待時間，疏散者在規(guī)定出發(fā)時間之前，原地等待，直到允許撤離后進(jìn)入道路網(wǎng)絡(luò)，并且途中將不存在交通沖突，直至到達(dá)安全地帶。通過實驗表明，通過這種算法制定的疏散計劃接近理論的最優(yōu)值，而且疏散規(guī)模越大，效果越好。但是該算法目前只適用于單一速度下的疏散情景，即所有疏散者具有相同的移動速度，該假設(shè)往往不符合現(xiàn)實情況。

基于對已有研究的分析，本文旨在從中觀尺度上提出一種用于混合速度應(yīng)急疏散的優(yōu)化算法，其通過將時間可用性記錄附加到疏散網(wǎng)絡(luò)基礎(chǔ)設(shè)施中，實現(xiàn)交通沖突的檢測和避免。因此，該疏散網(wǎng)絡(luò)被稱為時間擴(kuò)展網(wǎng)絡(luò)，利用該算法制定的是一種有組織的應(yīng)急疏散計劃，該疏散計劃適用于受影響區(qū)域的人員需要快速有效地撤離而且對即將到來的危險可預(yù)知的場景。其主要思路是根據(jù)疏散者所處位置及其運動速度建立疏散組；不同的疏散組通過本文提出的優(yōu)化算法得到的出發(fā)時間進(jìn)入道路網(wǎng)絡(luò)以達(dá)到避免交通沖突及確保疏散效率的目的；在確定出發(fā)時間時，考慮疏散組的速度差異，確保每個疏散組在出發(fā)以后都能以自己的最快速度移動到目的地。在本文接下去的部分，首先，對研究問題及相關(guān)變量和數(shù)據(jù)結(jié)構(gòu)進(jìn)行了定義，之后提出上述算法，最后，通過一系列模擬實驗，驗證了該算法的有效性并分析了算法的適用性。

1 問題定義

本研究采用結(jié)點-弧段模型表示用于應(yīng)急疏散的道路網(wǎng)絡(luò)[32]，并選擇其中度為1的某個結(jié)點作為疏散目的地，即安全出口。其相關(guān)定義為：N={n1,n2,n3…nm}：m個結(jié)點集合；A={a1,a2,a3…ak}：k條弧段集合；Nexit∈N：安全出口。

根據(jù)待疏散者所處位置及其運動速度建立疏散組，每個疏散組由靠近相同結(jié)點且具有相同速度的疏散者構(gòu)成。其相關(guān)定義為：g=〈c,n,s,l,v,t〉：單個疏散組。其中c代表該疏散組被完全加載到道路網(wǎng)絡(luò)上時所占據(jù)的隊列長度，n代表距離疏散組最近的結(jié)點，s代表疏散組到Nexit依此通過的弧段集合(即疏散路徑)，l代表疏散路徑長度(即s中所有弧段長度之和)，v代表疏散組速度，t代表疏散組的出發(fā)時間。δ：疏散組數(shù)量。

在上述定義中，當(dāng)疏散組的出發(fā)時間已經(jīng)確定后，需要將其疏散過程中占用弧段的時間信息記錄在一個與弧段相關(guān)的列表中，用以進(jìn)行交通沖突判斷。具有弧段占用時間信息記錄的網(wǎng)絡(luò)被稱為時間擴(kuò)展網(wǎng)絡(luò)，其定義為:ax∈〈l,olist〉：弧段集合中的一個元素。其中l(wèi)代表弧段長度，olist代表弧段被占用的時間間隔序列，olist={〈tf1,tt1,g1〉,〈tf2,tt2,g2〉,…,〈tfx,ttx,gx〉…}，其中任意元素的tfx和ttx分別代表疏散組gx到達(dá)弧段ax某一端點的時刻和完全通過該端點的時刻，ttx-tfx=gx·c/gx·v并且tfx-1

根據(jù)疏散組速度不同，將其進(jìn)一步組合成不同的疏散類，每一疏散類由多個具有相同移動速度的疏散組構(gòu)成，其定義為:C={C1,C2,C3…Cw}：由w個疏散類構(gòu)成的集合。Cx=〈v,glist〉：C中的一個元素，即一個疏散類。其中v代表該類的速度，與類中各疏散組速度一致；glist為疏散組列表，glist={g1,g2,g3…}。集合C中的不同元素之間速度不同，并且Cx·v>Cx+1·v。

令t0表示起始疏散時刻，則總疏散時間定義T為

T=max[((gx·t-t0)+gx·l/v+gx·c/v)],?x∈[1,δ]

(1)

由公式(1)知，每個疏散組gx的疏散時間由3部分相加而成，分別為gx在起點的等待時間、在路徑上花費的時間和完全通過Nexit所用的時間；總疏散時間T等價于所有組中的最長疏散時間，即最后通過出口的那一組所用的時間。

理論最優(yōu)總疏散時間Ts定義為

(2)

由公式(2)知，Ts表示理想狀況下最快的疏散時間，由最快到達(dá)出口的疏散組在路徑上所用時間與所有疏散組完全通過出口所用時間之和組成。達(dá)到理論最優(yōu)總疏散時間Ts需要滿足以下兩個條件：1)距離安全出口最近的疏散組必需在時刻出發(fā)并以其最快速度首先達(dá)到出口；2)任意兩個連續(xù)通過安全出口的疏散組之間沒有時間間隔且任意疏散組都能持續(xù)保持其最快速度疏散。盡管上述條件在實際情況中很難滿足，尤其是當(dāng)疏散組速度不一致時，但通過比較T與Ts，可用于評價本文算法的效率。相關(guān)定義為

Tr=(T-Ts)/Ts

(3)

Tr值越小代表T與Ts的差距越小，即算法的效率越高。

2 方法

根據(jù)前文討論，希望為每個疏散組設(shè)定優(yōu)化的疏散出發(fā)時間，用以替代在疏散途中由于交通沖突產(chǎn)生的可能等待時間。為此，對于任意疏散組g=〈c,n,s,l,v,t〉，定義以下策略：l為n到Nexit的最短距離，s為gx依次通過的路徑，c，n，v皆已知，通過計算疏散出發(fā)時間t確保gx一旦開始撤離，沿途不會停止，直至Nexit。通過逐一計算各個疏散類中疏散組的t，解決疏散速度差異的問題。相關(guān)算法給出如下。

算法1：總程序

1) 清空弧段占用時間列表olist。

2) 計算每個疏散組的n到Nexit的最短路徑，并記載路徑弧段集合s，及長度l。

3) 將每個疏散組出發(fā)時間t設(shè)為未知。

4) 從第一個疏散類C1開始，依次通過算法2為每一個疏散類Cx中疏散組確定出發(fā)時間t。

5) 結(jié)束。

算法2：計算同一個疏散類中各個疏散組的出發(fā)時間t

1) 對所有t未知的疏散組，通過算法3得到其暫定的出發(fā)時間tx。

2) 找到上述所有疏散組中tx最小的疏散組，記為gy。

3) 令gy·t=tx。

4) 對于gy·s中的每一條弧段，增加一個元素〈tfy,tty,gy〉到該弧段olist中。其中，tfy為gy進(jìn)入這條弧段的時間，tty=tfy+gy·c/gy·v；顯然第1條弧段增加的元素為〈tx,tx+gy·c/gy·v,gy〉。

5) 如果所有疏散組的出發(fā)時間均已知，則結(jié)束；否則，跳回步驟1。

算法3：計算疏散組的暫定出發(fā)時間

1) 令tx=t0，tc=gx·c/gx·v。

2) 建立列表O記錄gx·s中每條弧段以及其時間占用間隔，在這里假設(shè)gx·s={a1,a2,a3…},O={〈tf1,tt1,g1〉,〈tf2,tt2,g2〉,〈tf3,tt3,g3〉…}，其中tf1=tx,tt1=tx+tc,tf2=tf1+a1·l/Cx·v,tt2=tf2+tc,tf3=tf2+a2·l/Cx·v,tt3=tf2+a2·l/Cx·v,tt3=tf3+tc…

3) 對于O中的每一個元素〈ax,tfx,ttx〉

(1)將〈tfx,ttx,gx〉與ax·olist中的時間占用情況進(jìn)行比較，通過算法4得到推遲時間tp。

(2)如果tp>0,tx=tx+tp,跳回步驟2。

算法4：將〈tfx,ttx,gx〉與ax·olist中時間占用情況進(jìn)行比較，得到推遲時間tp

1) 令tp=0，tc=ttx-tfx。

2) 在ax·olist中找到元素〈tfz,ttz,gz〉，要求tfx≥ttz并且tfx-ttz=min{tfx-ttm,m=0,1…n-1,n表示ax·olist中元素的個數(shù)}。如果沒有找到合適的元素，令z=-1。

3) 如果z=n-1，返回tp的值。

4) 如果tf(z+1)≥ttx并且tf(z+1)+ax·l/g(z+1)·v≥ttx+ax·l/gx·v，返回tp的值。

5) 令tp=tp+(tt(z+1)-tfx)，tfx=tt(z+1),ttx=tfx+tc，返回步驟2。

圖1 疏散組gx與其它疏散組在同一弧段上的時間占用關(guān)系Fig.1 Time occupation relation between the evacuation group gx and the others evacuation groups on the same arc

算法1調(diào)用算法2為各個疏散類的疏散組確定出發(fā)時間。算法2為單個疏散類中的各個疏散組確定出發(fā)時間，這是一個循環(huán)的過程，每次循環(huán)從尚未確定的疏散組中選擇出一個具有最早暫定出發(fā)時間的疏散組，令其暫定出發(fā)時間為最終出發(fā)時間，并記錄其弧段占用時間。算法3用于確定每組的暫定出發(fā)時間，首先假定該組出發(fā)時間為t0，然后利用算法4判斷其疏散過程中是否存在交通沖突，如果存在，則延遲出發(fā)時間。算法4通過分析元素〈tfx,ttx,gx〉進(jìn)入弧段ax的時間段與ax·olist元素中時間占用關(guān)系來檢測交通沖突，如圖1所示。情況a表示gx通過ax過程中，ax沒有其他疏散組。情況b表示gx進(jìn)入ax時，ax前方有n個疏散組，在gx通過ax的過程中，沒有其他疏散組進(jìn)入ax。情況c表示gx進(jìn)入ax時，ax前方?jīng)]有任何疏散組，在gx通過ax的過程中有n個疏散組進(jìn)入ax，由于gx速度可能小于后面疏散組的速度，在此情況下需要考慮在gx通過ax過程中是否會被后面疏散組超越，如果有超越，gx的出發(fā)時間就需要推遲。情況d表示gx進(jìn)入ax時，ax前方有n個疏散組，在gx通過ax過程中，又有其他m個疏散組進(jìn)入ax，由于gx的速度小于或等于前面疏散組速度，因此仍只需考慮gx是否被后面疏散組超越。情況e表示gx到達(dá)ax時，恰好有疏散組進(jìn)入ax，此情況需要將gx進(jìn)入ax的時間向后延遲，直到gx可以完全進(jìn)入ax而不會與其他疏散組有時間沖突。

圖2 疏散網(wǎng)絡(luò)Fig.2 Road network

表1 實驗情景Tab.1 Experimental scenarios

3 實驗

我們選擇用于實驗的疏散網(wǎng)絡(luò)如圖2所示，包括312條弧段和247個結(jié)點，道路總長度為449.8公里，其中紅色結(jié)點為安全出口。疏散者隨機分布于該網(wǎng)絡(luò)區(qū)域中，并通過最近的結(jié)點進(jìn)入路網(wǎng)開始疏散，同一結(jié)點上速度相同的疏散者組成一個疏散組。算法通過C#語言編碼實現(xiàn)，并運行于一臺硬件配置為酷睿I5處理器，8G內(nèi)存的電腦上。本文對算法在不同疏散規(guī)模和不同速度構(gòu)成情況下的運行效率進(jìn)行了分析；為保證結(jié)果的有效性，針對每種情景，分別進(jìn)行10次隨機實驗，取平均值作為實驗結(jié)果，其中疏散組長度在1 000 m到2 000 m之間隨機取得，每次算法運行時間在19 ms至85 872 ms之間；最后，通過數(shù)值比較和模擬實驗的方法分析了實際值T與理論最優(yōu)值Ts之間差距產(chǎn)生的原因。

3.1 不同疏散規(guī)模下的算法效率分析

實驗設(shè)計6種不同情景來分別模擬不同疏散規(guī)模，如表1所示，網(wǎng)絡(luò)占用率表示所有疏散者完全加載到疏散網(wǎng)絡(luò)時，所占用的總長度與疏散網(wǎng)絡(luò)總長度之間的比值，占用率越大，代表疏散規(guī)模越大。設(shè)定在每種情形下，疏散組都被盡量均勻地分成4類，每一類具有相同的速度，分別為8，10，12，14，單位為m/s。

從表2實驗結(jié)果可以看出在6種情景中，隨著網(wǎng)絡(luò)占用率的增加，疏散時間明顯變長，而T-Ts值相對于總疏散時間來說非常小且變化不大，而且在網(wǎng)絡(luò)占用率較小(如情景1)時，T-Ts值大于網(wǎng)絡(luò)占用率大的情景(如情景5)。一種解釋是由于疏散組較為密集，由疏散組分布引起的時間差減少，而速度引起的時間差基本不變。再結(jié)合圖3所示，Tr值隨網(wǎng)絡(luò)占用率的增加而單調(diào)遞減，表明疏散規(guī)模越大，該算法制定的疏散計劃執(zhí)行效率越高。

表2 實驗結(jié)果Tab.2 Experimental results

圖3 各種情景下Tr平均值之間的關(guān)系Fig.3 The relationship between Tr and different scenarios

3.2 不同速度構(gòu)成下的效率分析

此實驗場景中，共有300個疏散組，網(wǎng)絡(luò)占用率為1.0。實驗設(shè)計4種不同情景來模擬不同速度分配下的疏散情況，如表3所示。其中，情景1,2,3有相同的速度類，但是情景2相比于情景1，各速度類間的差別更大；情景3相比于情景1，疏散組的速度更快；情景4與情景2有相同的最大和最小速度，但是情景4的疏散速度類別更多。每個速度類別下的疏散組數(shù)量接近。

從實驗結(jié)果表4可知，在具有相同速度類別數(shù)量情況下，情景2的Tr高于情景1與情景3，表明算法的效率與疏散組之間的速度差有很大聯(lián)系，速度差越小，算法效率越高；情景4的Tr與情景2接近并高于其它情景，表明速度類別數(shù)量對算法效率有一定影響，類別數(shù)量多會影響算法效率；情景1與情景3下Tr類似，表明在速度類別數(shù)量相同、速度差相似情況下，絕對速度值的不同對算法效率影響有限。

表3 實驗場景Tab.3 Experimental scenarios

表4 實驗結(jié)果Tab.4 Experimental results

3.3T與Ts差距分析

為理解實際值與理論最優(yōu)值之間差距產(chǎn)生的原因，進(jìn)一步對每個疏散組的疏散過程進(jìn)行了微觀分析。此次試驗具有400個疏散組，網(wǎng)絡(luò)占有率為1.34，速度分別為8,10,12,14，單位為m/s，其部分疏散組的信息如表5及表6所示。

在疏散剛開始時，當(dāng)一個疏散組完全撤離時，而接下來的疏散組尚未到達(dá)出口，這是疏散組分布導(dǎo)致的時間差，而隨著時間的延長更多的疏散組被加載到網(wǎng)絡(luò)中，這種時間差基本會消除。例如，從表5看出，84號疏散組t0+1 764撤離完畢，但是255號疏散組到達(dá)出口的時刻為t0+1 776。而從358號疏散組開始，可以看到其到達(dá)出口的時刻恰好等于前面疏散組完全撤離的時刻。

在疏散過程中，速度慢的疏散組與速度快的疏散組相繼進(jìn)入一條弧段時，由于在弧段上兩者的速度不同，當(dāng)速度快的完全撤離時，速度慢的疏散組還沒有達(dá)到出口，這是由疏散組速度差異導(dǎo)致的時間差。例如，從表6中看出，前3行和后3行疏散組各有相同的速度，在出口處可以很好地首尾相連，但是在第3行和第4行，399號疏散組完全進(jìn)入最后一條弧段的時刻為t0+11 896，而103號疏散組剛好在此刻尾隨而入，然而由于103號的速度慢，399號疏散組完全撤離時刻是t0+12 122，而103號疏散組到達(dá)出口的時刻是t0+12 159。

該實驗得到的實際疏散時間T=56 974 s，理論最優(yōu)疏散時間Ts=56 468 s，由分布引起的總時間差為337 s，由速度差引起的總時間差為169 s，而T-Ts=506 s，恰好是分布總時間差與速度總時間差之和。相對于總疏散時間來說，利用本文提出的算法得到的T-Ts值非常小，且根據(jù)上述分析，這一時間差是較難消除的。

上述過程可以通過我們的微觀仿真實驗直觀展示出來，圖4和圖5為一系列描述安全出口附近疏散網(wǎng)絡(luò)的時間快照：其中任意兩張連續(xù)快照的時間間隔為100 s；紅點表示安全出口所在的結(jié)點；其它具有不同顏色的線段表示不同疏散組，長度代表疏散組容量，標(biāo)識對應(yīng)于表5及表6中的部分疏散組。圖4快照的時間跨度從t0+1 500 s到t0+2 200 s，圖5快照的時間跨度從t0+11 600 s到t0+12 300 s。

表5 疏散組信息Tab.5 Evacuation group information(after the evacuation process began shortly)

注：疏散過程開始不久

表6 疏散組信息Tab.6 Evacuation group information(evacuation groups with different velocity were arriving at the exit)

注：疏散進(jìn)行中，具有不同速度的疏散組相繼到達(dá)出口

圖4 疏散過程開始不久一系列時間快照Fig.4 A series of time snapshot after at the evacuation process began shortly

圖5 疏散過程中不同速度疏散組到達(dá)出口時一系列時間快照Fig.5 A series of time snapshot during evacuation process when the groups arrived at exit with different volecity

4 結(jié)論

本文提出了一種基于時間擴(kuò)展網(wǎng)絡(luò)用于制定混合速度應(yīng)急疏散計劃的算法，其中時間擴(kuò)展網(wǎng)絡(luò)是指用于應(yīng)急疏散的網(wǎng)絡(luò)基礎(chǔ)設(shè)施，它不僅具有空間屬性，同時也記載其時間可用性，可用于疏散過程中交通沖突的檢測，利用該算法制定的是一種有組織的應(yīng)急疏散計劃。其主要思路是根據(jù)疏散者所處位置及其運動速度建立疏散組；通過設(shè)定不同疏散組的出發(fā)時間以達(dá)到避免交通沖突及確保疏散效率的目的；在確定出發(fā)時間時，考慮疏散組的速度差異，確保每個疏散組在出發(fā)以后都能以自己的最快速度移動到目的地。實驗表明，本方法在確保避免疏散過程中交通沖突發(fā)生的前提下，能夠獲得與理論最優(yōu)值接近的疏散結(jié)果，且疏散規(guī)模越大，該算法制定的疏散計劃執(zhí)行效率越高。在今后的研究中，我們將考慮疏散組內(nèi)疏散者數(shù)量閾值對算法效率的影響以及如何在多出口情況下解決混合速度疏散的優(yōu)化計劃制定問題。此外將研究問題向微觀尺度延伸，考慮疏散組內(nèi)部疏散個體之間的協(xié)同，也將是我們未來的研究方向。

[1]Southworth F.Regional evacuation modeling:a state-of-the-art review[J].Oak Ridge National Labs,1991,11(5):511-521.

[2]Sheffi Y,Mahmassani H,Powell W B.A transportation network evacuation model[J].Transportation Research Part A:General,1982,16(3):209-218.

[3]Kisko T M,Francis R L.EVACNET+:a computer program to determine optimal building evacuation plans[J].Fire Safety Journal,1985,9(2):211-220.

[4]Thompson P A,Marchant E W.Testing and application of the computer model ‘SIMULEX’[J].Fire Safety Journal,1995,24(2):149-166.

[5]Cova T J,J.Microsimulation of neighborhood evacuations in the urban-wildland interface[J].Environment and Planning A,2002,34(12):2211-2229.

[6]Chen X.Agent-based modelling and simulation of urban evacuation:relative effectiveness of simultaneous and staged evacuation strategies[J].The Journal of the Operational Research Society,2008,59(1):25-33.

[7]Duanmu J,Taaffe K M,Chowdhury M,et al.Simulation analysis for evacuation under congested traffic scenarios:a case study[J].Simulation,2012,88(11):1379-1389.

[8]Zong X,Xiong S,Xu H,et al.Space-time simulation model based on particle swarm optimization algorithm for stadium evacuation[J].Evolutionary Compution,2014:194-201.

[9]Varas A,Cornejo M D,Mainemer D,et al.Cellular automaton model for evacuation process with obstacles[J].Physica A:Statistical Mechanics and Its Applications,2007,382(2):631-642.

[10] Pelechano N,M A.Evacuation simulation models:Challenges in modeling high rise building evacuation with cellular automata approaches[J].Automation in Construction,2008,17(4):377-385.

[11] Pan X,Han C S,Dauber K,et al.A multi-agent based framework for the simulation of human and social behaviors during emergency evacuations[J].AI & SOCIETY,2007,22(2):113-132.

[12] Ren C,Yang C,Jin S.Agent-based modeling and simulation on emergency evacuation[M].Complex Sciences:Springer,2009,1451-1461.

[13] Cheng W,Bo Y,Lijun L,et al.A modified particle swarm optimization-based human behavior modeling for emergency evacuation simulation system[C]∥International Conference on Information & Automation.2008:23-28.

[14] Zheng Y,Chen J,Wei J,et al.Modeling of pedestrian evacuation based on the particle swarm optimization algorithm[J].Physica A:Statistical Mechanics and Its Applications.2012,391(17):4225.

[15] Hamza-Lup G L,Hua K A,Peng R,et al.A maximum-flow approach to dynamic handling of multiple incidents in traffic evacuation management[J].Intelligent Transporation Systems,2005:1147-1152.

[16] Zhang X,C G.A dynamic evacuation model for pedestrian-vehicle mixed-flow networks[J].Transportation Research Part C,2014,40:75.

[17] Yamada T.A network flow approach to a city emergency evacuation planning[J].International Journal of Systems Science,1996,27(10):931-936.

[18] Fleischer L,S M.Minimum cost flows over time without intermediate storage[C].SODA'03 Proceedings of the Fourteenth annual ACM-SIAM Symposium on Discrete Algorithms.PA,USA:Society for Industrial and Applied Mathematics,2003:66-75.

[19] Cova T J,J.A network flow model for lane-based evacuation routing[J].Transportation Research Part A.2003,37(7):579-604.

[20] Lu Q,George B,Shekhar S.Capacity Constrained Routing Algorithms for Evacuation Planning:a Summary of Results[M].Advances in Spatial and Temporal Databases:Springer,2005,291-307.

[21] Xie C,Lin D,Waller S T.A dynamic evacuation network optimization problem with lane reversal and crossing elimination strategies[J].Transportation Research.2010,46(3):295-316.

[22] Fang Z,Li Q,Li Q,et al.A space-time efficiency model for optimizing intra-intersection vehicle-pedestrian evacuation movements[J].Transportation Research Part C,2013,31:112.

[23] Stepanov A,S J.Multi-objective evacuation routing in transportation networks[J].European Journal of Operational Research,2009,198(2):435-446.

[24] Saadatseresht M,Mansourian A,Taleai M.Evacuation planning using multiobjective evolutionary optimization approach[J].European Journal of Operational Research.2009,198(1):305-314.

[25] Yi W,K A.Ant colony optimization for disaster relief operations[J].Transportation Research Part E,2007,43(6):660-672.

[26] Fang Z,Zong X,Li Q,et al.Hierarchical multi-objective evacuation routing in stadium using ant colony optimization approach[J].Journal of Transport Geography,2011,19(3):443-451.

[27] Li Q,Fang Z,Li Q.Ant Colony Based Evacuation Route Optimization Model for Mixed Pedestrian-Vehicle Flows[M].Pedestrian and Evacuation Dynamics 2012:Springer,2014,1213-1224.

[28] Liu Y,Lai X,Chang G.Cell-based network optimization model for staged evacuation planning under emergencies[J].Transportation Research Record:Journal of the Transportation Research Board,2006,1964(1):127-135.

[29] Sbayti H,Mahmassani H S.Optimal scheduling of evacuation operations[J].Transportation Research Record:Journal of the Transportation Research Board,2006,1964(1):238-246.

[30] Li X,Huang B,Liu Z,et al.A novel method for planning a staged evacuation[J].Journal of Systems Science and Complexity,2012,25(6):1093-1107.

[31] Chow W K,N.Waiting time in emergency evacuation of crowded public transport terminals[J].Safety Science,2008,46(5):844-857.

[32] Sheffi Y.Urban transportation networks:equilibrium analysis with mathematical programming methods[D].Englewood Cliffs,NJ:Prentice-Hall,1985.

(責(zé)任編輯 李進(jìn))

A Time-Extended Network Approach to Planning Multi-Velocity Evacuation

XU Dong，LI Xiang

(Key Laboratory of Geographic Information Science,Ministry of Education,East China Normal University,Shanghai 200241,China)

To deal with the contradiction between the supply of infrastructures and the demand of multi-velocity traffic flow in a large scale evacuation,we present an algorithm based on time-extended network.It can be applied to making organized and staged evacuation plans.First,evacuees are grouped according to their locations and velocities.Then,individual starting time and route are allocated to each group in order to avoid any traffic conflict and ensure the efficiency of evacuation through recording time availability of each road segment.Following this plan,each group can move towards to the safe exit at their own velocity.Experiments demonstrate that,with this algorithm,the total evacuation time is close to the theoretical shortest evacuation time.And the larger the evacuation scale is,the better the algorithm performs.

multi-velocity; staged evacuation; time-extended network

1672-3813(2017)01-0088-08；

10.13306/j.1672-3813.2017.01.013

2015-04-15；

2015-11-17

國家高技術(shù)研究發(fā)展計劃專項研究基金(2013AA122302)

徐棟(1989-)，男，山東濱州人，碩士研究生，主要研究方向為交通地理信息系統(tǒng)與空間優(yōu)化。

U491

A