Shortest path optimal algorithm for emergency evacuation based on cellular automata

doi:10.16265/j.cnki.issn1003-3033.2019.04.009

Abstract

Abstract: To plan the shortest emergency evacuation route scientifically and efficiently, an optimal algorithm for GSPCA was put forward by establishing a detour distance field against obstacles, and two solving modes of GSPCA_2D and GSPCA_3D were developed. To analyze the characteristics and applicability of GSPCA, this algorithm was compared with the heuristic search algorithm based on Euclidean distance (A^* algorithm) in the shortest path planning experiment. The results show that compared with A^* algorithm, GSPCA optimal algorithm is more comprehensive which can avoid the phenomenon of detours by clinging to the wall, and the shortest path is shortened by 12.39 % (GSPCA_2D) and 16.82 % (GSPCA_3D) on average; more importantly, with the terrain factors taken into consideration, GSPCA could select reasonable solution modes according to the terrain characteristics and practical application requirements.

Key words: emergency evacuation, global shortest path based on cellular automata (GSPCA), A^* algorithm, Euclidean distance, detour distance field

CLC Number:

X913

HE Mengnan, FU Yuling, CHEN Cheng, HE Hubin, LIN Yuqing, CHEN Qiuwen. Shortest path optimal algorithm for emergency evacuation based on cellular automata[J]. China Safety Science Journal, 2019, 29(4): 51-57.

References

[1] 吴坷, 宋英华, 吕伟. 城镇应急资源储备点选址与布局优化研究:考虑暴雨灾害和路径长度[J]. 中国安全科学学报, 2017, 27(9): 170-174.
WU Ke, SONG Yinghua, LYU Wei. Research on siting of urban emergency resources depots and layout optimization considering rainstorm disaster and distribution route[J]. China Safety Science Journal, 2017, 27(9): 170-174.
[2] 李国平,罗心然. 京津冀地区人口与经济协调发展关系研究[J]. 地理科学进展,2017, 36(1): 25-33.
LI Guoping, LUO Xinran. Coordinated development between population and economy in the Beijing-Tianjin-Hebei region[J]. Progress in Geography, 2017, 36(1): 25-33.
[3] MARCHESE F. A directional diffusion algorithm on cellular automata for robot path-planning[J]. Future Generation Computer Systems, 2002, 18(7): 983-994.
[4] 李梦雅,王军,沈航. 洪灾应急疏散路径规划算法优化[J]. 地球信息科学学报,2016,18(3): 362-368.
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.
[5] JASIKA N, ALISPAHIC N, ELMA A, et al. Dijkstra's shortest path algorithm serial and parallel execution performance analysis[C].2012 35^th International Convention on Information and Communication Technology, Electronics and Microelectronics, 2012: 1 602-1 611.
[6] HATZIKIROU H, BRUSCH L, SCHALLER C, et al. Prediction of traveling front behavior in a lattice-gas cellular automaton model for tumor invasion[J]. Computers and Mathematics with Applications, 2010, 59(7): 2 326-2 339.
[7] 刘春霞. CA模型下改进D^*算法的室内路径规划与避碰研究[D]. 合肥:合肥工业大学, 2016.
LIU Chunxia. Research on indoor path planning and avoidance based on improved D^* algorithm using CA model[D]. Hefei: Hefei University of Technology, 2016.
[8] LUATHEP Paramet, SUWANSUNTHON Arun, SUTTHIPHAN Suppakon, et al. Flood evacuation behavior analysis in urban areas[J]. Journal of the Eastern Asia Society for Transportation Studies, 2013, 10(11/12): 1 277-1 290.
[9] 张钟. 大规模图上的最短路径问题研究[D]. 合肥:中国科学技术大学, 2014.
ZHANG Zhong. Study of shortest path problem on large-scale graph[D]. Hefei: University of Science and Technology of China, 2014.
[10] 杨传勇. 欧氏障碍空间的最短路径问题解法(MA-ESPO)[D]. 武汉:武汉大学, 2005.
YANG Chuanyong. The solution on euclidean space shorest path with obstacles-Map Algebra ESPO[D]. Wuhan: Wuhan University, 2005.
[11] 任志国,郭健,李爱光,等. 元胞自动机最短路径算法优化[J]. 遥感学报, 2015, 19(1): 108-115.
REN Zhiguo, GUO Jian, LI Aiguang, et al. Optimal path algorithm enhancement based on cellular automaton[J]. Journal of Remote Sensing, 2015, 19(1): 108-115.
[12] 何梦男. 基于元胞自动机的城市洪涝人群疏散模型研究[D]. 重庆:重庆交通大学, 2018.
HE Mengnan. Study on urban flood evacuation model based on cellular automata[D]. Chongqing: Chongqing Jiaotong University, 2018.
[13] KOMAROV A, PALENOVA M, SMIRNOVA O. The concept of discrete description of plant ontogenesis and cellular automata models of plant populations[J]. Ecological Modelling, 2003, 170(2): 427-439.
[14] ABDELGHANY A, ABDELGHANY K, MAHMASSANI H, et al. Modeling framework for optimal evacuation of large-scale crowded pedestrian facilities[J]. European Journal of Operational Research, 2014, 237(3): 1 105-1 118.

