謝 君，萬 慶，張 弛，李 強，李 響

1.華東師范大學 地理信息科學教育部重點實驗室，上海 200241

2.中國科學院 地理科學與資源研究所，北京 100101

3.中國科學院 新疆生態(tài)與地理研究所，烏魯木齊 830011

4.中國人民解放軍95806部隊

5.清華大學 建筑學院，北京 100084

虛擬結點法在多出口疏散方案中的適用性分析

謝 君1，萬 慶2，張 弛3，李 強4，5，李 響1

1.華東師范大學 地理信息科學教育部重點實驗室，上海 200241

2.中國科學院 地理科學與資源研究所，北京 100101

3.中國科學院 新疆生態(tài)與地理研究所，烏魯木齊 830011

4.中國人民解放軍95806部隊

5.清華大學 建筑學院，北京 100084

1 引言

城市的規(guī)模及人口密度隨著城市化進程的推進而不斷擴大，在此背景下，制定合理的撤離方案快速地組織人員在存在危險時有序地撤離到安全地區(qū)已經成為一個重要的問題。

目前，已有一些學者對突發(fā)事件應急疏散問題進行了多方面的研究。一些研究從宏觀模型的角度考慮[1]，對疏散地區(qū)或建筑建立模型，應用網絡流解決疏散問題，以達到系統(tǒng)最優(yōu)的目的。如Bretschneider及Kimms用混合整數規(guī)劃模型設計避免沖突的疏散路線，并采用啟發(fā)式方法解決高頻的計算量[2]。Yamada將城市模擬為無向圖，采用網絡流中的最短路徑方法制定疏散人群到避難場所的路徑，最小費用流方法解決避難場所的容量限制問題[3]。Liu等利用元胞傳輸模型將網絡按照突發(fā)事件的影響程度分成幾個區(qū)域，越靠近事發(fā)地點遭受的影響越嚴重，需要越快撤離。因此，采用分階段疏散策略確定各個區(qū)域疏散時間。在分階段疏散建模中，只有每個區(qū)域的開始撤離時間是可控制的。此分階段疏散策略通過在允許的安全時間窗內達到更統(tǒng)一的需求分布，從而大大減少疏散網絡的擁堵[4]。Li等提出了一種基于網絡的分階段疏散算法（下文簡稱分階段算法），該方法將地理位置相近的人員劃分為一個疏散小組，通過為每個疏散小組安排疏散出發(fā)時間并設計疏散路線，避免在疏散過程中不同疏散組之間可能產生的沖突，提高總體疏散效率。該方法為單個安全出口的應急疏散提供了一個較為有效的解決辦法，但尚不支持多出口情形，因此有一定的局限性[5]。Saadatseresht等采用多目標進化算法進行疏散規(guī)劃，在選擇每個建筑群的安全撤離區(qū)后，利用多目標優(yōu)化問題求解疏散規(guī)劃問題，同時考慮距離與安全區(qū)容量兩個因素，應用MATLAB中的NSGA-II完成疏散規(guī)劃[6]。

較之宏觀模型強調均一交通流特征，微觀模型更多考慮待疏散人員的個體行為差異，旨在模擬預測過程，或評估影響疏散過程的各種參數。如Pel等總結了以往學者的研究成果，認為重復的二進制邏輯模型適用于是否參與撤離以及開始撤離時間的預測，混合路徑選擇模型適用于疏散路徑選擇，該模型將疏散人員的行為與個人信息綜合到EVAQ模型當中[7-8]。Chen等提出采用龐特里亞金最小值原理獲得最短的應急時間，并動態(tài)考慮交叉口容量，但此方法僅適用單個個體[9]。何大治等采用幾何方法規(guī)劃人員的最佳疏散路徑，此方法突破傳統(tǒng)網格法限制人員只能在網格中移動，充分考慮人員的運動方向，具有很大的靈活性，設計人員個體和障礙物、人員個體之間的碰撞檢測方法，以移動路徑最短為目標，規(guī)劃人員疏散方向和路徑[10]。Zheng等基于粒子群優(yōu)化算法（PSO）改進其更新規(guī)則，既考慮個體行為的影響又考慮環(huán)境相互作用，使得距離安全出口最近的人員先疏散，但是當出現擁堵時，安排人員在擁堵區(qū)附近等待，這將有可能發(fā)生爭搶有效道路資源的問題[11]。Uno及Kashiyama利用多智能體模擬器“artisoc”開發(fā)應急疏散模擬軟件，用以分析疏散過程的演變規(guī)律[12]。最優(yōu)疏散調度算法中交通模擬模型和最小風險交通分配算法不可或缺。DYNASMART-P是一個在智能網絡設計，規(guī)劃，評估，交通仿真等領域有效的工具。疏散模型中安全區(qū)域需要被指定，但是分配給安全區(qū)的交通流是不能預設，因此，將所有指定的安全區(qū)域聚合到一個虛擬安全地區(qū)。同時在最小風險流建模中聚合區(qū)域以利于多個交通分析區(qū)（TAZ）被指定為一個安全區(qū)。實驗表明，所提出的方法在非預期極端事件中為大規(guī)模的緊急疏散管理提供了一個重要規(guī)劃[13]。

