EN中文

Journal of Geo-information Science >

2016 , Vol. 18 >Issue 3: 362 - 368

DOI: https://doi.org/10.3724/SP.J.1047.2016.00362

Orginal Article

Optimization of Evacuation Routes Planning Algorithms for Flood Events

  • LI Mengya , 1, 2 ,
  • WANG Jun , 1, 2, * ,
  • SHEN Hang 1, 3
Expand
  • 1. School of Geographic Sciences, East China Normal University, Shanghai 200241, China
  • 2. Key Laboratory of Geographic Information Science of Ministry of Education, East China Normal University, Shanghai 200241, China
  • 3. School of Resource and Environmental Sciences, Wuhan University, Wuhan 430079, China
*Corresponding author: WANG Jun, E-mail:

Received date: 2015-04-30

  Request revised date: 2015-06-12

  Online published: 2016-03-10

Copyright

《地球信息科学学报》编辑部 所有
Fold

Abstract

Well-planned evacuation routes definitely contribute to reducing traffic congestions and mitigating logistics costs during an emergency evacuation. With an objective to minimize the total evacuation time, an approach to seek optimum evacuation routes in a capacity constrained road network was presented in this paper, and then it is carried out based on a scenario with severe surge floods affecting an island county in Zhejiang province, China. The classical Dijkstra algorithm is improved by addressing the issues aroused with respect to evacuees' demands, traffic congestion, and the equal accessibility to and assignment of relief resources. Besides, regarding the fact that, since the evacuee units contain a large population, it is hard to find a closest shelter with enough capacity at one time, thus the mixed split delivery model is adopted. Namely, a unit might be divided into several groups and sent to different shelters separately. Using C#, an applet with built-in algorithms named MiniGIS is developed for the visualization of the dynamic evacuation flow. As presented in this paper, the ideal algorithm, though being capable of finding out the optimal evacuation routes, is based on a highly ordered scenario in which only simple traffic congestion is considered. Next, the additional delay caused by mode transferring and slow down at road cross-sections, turnings and crowded segments is taken into consideration. In addition, the delay-improved algorithm, which records the state of each group at road conjunctions, is able to calculate the total delay if given the time when evacuation state swifts from one to another. Undoubtedly, it provides more reliable results than the ideal algorithm does; however, due to route adjustments, several retrogressions are captured in the routes planned by delay-improved algorithm using the tracking animation in MiniGIS, implying that a certain vehicle is required to return to a former earlier location before heading toward the destination according to the new planned route. Considering routes with retrogressions are not common and easily being identified and adjusted, such routes are artificially fixed and then input to the retrogression-improved algorithm, which would calculate the new evacuation time and meanwhile avoid redundant retrograde motions. Basically, though the total travel time would slightly exceed that of delay-improved algorithm, results of retrogression-improved algorithm is still regarded as the optimum solution giving priority to efficient evacuation management and resource economization.

Key words： emergency evacuation; routes planning; algorithm optimization; flood events; MiniGIS

Cite this article

LI Mengya , WANG Jun , SHEN Hang . Optimization of Evacuation Routes Planning Algorithms for Flood Events[J]. Journal of Geo-information Science, 2016 , 18(3) : 362 -368 . DOI: 10.3724/SP.J.1047.2016.00362

1 引言

灾后应急响应能有效减少生命和财产损失,是增强公众逃生技能,提高灾害管理效率,完善城市安全体系的重要途径[1-3].灾后应急响应主要包括人员疏散和物资配给2个方面[4],而将受灾人员疏散到安全地带是救灾工作第一阶段的紧要任务.合理的路径规划能有效缩短疏散时间,具有重要的现实意义[5].
建立网络(流)模型是应急疏散路径规划的基础,最佳路径求解算法因寻优目标而异,最短路径[6],最快路径[7-8],最大流[9-10],最小费用最大流[2,11]等是普遍用于应急疏散问题的基本算法.由于灾害事件和疏散对象的差异性,需对基本算法进行定向设计和改进,以体现研究侧重点.Naghawi和Wolshon设计了交通方式选择模块,提出城市公交系统是最有效的疏散方式[12];Yi和Özdamar采用整合的选址--路径分配(FLP)算法,在求解最佳疏散路径的同时,还可对车辆中转站点,避难场所的选址进行优化[13];Kaisar根据特殊受灾对象的社会属性计算疏散需求权重[14];叶明武根据洪水淹没进程确定不同灾区的疏散顺序[15];Chen设计了分阶段疏散算法,也被证明能有效减少交通拥堵,加快疏散过程[16].此外,微观规划需考虑疏散对象的主观反应和随机移动特性,元胞自动机(CA),人工神经网络(ANN)等算法也被广泛采用,并取得了较好的效果[17-18].
以往以算法为主的应急疏散研究多关注于求解方法的优化,对算法的实用性和计算效率缺乏实例验证,而利用模拟平台反馈对算法进行优化的研究较少.本文以浙江省玉环县遭遇超强台风(中心气压915 hPa)风暴洪水灾害情景为例,以疏散总时间最短为目标,对经典Dijkstra算法加以改进,采用混合拆分疏散方法,构建洪灾应急疏散路径规划模型.运用C#语言开发应急疏散分析工具MiniGIS,求解最佳路径,并对规划路径进行动态模拟,根据反馈逐次对算法进行优化.