[1]	FENG Sihai, WANG Zhijie, DENG Jie, XIN Yaojiao, HE Yuanhua. Cellular automata model for emergency evacuation considering panic factor [J]. China Safety Science Journal, 2022, 32(4): 148-154.
[2]	YU Ping. Modeling and simulation of cruise emergency evacuation process for layout optimization [J]. China Safety Science Journal, 2021, 31(9): 142-149.
[3]	SONG Yinghua, WANG Yaxin, MA Yaping, LYU Wei. Research on multi-mode cooperative emergency evacuation scheduling considering types of disaster victims [J]. China Safety Science Journal, 2021, 31(11): 135-140.
[4]	WANG Lixiao, YU Jiangbo, SUN Xiaohui. Decision-making modeling of metro emergency evacuation behavior considering psychological heterogeneity [J]. China Safety Science Journal, 2021, 31(10): 119-126.
[5]	JIANG Xue, YANG Huan, ZHANG Peihong. Emergency evacuation decision optimization for commercial pedestrian streets based on ant colony algorithm [J]. China Safety Science Journal, 2021, 31(10): 144-151.
[6]	LYU Wei, QIN Shuangshuang, MU Zhiguo, WANG Jinghui, JIANG Yajuan, LI Jiawei. Simulation study on evacuation of CRH380AL high-speed train and its influencing factors [J]. China Safety Science Journal, 2020, 30(8): 164-170.
[7]	YANG Dongdong, CHEN Guoming, SHI Jihao, DAI Ziliang. A dynamic assessment method for consequences of explosion accidents on offshore platforms [J]. China Safety Science Journal, 2020, 30(11): 121-126.
[8]	ZHENG Xiazhong, CAI Lili, ZHANG Ming, JIN Lianghai, CHEN Yan. Emergency evacuation path optimization model under multi-export conditions [J]. China Safety Science Journal, 2019, 29(3): 180-186.
[9]	MA Yaping, LI Lihua, ZHANG Hui. Study on evacuation behaviors of primary school pupils considering social relations [J]. China Safety Science Journal, 2019, 29(12): 144-151.
[10]	WANG Jingchun, ZHAO Fuquan, WANG Binghua, HE Xusheng. Resilience evaluation for deep foundation pit of metro station under influence of multiple factors [J]. China Safety Science Journal, 2019, 29(10): 154-159.
[11]	WANG Yanfu, LI Biao, QIN Tao, GONG Xiaofeng. Simulation of evacuation from offshore drilling platform in fire [J]. China Safety Science Journal, 2018, 28(3): 68-73.
[12]	CHEN Shu, SHEN Haobo, WANG Yue, WANG Jianping, LI Zhi. Strategy for emergency evacuation from vertical ship lift on initial fire [J]. China Safety Science Journal, 2018, 28(2): 187-192.
[13]	WANG Qiquan. Research on intelligent early-warning of crowded stampede accidents vulnerable areas in subway [J]. China Safety Science Journal, 2018, 28(11): 162-167.
[14]	LIU Qing, YIN Tongle, WANG Lei, RONG Minmin. Organization optimization decision making model for emergency evacuation of overstocked ships in restricted waters [J]. China Safety Science Journal, 2018, 28(1): 173-178.
[15]	LIU Huilin, SHEN Fei. Evacuation route planning model based on toxic injury index [J]. China Safety Science Journal, 2018, 28(1): 179-184.