馬 毅，嚴(yán)余松

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

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

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

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

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

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

1 引 言

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

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

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

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

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

2.1 問題的提出

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

約束條件如下：

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

(2)平衡條件.

對(duì)于起點(diǎn)vs，滿足

對(duì)于終點(diǎn)vt，滿足

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

3 理想疏散時(shí)間流的求解算法

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

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

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

4 保守疏散時(shí)間流的近似求解算法

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

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

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

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

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

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

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

基于上述最長(zhǎng)路徑搜索方法，將經(jīng)典網(wǎng)絡(luò)流理論中的最小費(fèi)用流算法加以改造，即可用于求解近似保守最短疏散時(shí)間流.其基本步驟如下所示，并且在流量加載完畢后，重新搜索整個(gè)網(wǎng)絡(luò)的時(shí)間最長(zhǎng)路，該最長(zhǎng)路即為保守疏散時(shí)間.設(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)造方法類似于最小費(fèi)用流算法，但不同之處在于，當(dāng)弧上實(shí)時(shí)流量時(shí)，并不構(gòu)造與原弧方向相反的“時(shí)間費(fèi)用”為的反向弧，這樣做的目的是避免在增量網(wǎng)絡(luò)中尋找時(shí)間最長(zhǎng)路徑時(shí)出現(xiàn)回路，造成無法找到有效的最長(zhǎng)路徑；當(dāng)弧上實(shí)時(shí)流量時(shí)，將該弧凍結(jié)，設(shè)置為無效路徑.

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

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

5 計(jì)算示例

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

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

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

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

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

圖3 不同疏散人數(shù)下理想疏散時(shí)間與保守疏散時(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)急疏散理想疏散時(shí)間流問題與保守疏散時(shí)間流問題.理想疏散時(shí)間流和保守疏散時(shí)間流是應(yīng)急疏散時(shí)受危人群流動(dòng)分布的兩種極端狀態(tài).求解理想疏散時(shí)間流與保守疏散時(shí)間流，可以明確疏散過程的時(shí)間范圍，也能夠在一定程度上揭示哪些路徑是疏散時(shí)的關(guān)鍵路徑，哪些是不合理路徑，從而為制定合理的應(yīng)急疏散方案提供必要的理論依據(jù).

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

[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]高明霞,賀國(guó)光.考慮交叉口延誤和通行能力優(yōu)化疏散救援路線的最小費(fèi)用流模型[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ò)散實(shí)時(shí)影響下的應(yīng)急疏散路徑選擇模型[J].系統(tǒng)仿真學(xué)報(bào),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

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

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

：414580215@qq.com