2 数据准备与疏散规划建模

2.1 疏散网络构建

县域尺度的洪灾疏散适于进行大,中尺度路径规划[19],受灾人员以村为单位聚集为受灾点,且不考虑其主观意识.将疏散过程中的空间实体(受灾点,避难场所,道路等)抽象为结点和弧段,采用GIS网络分析和POLYVRT结构处理方法[20],构建疏散拓扑网络.考虑到部分受灾点和避灾点与道路在拓扑上不完全连通,利用最短的直线弧段将其与道路网络接合[21].以上过程通过C#语言编程实现.网络模型信息如表1所示.
Tab. 1 Features of the emergency evacuation network

表1 应急疏散网络要素

要素 结点/个 弧段/条 需疏散人数/人 避灾总容量/人
受灾点 避灾点 道路结点
数量 92 69 19 401 590 168 635 446 988
属性 受灾人口,空间位置 避灾容量,空间位置 空间位置 通行时间 - -

2.2 混合拆分疏散方法

洪涝灾害中的受灾人群在空间上比较集中,对于人数较多的受灾点而言,不一定能在其附近找到一次性容纳所有灾民的避灾点,故本文采用混合拆分疏散方法[13](图1(a)),将受灾点拆分成多个疏散组,分拨到不同的避灾点,不仅可以加快疏散进程,也能充分利用避灾资源.
Fig. 1 Flowchart of mixed split delivery method and splitting evacuee units

图1 以疏散组为单位的混合拆分疏散方法

但考虑到拆分受灾点会增加疏散管理的难度,需对疏散组的数量加以控制.为了避免单个受灾点被拆分的次数过多,本文设置最小疏散组人数(MinPop),确保拆分过程中不会出现人数小于MinPop的疏散组.以疏散组为单位的疏散流程如图1(b)所示.

2.3 疏散规划模型

对于以疏散组为基本单位的疏散规划,采用式(1)所示的目标函数进行人群分配和路径选择.
MinT = ∑ i = 1 M ∑ j = 1 N t ij x ij + T a (1)
式中:MinT为最小疏散总时间;M为疏散组数量;i为其编号;N为避灾点数量;j为其编号;tij为从i到j的时间;xij为标记,当疏散组i分配给避灾点j时,xij=1,否则 x ij = 0 ; T a 为交通拥堵等待时间.
规划约束条件为:
(1)需求控制: ∑ i = 1 M x ij = 1 ,确保每个疏散组i内的人员都被迁移到安全避灾点.
(2)容量限制:对于每个避灾点,记其最大容量为 C maxj ,实际容量为 C actj , C actj ≤ C maxj .
(3)先到先得:采用Dijkstra算法,为每个疏散组找到其最快到达的避灾点.在每个避灾点处,按照到达时间先后为疏散组标记序号为 S ij ,令序号较小的疏散组先进入该避灾点.记g,h分别为2个疏散组,若: x ij ( g ) = x ij ( h ) = 1 ,且 t ij ( g ) < t ij ( h ) ,则 S ij ( g ) < S ij ( h ) ;若 x ij ( g ) = x ij ( h ) = 1 , t ij ( g ) = t ij ( h ) ,且 P i ( g ) > P i ( h ) ,则 S ij ( g ) < S ij ( h ) ,Pi为疏散组i上的人数.最小疏散组人数MinPop=30.
(4)中途自主调整路线:若疏散组在某一路口因交通拥堵等待时间较长,则以此路口为起点,搜索新的疏散路径,并进行判断:若等待时间与原路径剩余疏散时间之和大于新路径上的疏散时间,则按新路径到达避灾点,完成疏散[15,22-23].
此外,假设疏散过程中实行交通管制,限制不用于疏散的车辆数量;对于同时到达道路结点且将要进入相同下一路段的疏散组,后到的疏散组必须等待先到达的疏散组通过以后才能依次通过;所有疏散组在得到疏散指示后同时开始疏散.疏散开始后,人群和车辆能以不超过限速标准的最快速度匀速前行.
理想算法即采用Dijkstra经典算法求解以上规划问题中的tij,加入Ta项对疏散时间进行修正,进而求解MinT(式(1)).路径规划结果见表2.
Tab. 2 Comparison of the evacuation time calculated by three algorithms