總結來看，宏觀模型與微觀模型側重點不同，前者強調統(tǒng)一疏散方案的制定，后者強調疏散個體在整個疏散過程中的表現與相互影響。Chen采用基于智能體的微觀模擬技術，研究同時和分階段疏散策略對加爾維斯頓島颶風疏散的效率。實驗結果顯示同時疏散不一定獲得有效的疏散方案而最有效的分階段疏散能夠減少約1 h的疏散時間[14]。也有實驗表明，如果分階段疏散合理地應用，能夠顯著減少疏散和延遲時間[15]。Li等設計實驗場景比較同時疏散與分階段疏散效率。在各個場景中，同時疏散需要的時間比分階段疏散少?，F實中，同時疏散無法總是保證所有疏散者能夠自發(fā)地移動，但分階段疏散是可控制的。并且隨著疏散規(guī)模的增大，分階段疏散花費的時間越接近同時疏散[5]。而本文提出的方案正是為解決大規(guī)模疏散問題，因此，著重分析利用虛擬結點法完善分階段算法在多安全出口情況下的適用性問題。

2 問題定義

本文采用典型的結點-弧段模型描述道路網絡[16]。即設G= A，N 表示一個道路網絡，其中A={a1，a2，…，an}表示對應 n條道路的弧段集，N={n1，n2，…，nm}表示對應m個道路交叉口的結點集。本文將待疏散人員根據其所處的地理位置聚合到道路網絡中的各結點并將同一結點的疏散人員歸為一組，然后由該結點進入道路網絡中。相關變量定義如下：

δ表示疏散組的數量。

Nexit表示安全出口結點（虛擬結點法將新增的虛擬結點對應此結點）。

t0表示疏散命令發(fā)出時刻。

routev=表示疏散組v的疏散路徑，共k條弧段，由以上定義可知，nv0和 Nexit分別對應routev中a和a二者的終點。

（3）用于疏散的道路具有近似的通行容量。

（4）無背景交通流。

根據以上變量及假設，總疏散時間TET定義如下：

TET表示從t0開始到第δ個疏散組完全通過Nexit過程中耗費時間最長一組的疏散時間。疏散方案的目的在于有組織地快速撤離人員，因此，本文將總疏散時間TET的長短作為評價方法適用性的標準。

3 方法

3.1 分階段算法

當突發(fā)事件的影響范圍較大，需要疏散居民較多時，同時疏散會使得短時的交通需求過大，而疏散路網容量是相對固定的，因此，疏散道路會處于飽和或者超飽和狀態(tài)，疏散車流擁擠十分嚴重，甚至會堵塞很長時間，總的疏散時間也會相應延長。因此，分階段算法的目的在于確保總疏散時間最小化的同時能夠使得整個道路網絡不發(fā)生擁堵，人員能夠有組織、有序撤離。因此，當公式（1）中TET獲得最小值時，總疏散時間達到最小。然而，對于給定疏散組v，t0和已知，最小化即可達到算法目的。根據變量定義，疏散組選擇到達安全出口的最短路徑即最小化在此算法中采用Dijkstra最短路徑算法[17]計算v到Nexit的最短路徑routev。因此，最小化成為算法的目標。理論上，當最接近Nexit的疏散組到達Nexit后，其他的疏散組連續(xù)地跟隨進入Nexit直到所有疏散組完成疏散是最優(yōu)的方案，但現實實現依賴于被疏散者的分布和道路網絡的空間配置。

