Abstract：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.
[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.