表2 理想算法,延时-改进算法,逆行-改进算法规划结果比较

疏散算法 受灾点/个 避灾点/个 疏散组/个 到达避灾点/个 最长疏散时间/s 平均疏散时间/s 平均等待时间/s
理想算法 92 69 126 52 1413 548 68
延时-改进算法 92 69 127 52 2672 627 19
逆行-改进算法 92 69 126 51 2702 647 41

3 算法优化与结果对比分析

3.1 算法优化

在现实情况中,疏散过程很难达到理想的紧凑状态.因此,在理想算法的基础上考虑疏散过程中可能出现的延误:(1)疏散人群从步行改为车行;(2)车队转弯,通过道路交叉口时减速;(3)非匀速状态下的车辆缓行.本文将上述3种延误都视为或等价于发生在道路结点,即疏散组每通过一个道路结点会产生时间延误.
为了计算在结点处的延误时间,需对疏散组通过结点的过程有更准确的了解.故将疏散组的行进状态分为:运动(Moving),到达路口(To Cross),正在通过路口(Crossing),等待(Waiting)和到达(Reached),各种状态都包含疏散组在疏散网络中的位置信息和时间信息.当疏散组到达任一路口(ToCross状态)时,需判断"是否发生交通拥堵"及"是否需要调整路线",以决定疏散组将进入Crossing或Waiting状态.在疏散过程中,疏散组具有"当前状态(State)"和"下一状态(Next_State)"2组信息,并随时更新,通过各状态发生变化的时间可计算在节点处停滞的总时间.鉴此,设 T b 为通过道路结点延误的时间,加入 T b 项对理想算法进行修正,设计延时-改进算法,如式(2)所示.
Min T 2 = ∑ i = 1 M ∑ j = 1 N t ij x ij + T a + T b (2)
式中: Min T 2 为延时-改进算法的最短疏散总时间; T a 为交通拥堵等待时间.
借助应急疏散分析工具MiniGIS,对延时-改进算法所得路径结果进行动态模拟,观察疏散组的移动轨迹,发现因中途调整路线,部分疏散组会走"回头路",导致疏散路径相互重叠逆行,这样既不利于交通组织,又会造成资源浪费.鉴于逆行情况较少,易于检测和修改,而避免此类问题需考虑司机对研究区路网的了解程度及对路况的判断能力,进一步改进算法,数据要求和计算成本都会增加.综合考虑,仅对延时-改进算法结果中存在逆行问题的路径稍作调整,使规划结果更加合理.故本文设计逆行-改进算法如下:在满足规划约束的前提下,删除"回头路",手动调整延时-改进算法结果中存在逆行问题的路径,作为规划路径输入MiniGIS中重新计算疏散时间,并要求各疏散组严格遵循规划路径而行,即使遇到交通拥堵,为了保持整体的疏散秩序,不再自行调整路径.
以上对理想算法的优化过程见图2.其中,延时-改进算法流程以实线箭头表示,在延时-改进结果基础上,按逆行-改进算法流程(虚线箭头表示)进一步优化.3种算法路径规划结果见图3,疏散所需时间比较见表2.
Fig. 2 Flowchart of the optimization of routes planning algorithm

图2 路径规划算法优化流程

注:虚线箭头表示逆行-改进算法优化

Fig. 3 Comparison of the evacuation routes planned by three algorithms

图3 应急疏散算法路径求解结果

3.2 疏散时间比较

由表2可知,因过程简单,紧凑,理想算法的疏散总时间最短;延时-改进算法考虑了除交通拥堵以外的其他延误,在结果进一步趋于合理的同时,疏散总时间比理想算法增加了近一倍.逆行-改进算法疏散总时间比延时-改进算法增加了30 s,平均疏散时间增加了20 s,但避免了走"回头路"的 情况,便于疏散过程的组织与管理,也节约了疏散资源.
总的来看,理想算法实现了"最快路径"目标,延时-改进算法考虑的情景更加贴合实际情况,而逆行-改进算法在二者的基础上,舍弃部分"最快"路径,在时间次优的条件下,便于交通管理和资源节约,20~30 s的时间劣势可接受.本文认为其结果是此次路径规划的最优解.