一旦算法為所有疏散組設置好開始撤離時刻和撤離路徑，就告知疏散者，避免人員在交叉口發(fā)生擁堵，同時也避免人員在遇到擁堵時發(fā)生爭搶有效道路資源從而延長整個疏散過程。但此算法只能滿足一個安全出口的情況，有一定的局限性。因此，本文在上述算法的基礎上結合了虛擬結點法以適應多安全出口情況。

3.2 虛擬結點法

3.1節(jié)中介紹的分階段疏散算法尚不支持多出口情形，可利用虛擬結點修改網路結構以突破此局限性，將多源多匯問題轉換為多源單匯，也更容易滿足先進先出（FIFO）原則。此方法的目的在于減少網絡中所有疏散者的總出行成本[18]。具體步驟如下：首先，在網絡中添加一個虛擬結點，即網路流問題中的匯，并將它作為足以容納網絡中所有疏散者的最終安全出口，再將所有已知安全出口通過虛擬弧段連接到該虛擬結點，從而所有待疏散人員就作為該“匯”的輸入[1]。其中，所有安全出口在連接到虛擬結點后將作為路網中的待疏散容量為零的普通結點，虛擬弧段的長度為零，即通過時間為零。然后，將其應用到分階段算法中以解決道路網絡的人員疏散問題。如圖1所示，在原有道路結點圖層中增加一個虛擬結點 D*，將實際安全出口D1，D2連接到 D*，再次構建新的拓撲關系。疏散人員的最短疏散路徑即為出發(fā)結點到D*的最短路徑。在重建拓撲關系之后，道路網絡中只有一個安全出口，多安全出口問題轉化為單個安全出口問題，滿足分階段算法的適用條件，因而可對整個道路網絡應用分階段算法。

4 適用性分析

本文提出的方法采用C#語言在Microsoft Visual Studio 2010開發(fā)平臺，酷睿2 2.0 GHz CPU，2 GB內存環(huán)境下實現，并對其適用性進行分析。實驗設置如表1所示的6種多出口情景，隨機生成均勻分布和不均勻分布2類人口分布，并以圖2所示的包含247個結點，312條道路的某道路網絡為例，疏散者平均速度為10 m/s，采用虛擬結點法進行模擬疏散。

圖1 虛擬結點法示意圖

表1 實驗情景定義

圖2 道路網絡、出口和人口分布圖

圖3表示各實驗情景下以遠離安全出口的疏散組先撤離原則進行疏散時出口被疏散小組占用情況，實驗結果在0.58～1.2 s之內獲得。出口被占用情況間接反映出總疏散時間。最后占用出口的疏散組結束占用的時刻越晚，總疏散時間越長，方法適用性越差。反之，總疏散時間越少，方法適用性越好。從圖3中還可以獲得以下幾點信息。

首先，橫向比較圖3中各場景，情景1，情景4中各出口被占用時間差距最大。在情景1中，通過出口66，64的人數分別為37 186和10 360，出口66疏散的人數是出口64的3.589倍。而在情景4中，通過出口66，64的人數分別為5 795和1 422，出口66疏散的人數比出口64多出了3.075倍，各出口疏散的人數分配十分不均。結合圖2出口位置分布可知兩個安全出口地理位置集中，且分布在路網的一角，而各個疏散組按到虛擬結點的最短路徑選擇安全出口，導致多數疏散組選擇某一距離更近的出口（出口66）卻不選擇通往空閑出口（出口64）。因此在有組織疏散人群的前提下，部分疏散組的出發(fā)時間被延遲，最終導致疏散時間的明顯增長。

圖3 各情景出口被占用情況

其次，縱向觀察圖3中各場景，情景2、3、5、6各個出口被占用時間較為均勻。上述情景中，按各情景中出口編號順序，疏散人數比例依次為：1.053∶1，1.520∶1.342∶1.212∶1，0.994∶1，1.199∶1.106∶1∶1.093，由此可見，各安全出口需要疏散的人群總數約相當。且安全出口分散地分布在路網邊緣，因此，能夠充分利用兩個安全出口進行疏散。

此外，情景3下各出口疏散人數比例比情景2、5、6人數大，因道路網絡中結點的人數隨機分布，使得在情景3下通往出口64的人口數較其他出口更多，導致各出口需疏散的人口數不均，被占用時間差距大，從圖3中也可以得到印證。