3.3 典型优化路径比较

对算法优化过程中发生明显改动的路径做进一步分析.以77#疏散组为例(图4),由理想算法获得的路径如图4(a)所示,出发后途经4418 m(车行速度为13.3 m/s)到达43#避灾点,而延时-改进算法的结果是途经2962 m(车行速度为5 m/s)到达4#避灾点.比较道路属性发现,77#→43#路段比77#→4#路段道路等级高,通行速度快,理想算法在"最短时间"目标下,选择了通行快,距离远的避灾点;然而,多数疏散组都选择通行快的路径导致交通拥堵更频繁,且77#→43#路段上的道路结点较多,延时-改进算法(图4(b))在考虑通过道路结点时间延误以后,选择了通行速度慢,距离近的避灾点.相比之下,延时-改进算法在兼顾时间最短和距离最短方面做得更好.
Fig. 4 Evacuation routes of group 77# planned by the ideal and delay-improved algorithms respectively

图4 不同算法77#疏散组的疏散路径比较

以21#疏散组为例(图5),延时-改进算法的结果为:途经网络结点118→120→125→130→359→130→133,到达27#避灾点.由于在359处调整路线,需先返回至130,再经过133前往27.逆行-改进算法删去"回头路",路径更改为118→120→125→130→133.全长由3524 m缩短为3275 m,疏散时间由946 s缩短为905 s.
Fig. 5 Evacuation routes of group 21# planned by the delay-improved and retrogression-improved algorithms respectively

图5 不同算法21#疏散组的疏散路径比较

4 结论

(1)本文以疏散总时间最短为目标,考虑需求控制,容量限制,交通延误,公平分配和资源节约等约束条件,采用混合拆分疏散方法,构建了洪灾应急疏散路径规划模型;运用C#语言编写算法,求解最佳路径,所得结果对县域尺度的应急疏散路径选择均具有一定的指导意义.
(2)基于自主开发的应急疏散分析工具MiniGIS,对规划路径进行动态模拟,根据反馈逐次优化算法.其中,逆行-改进算法在贴近真实情景的同时,避免了因中途路径调整而出现的"回头路",在时间最短次优的条件下,便于疏散管理与资源节约,其结果被认为是此次应急疏散路径规划的最优解.
(3)本研究虽实现了县域尺度的洪灾应急疏散路径求解与优化,但对"疏散人群的抽象模型","背景交通流量","容量网络中的车辆变速","疏散需求等级"等现实问题的考虑还不够周全,因此,今后还需对算法进行更深入的研究,以得到更为准确完整的疏散路径.

The authors have declared that no competing interests exist.

References

Publishing order | Descend order by publishing year | Descend order by cited within
[1]
Murray-Tuite P, Wolshon B.Evacuation transportation modeling: an overview of research, development, and practice[J]. Transportation Research Part C: Emerging Technologies, 2013,27:25-45.This paper presents a review of highway-based evacuation modeling and simulation and its evolution over the past decade. The review includes the major components of roadway transportation planning and operations, including the current state of modeling in the forecasting of evacuation travel demand, distribution and assignment of evacuation demand to regional road networks to reach destinations, assignment of evacuees to various modes of transportation, and evaluation and testing of alternative management strategies to increase capacity of evacuation networks or manage demand. Although this discussion does not cover recent work in other modes used in evacuation such as air, rail, and pedestrian, this paper does highlight recent interdisciplinary modeling work in evacuation to help bridge the gap between the behavioral sciences and engineering and the application of emerging techniques for the verification, validation, and calibration of models. The manuscript also calls attention to special considerations and logistical difficulties, which have received limited attention to date. In addition to these concerns, the following future directions are discussed: further interdisciplinary efforts, including incorporating the medical community; using new technologies for communication of warnings and traffic condition information, data collection, and increased modeling resolution and confidence; using real-time information; and further model refinements and validation.

DOI

[2]
Takizawa A, Inoue M, Katoh N.An emergency evacuation planning model using the universally quickest flow[J]. The Review of Socio-network Strategies, 2012,6(1):15-28.In recent years, catastrophic disasters by massive earthquakes have been increasing in the world, and disaster management is required more than ever. In the case of disasters such as tsunamis, a slight delay in evacuation may deprive evacuees of life. In this article, we formalize the emergency evacuation planning model for evacuation from tsunamis and other disasters based on the idea of the universally quickest flow. We show that there does not always exist a universally quickest flow when the capacity constraint of refuges is taken into account. Therefore, we propose an alternative criterion that approximates a universally quickest flow, and presents an algorithm for finding an optimal flow for this criterion. Numerical experiments are carried out for the evacuation of a local city in Japan where tsunami damages are assumed to occur when a large earthquake occurs in the ocean nearby.

DOI

[3]
Renne J, Sanchez T, Litman T.Carless and special needs evacuation planning: a literature review[J]. Journal of Planning Literature, 2011,26(4):420-431.For this review, we included a wide range of literature related to emergency preparedness planning and information on the evacuation of carless residents, including minority, low income, elderly, disabled, and residents with limited mobility and health problems. The review includes sources that highlight best practices, and identify areas of weakness within the field of emergency preparedness with respect to the target population of this study. This review discusses different needs for different types of natural and human-induced disasters. It also discusses the role for an integrated, multimodal approach for evacuation planning to assist with evacuating people in the most efficient manner possible. This literature review serves to characterize the current state of thinking and practice on the subject of carless and special needs evacuation planning. The focus of the literature review is on the role of government and public agencies. Overall, the literature related to carless evacuation planning is multidisciplinary and wide ranging. The events surrounding Hurricane Katrina motivated this review of existing research and provided an opportunity to synthesize other earlier related research. The process is important for finding gaps in the contemporary understanding of these issues, especially given more recent evacuations.

DOI

[4]
Özdamar L, Demir O.A hierarchical clustering and routing procedure for large scale disaster relief logistics planning[J]. Transportation Research Part E: Logistics and Transportation Review, 2012,48(3):591-602.We describe a hierarchical cluster and route procedure (HOGCR) for coordinating vehicle routing in large-scale post-disaster distribution and evacuation activities. The HOGCR is a multi-level clustering algorithm that groups demand nodes into smaller clusters at each planning level, enabling the optimal solution of cluster routing problems. The routing problems are represented as capacitated network flow models that are solved optimally and independently by CPLEX on a parallel computing platform. The HOGCR preserves the consistency among parent and child cluster solutions obtained at consecutive levels. We assess the performance of the algorithm by using large scale scenarios and find satisfactory results.

DOI

[5]
Lahmar M, Assavapokee T, Ardekani S A.A dynamic transportation planning support system for hurricane evacuation[C]. Intelligent Transportation Systems Conference, ITSC'06, IEEE, 2006:612-617.

[6]
于德新,杨薇,杨兆升.重大灾害条件下基于GIS的最短路径改进算法[J].交通运输工程学报,2011,11(4):123-126.利用经典的Dijkstra算 法,对重大灾害条件下Dijkstra算法进行了改进,构建了惩罚因子函数,结合GIS软件二次开发模块,通过Visual C++6.0实现了复杂网络的分析功能。分析了重大灾害条件下节点数量对于道路可靠性以及最优路径选取的影响,综合考虑距离、行程时间以及节点数量因素, 证明了改进Dijkstra算法对于最优路径选择的优越性。分析结果表明:利用改进Dijkstra算法、经典Dijkstra算法计算出的路径节点数分 别为31、59,行程时间基本相同。可见,改进算法能有效减少疏散路径中的节点数量,降低车辆在节点处的延误损失和风险。

[ Yu D X, Yang W, Yang Z S.Forecast model of emergency traffic evacuation time under major disaster[J]. Journal of Jilin University (Engineer and Technology Edition), 2011,11(4):123-126. ]

[7]
Ye M W, Wang J, Huang J, et al.Methodology and its application for community-scale evacuation planning against earthquake disaster[J]. Natural Hazards, 2012,61(3):881-892.Abstract<br/>In urban area, popular and property is accumulated in a small area, potential risk of earthquake disaster in urban community is great. Pre-disaster emergency evacuation zoning has become a significant topic of disaster prevention and mitigation research. Based on the present layout of evacuation facilities and shelters as well as the evacuation demands in urban communities, a systematical methodology for occupant evacuation against earthquakes on community scale was developed by employing spatial analysis techniques of Geographical Information System (GIS). The methodology included the following aspects: the distribution analysis of emergency evacuation demands, the calculation of shelter space accessibility, and the optimization of evacuation destinations. This methodology was applied to Lujiazui Street in Pudong, a new district located in Shanghai, China. It was found that the proposed methodology could be used to formulate pre-event planning for earthquake disaster prevention and mitigation on a community scale, especially for organizing a rapid and smooth evacuation and optimizing the location allocation of shelters.<br/>