圖4～6為情景1～3下以遠離安全出口的疏散組先撤離為原則的一系列時刻的快照圖。該系列時刻分別為第 2 200 s，2 300 s，2 400 s，2 500 s，2 600 s，2 700 s。不同顏色的結點表示聚集在此出發(fā)結點并等待出發(fā)時刻的各組疏散人員，不同顏色的線段表示正在撤離的各疏散組，線段的長度表示疏散組的大小，標有編號的結點表示安全出口。如圖4～6可知，開始出發(fā)的疏散人員能夠有序地通往各自的安全出口，而未開始疏散的人員則在原地等待其開始疏散的時刻，并未出現交叉口擁堵的情況。

圖4 情景1下疏散過程系列快照圖

圖5 情景2下疏散過程系列快照圖

圖6 情景3下疏散過程系列快照圖

由實驗結果可知虛擬結點法在情景2、3、5、6這些出口分布較為分散且各出口待疏散的總人口數相當的情況下，各個出口的被占用時間差距較小且最后占用出口的疏散組結束占用的時刻較其他場景早，總疏散時間也縮短，具有較好的適用性。然而，對于情景1、4這種出口分布較為集中，且各出口待疏散人口差距顯著的情景虛擬結點法的適用性較差。

5 結論

本文在已有的分階段疏散算法基礎上進行完善，結合虛擬結點法以解決多個安全出口的人群疏散問題，同時分析虛擬結點法的適用性。虛擬結點法即在原有道路結點圖層中新增一個虛擬結點作為最終安全出口，把原有實際出口作為普通結點并虛擬路徑將實際出口連接到該虛擬結點，重新構建拓撲關系后應用分階段疏散算法疏散人群。同時，本文以某路網為例設置在不同總疏散人口場景下，2個安全出口距離遠，2個安全出口距離近，4個安全出口均勻分布這3類不同安全出口位置分布情景進行實例驗證。模擬結果顯示，此方法能夠有效解決大規(guī)模人群的多安全出口應急疏散。但適用性因安全出口分布和各出口待疏散的人口總數差距不同而不盡相同，虛擬結點法更適合當各個安全出口的位置比較分散，且各安全出口需要疏散的人數分配較為均勻，使得各安全出口能夠接近同時完成疏散的情形。當多個安全出口較為集中，待疏散人群不能較均勻地分配到各安全出口，從而各出口不能保持大致同時處于疏散狀態(tài)時，方法的適用性較差。因此，調整各安全出口通過的待疏散人群，以使多個安全出口保持大致同時在疏散狀態(tài)，達到疏散時間的最優(yōu)化，這部分將會是下一步需要研究的問題。

[1]Hamacher H W，Tjandra S A.Mathematical modelling of evacuation problems-a state of the art[J].Pedestrian and Evacuation Dynamics，2002：227-266.

[2]Bretschneider S，Kimms A.A basic mathematical model forevacuation problemsin urban areas[J].Transportation Research Part A：Policy and Practice，2011，45（6）：523-539.

[3]Yamada T.A network flow approach to a city emergency evacuation planning[J].InternationalJournalofSystems Science，1996，27（10）：931-936.

[4]Liu Y，Lai X，Chang G L.Cell-based network optimization model for staged evacuation planning under emergencies[J].Transportation Research Record：Journal of the Transportation Research Board，2006，1964：127-135.

[5]Li X，Huang B，Liu Z J，et al.A novel method for planning a staged evacuation[J].Journal of Systems Science and Complexity，2012，25（6）：1093-1107.

[6]Saadatseresht M，Mansourian A，Taleai M.Evacuation planning using multiobjective evolutionary optimization approach[J].European JournalofOperationalResearch，2009，198（1）：305-314.

[7]Pel A J，Bliemer M C J，Hoogendoorn S P.A review on travel behaviour modelling in dynamic traffic simulation models for evacuations[J].Transportation，2012，39（1）：97-123.

[8]Pel A J，Hoogendoorn S P，Bliemer M C J.Evacuation modeling including traveler information and compliance behavior[J].Procedia Engineering，2010，3：101-111.

[9]Chen Y，Xiao D.Emergency evacuation model and algorithms[J].Journal of Transportation Systems Engineering and Information Technology，2008，8（6）：96-100.

[10]何大治，王長波，謝步瀛.基于幾何方法的人員疏散最佳路徑[J].工程圖學學報，2006，27（5）：23-28.