DOI

[8]
陈玲,林鹏.蓄滞洪区疏散最快时间研究[J].武汉大学学报(工学版),2012,45(4):468-471.中国是灾害严重的国家之一,应急疏散是减少灾害损失最重要的一环,传统的网络分析不能考虑网络路径的行走时间和路径通行能力随时间变化的特点,对于人员安全疏散网络优化具有很大的局限性.动态网络通过对静态网络在时间上的拓展,反映了灾时路径通行时间和通行容量随时间变化的特点,可以全面地优化疏散计划和路径.提出了基于动态网络流的优化算法,并应用于蓄滞洪区的安全疏散,通过疏散模拟、敏感性分析、疏散路线和场景研究分析等,为蓄滞洪区人员、物质的安全转移提供最优的路径及估算疏散时间.

[ Chen L, Lin P.Quickest evacuation of flood detention basin[J]. Journal of Wuhan University (Engineering Edition), 2012,45(4):468-471. ]

[9]
曾麦脉. 城市应急路网疏散规划的模型与算法研究[D].武汉:华中科技大学,2010:11-65.

[ Zeng M M.Research on model and algorithms of the traffic evacuation planning for city emergency [D]. Wuhan: Huazhong University of Science and Technology, 2010:11-65. ]

[10]
Lim G J, Zangeneh S, Baharnemati M R, et al.A capacitated network flow optimization approach for short notice evacuation planning[J]. European Journal of Operational Research, 2012,223(1):234-245.<p id="sp010">We present a capacity constrained network flow optimization approach for finding evacuation paths, flows and schedules so as to maximize the total evacuees for short notice evacuation planning (SNEP). Due to dynamic nature of this optimization problem, we first construct a time-expanded network that expands the static network over the planning horizon for every time interval. Since the resulting evacuation networks become extremely large to solve, we have developed Evacuation Scheduling Algorithm (ESA) to expedite the solution process. ESA utilizes Dijkstra&rsquo;s algorithm for finding the evacuation paths and a greedy algorithm for finding the maximum flow of each path and the schedule to execute the flow for each time interval. We show that the complexity of ESA is <span id="mmlsi14" class="mathmlsrc" onclick="submitCitation('/science?_ob=MathURL&amp;_method=retrieve&amp;_eid=1-s2.0-S0377221712004596&amp;_mathId=si14.gif&amp;_pii=S0377221712004596&amp;_issn=03772217&amp;_acct=C000228598&amp;_version=1&amp;_userid=10819599&amp;md5=5d8e07d11d38774cd7202185aa00be85')" style="cursor:pointer;" alt="Click to view the MathML source" title="Click to view the MathML source"><span class="formulatext" title="click to view the MathML source"><em>O</em>(|<em>N</em><sub><em>c</em></sub>|&middot;<em>n</em><sup>2</sup>)+<em>O</em>(|<em>N</em><sub><em>c</em></sub>|&middot;<em>m</em>&middot;<em>T</em>)</span></span>. Numerical experiments show a tremendous advantage of ESA over an exact algorithm (CCEP) in computation time by running up to 41,682 faster than CCEP. In many test network instances, CCEP failed to find a solution within 12&#xA0;hours while ESA converged to a solution in less than 0.03&#xA0;seconds.</p>

DOI

[11]
Baumnn N, Skutella M.Solving evacuation problems efficiently: earliest arrival flows with multiple sources[J]. Proceedings of FOCS, 2006:399-410.Earliest arrival flows capture the essence of evacuation planning. Given a network with capacities and transit times on the arcs, a subset of source nodes with supplies and a sink node, the task is to send the given supplies from the sources to the sink "as quickly as possible". The latter requirement is made more precise by the earliest arrival property which requires that the total amount of flow that has arrived at the sink is maximal for all points in time simultaneously. It is a classical result from the 1970s that, for the special case of a single source node, earliest arrival flows do exist and can be computed by essentially applying the successive shortest path algorithm for min-cost flow computations. While it has previously been observed that an earliest arrival flow still exists for multiple sources, the problem of computing one efficiently has been open for many years. We present an exact algorithm for this problem whose running time is strongly polynomial in the input plus output size of the problem