[11]Zheng Y，Chen J，Wei J，et al.Modeling of pedestrian evacuation based on the particle swarm optimization algorithm[J].Physica A：StatisticalMechanics and Its Applications，2012，391（17）：4225-4233.

[12]Uno K，Kashiyama K.Development of simulation system for the disaster evacuation based on multi-agent model using GIS[J].Tsinghua Science& Technology，2008，13：348-353.

[13]Chiu Y C.Traffic scheduling simulation and assignment for area-wide evacuation[C]//7th International IEEE Conference on Intelligent Transportation Systems，2004：537-542.

[14]Chen X.Microsimulation of hurricane evacuation strategiesofGalveston Island[J].The ProfessionalGeographer，2008，60（2）：160-173.

[15]Chien S I，Korikanthimath V V.Analysis and modeling of simultaneous and staged emergency evacuations[J]. Journal of Transportation Engineering，2007，133（3）：190-197.

[16]Sheffi Y.Urban transportation networks：equilibrium analysis with mathematical programming methods[M].Englewood Cliffs，NJ：Prentice Hall，1985.

[17]Dijkstra E W.A note on two problems in connexion with graphs[J].Numerische Mathematik，1959，1（1）：269-271.

[18]Han L D，Yuan F，Chin S M，et al.Global optimization of emergency evacuation assignments[J].Interfaces，2006，36（6）：502-513.

XIE Jun1,WAN Qing2,ZHANG Chi3,LI Qiang4，5,LI Xiang1

1.Key Laboratory of Geographic Information Science,Ministry of Education,East China Normal University,Shanghai 200241,China
2.Institute of Geographical Sciences and Natural Resources Research,Chinese Academy of Sciences,Beijing 100101,China 3.Xinjiang Institute of Ecology and Geography,Chinese Academy of Sciences,Urumqi 830011,China
4.Unit 95806 of PLA,China
5.School of Architecture,Tsinghua University,Beijing 100084,China

The expansion of city scale and ceaseless rise of population density are advanced by urbanization process.It’s an urgent problem to make an effective emergency evacuation plan with the purpose of evacuating pedestrian to safe places fast and orderly when danger happens.Many researches are done on this field,and virtual node approach is applied to network flow problem a lot.The staged evacuation algorithm based on road network for single exit is combined with virtual node approach which is applied to multiple exits evacuation planning,with the purpose of analyzing applicability of virtual node approach in this paper.The simulation results show that the approach can organize massive pedestrian to safe places orderly and fast.

multiple exits;virtual node approach;emergency evacuation;staged evacuation

城市化進程的迅速推進促使城市規(guī)模日益擴大、人口密度不斷提高，制定一個有效的應急疏散方案，使得人員在存在危險時快速且有序地撤離到安全場所，已經成為迫切需要解決的問題。目前已有一些研究成果，而虛擬結點法在網絡流中已有較多應用。結合基于道路網絡的單出口分階段疏散算法，將虛擬結點法應用在多出口疏散方案中，旨在對虛擬結點法的適用性進行分析。模擬結果顯示，該方法能夠有序、快速地組織大規(guī)模人群到安全場所。

多安全出口；虛擬結點法；應急疏散；分階段疏散

A

U491

10.3778/j.issn.1002-8331.1301-0194

XIE Jun,WAN Qing,ZHANG Chi,et al.Applicability analysis for virtual node approach to evacuation plan with multiple exits.Computer Engineering and Applications,2014,50（23）：245-250.

國家高技術研究發(fā)展計劃專項研究基金（No.2013AA122302）；華東師范大學科研創(chuàng)新基金資助課題；國家自然科學基金（No.41271441）；上海市自然科學基金（No.11ZR1410100）。

謝君（1988—），女，碩士生，研究領域為空間分析與建模；萬慶（1964—），男，研究員，研究領域為空間數據的組織與表達；張弛（1973—），男，研究員，研究領域為城市地理信息系統(tǒng)；李強（1973—），男，高級工程師，研究領域為地理過程模擬；李響（1975—），通訊作者，男，博士，教授，研究領域為空間分析與建模。E-mail：xli@geo.ecnu.edu.cn

2013-01-18

2013-03-11

1002-8331（2014）23-0245-06

CNKI網絡優(yōu)先出版：2013-04-08,http://www.cnki.net/kcms/detail/11.2127.TP.20130408.1646.006.html