DOI

[12]
Naghawi H, Wolshon B.Transit-based emergency evacuation simulation modeling[J]. Journal of Transportation Safety and Security, 2010,2(2):184-201.Several recent mass evacuations, including those in advance of Hurricane Katrina in New Orleans and Hurricane Rita in Houston, have demonstrated the effects of limited planning for carless populations. The lack of planning left a significant portion of the mobility-limited population of both these cities unable to flee in advance of the storms. Since 2005, however, both of these cities (as well as others across the United States) have developed transit-assisted mass evacuation plans at various levels of detail. Because these plans are relatively recent and do not have a history of experience on which to base their performance, it is difficult to know how well, or even if, they will work. This article describes one of the first attempts to systematically model and simulate transit-based evacuation strategies. In it, the development of and the results gained from an application of the TRansportation ANalysis and SIMulation System (TRANSIMS) agent-based transportation simulation system to model assisted evacuation plans of New Orleans are described. In the research, average travel time and total evacuation time were used to compare the results of a range of conditions over a two-day evacuation period, including two alternative transit evacuation routing plans and four alternative network loading scenarios. Among the general findings of the research was that the most effective scenarios of transit-based evacuation were those that were carried out during time periods during which the auto-based evacuation was in its "lull" (nonpeak/overnight) periods. These conditions resulted in up to a 10% reduction in overall travel time and up to 45% reduction in the total evacuation time when compared to peak evacuation conditions. It was also found that routing buses to alternate arterial routes reduced the overall travel time by up to 52% and the total evacuation time by up to 14%.

DOI

[13]
Yi W, Özdamar L.A dynamic logistics coordination model for evacuation and support in disaster response activities[J]. European Journal of Operational Research, 2007,179(3):1177-1193.<p id="">This paper describes an integrated location-distribution model for coordinating logistics support and evacuation operations in disaster response activities. Logistics planning in emergencies involves dispatching commodities (e.g., medical materials and personnel, specialised rescue equipment and rescue teams, food, etc.) to distribution centres in affected areas and evacuation and transfer of wounded people to emergency units. During the initial response time it is also necessary to set up temporary emergency centers and shelters in affected areas to speed up medical care for less heavily wounded survivors. In risk mitigation studies for natural disasters, possible sites where these units can be situated are specified according to risk based urban structural analysis. Logistics coordination in disasters involves the selection of sites that result in maximum coverage of medical need in affected areas. Another important issue that arises in such emergencies is that medical personnel who are on duty in nearby hospitals have to be re-shuffled to serve both temporary and permanent emergency units. Thus, an optimal medical personnel allocation must be determined among these units. The proposed model also considers this issue.</p><p id="">The proposed model is a mixed integer multi-commodity network flow model that treats vehicles as integer commodity flows rather than binary variables. This results in a more compact formulation whose output is processed to extract a detailed vehicle route and load instruction sheet. Post processing is achieved by a simple routing algorithm that is pseudo-polynomial in the number of vehicles utilized, followed by the solution of a linear system of equations defined in a very restricted domain. The behavior and solvability of the model is illustrated on an earthquake scenario based on Istanbul&rsquo;s risk grid as well as larger size hypothetical disaster scenarios.</p>

DOI

[14]
Kaisar E I, Hess L, Palomo A B P. An emergency evacuation planning model for special needs populations using public transit systems[J]. Journal of Public Transportation, 2012,15(2):45-69.

[15]
叶明武. 沿海台风风暴潮灾害复合情景模拟与应急避难研究--以上海为例[D].上海:华东师范大学,2011:76-96.

[ Ye M W.Compounded scenarios simulation and emergency evacuation of storm surge disaster in coastal cities: a case study of Shanghai [D]. Shanghai: East China Normal University, 2011:76-96. ]

[16]
Chen X.Micro-simulation of hurricane evacuation strategies of Galveston Island[J]. The Professional Geographer, 2008,60(2):160-173.This article investigates the effectiveness of simultaneous and staged evacuation strategies for hurricane evacuations of Galveston Island using agent-based microsimulation techniques. In the simultaneous strategy the entire population is informed to evacuate simultaneously, whereas in a staged evacuation strategy, people are informed to evacuate in a sequence. The results suggest that (1) the most efficient staged evacuation strategy can help reduce the evacuation time for Galveston Island by approximately one hour, (2) previous studies might have underestimated the evacuation time of Galveston, and (3) an evacuation under the rapid response assumption does not necessarily lead to an effective evacuation.

DOI

[17]
赵宜宾,黄猛,张鹤翔.基于元胞自动机的多出口人员疏散模型的研究[J].系统工程学报,2012,27(4):439-444.在对多出口场所紧急疏散过程的 研究中着重考虑个体在决策时的主观智能作用,通过引入目标方向密度概率,出口影响因子概率,移动方向校正因子,建立了基于元胞自动机的多出口人员疏散模 型.通过对教室中学生的疏散行为的模拟仿真,表明所建模型在考虑上述三个因素时,模拟疏散的过程和结果更加合理,模型具有较好的实用性.

DOI

[ Zhao Y B, Huang M, Zhang H X.Study on multi-exit occupant evacuation model based on cellular automaton[J]. Journal of Systems Engineering, 2012,27(4):439-444. ]

[18]
He S, Zhang L, Song R, et al.Optimal transit routing problem for emergency evacuations[C]. Transportation Research Board 88th Annual Meeting, 2009:9-931.

[19]
崔娜. 台风灾害下无车群体疏散需求预测与集散设施选址研究[D].哈尔滨:哈尔滨工业大学,2012:1-23.

[ Cui N.Research on careless evacuation demand forecasting and pickup facility location design under typhoon disasters [D]. Harbin: Harbin Institute of Technology, 2012:1-23. ]

[20]
张巨,刘雨.MapInfo空间数据库技术分析[J].微型电脑应用,1999,15(10):12-14.通过与ＰＯＬＹＶＲＴ模型的比较，本文系统地分析了Ｍａｐ Ｉｎｆｏ 的空间数据模型。在此基础上，对ＭａｐＩｎｆｏ 的数据组织方法和索引机制加以深入探讨

[ Zhang J, Liu Y.Analyses of spatial data model of MapInfo[J]. Microcomputer Applications, 1999,15(10):12-14. ]

[21]
翁敏,毋河海,杜清运,等.基于道路网络知识的启发式层次路径寻找算法[J].武汉大学学报(信息科学版),2006,31(4):360-363.基于道路网络的知识,探讨了定义一个层次拓扑来帮助路径寻找及如何确定层次之间转换的入/出结点,并结合启发式技术来提高路径计算性能的路径寻找算法。实验表明,该方法不仅可以减少计算所需要的时间和空间,也会产生一个符合人类思维特点的解。

[ Weng M, Wu H H, Du Q Y, et al.A heuristic and hierarchical way finding algorithm based on the knowledge of road network[J]. Geomatics and Information Science of Wuhan University, 2006,31(4):360-363. ]

[22]
刘永志,张行南,张文婷,等.基于GIS和OREMS的洪灾避难系统[J].灾害学,2007,22(3):17-21.面对突发的灾害，人类采取避难转移的方式来减少生命和财产的损失。大范围的人口转移是一个十 分复杂的过程，必须有合理的计划和有效地利用现有的交通设施。提出了基于GIS和OREMS的洪灾避难系统来模拟洪灾的避难转移过程。根据洪灾危险区的统 计资料，应用基于GIS的风暴潮洪灾风险系统分析洪灾淹没范围、避难区域的人口分布、路网结构，使用OREMS避难交通模型模拟避难过程。以长兴岛为例进 行洪灾避难交通模拟，得到避难耗费时间，路网拥堵路段，并且在分析模拟结果的基础上对避难计划进行优化。

DOI

[ Liu Y Z, Zhang X N, Zhang W T, et al.Flood disaster evacuation system based on GIS and OREMS[J]. Journal of Catastrophology, 2007,22(3):17-21. ]

[23]
袁媛,汪定伟.灾害扩散实时影响下的应急疏散路径选择模型[J].系统仿真学报,2008,20(6):1563-1566.应急疏散的目的是要在灾害发生时将处于危险地带的人群尽快转移至 安全地带.由于灾害的扩散,疏散网络中各弧段上的路况将不断恶化,且不同的弧段受到灾害扩散影响的程度也将不同.为此,在提出的应急疏散路径选择模型中, 将通过疏散路径所需的总疏散时间最短作为优化目标,将各弧段上的通行速度表示为关于时间的连续递减函数,并对不同弧段的速度函数设置了不同的衰减参数.设 计了求解这一时变最短路问题的改进Dijkstra算法并给出了算法的正确性证明,仿真实例说明了模型和算法的有效性和可行性.

[ 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. ]

Options
Outlines

/

〈 〉