基于元胞自动机的应急疏散最短路径优化算法

doi:10.16265/j.cnki.issn1003-3033.2019.04.009

中国安全科学学报 ›› 2019, Vol. 29 ›› Issue (4): 51-57.doi: 10.16265/j.cnki.issn1003-3033.2019.04.009

基于元胞自动机的应急疏散最短路径优化算法

何梦男¹, 付瑜玲^1,2, 陈诚^**1 工程师, 何湖滨¹, 林育青¹, 陈求稳¹ 研究员

1 南京水利科学研究院生态环境研究中心,江苏南京 210029;
2 重庆交通大学河海学院,重庆 400074

收稿日期:2018-12-19 修回日期:2019-01-28 出版日期:2019-04-28 发布日期:2020-11-04
通讯作者: ** 陈诚(1990—),男,江苏宿迁人,硕士,工程师,从事城市水环境和生态环境遥感研究。E-mail: chencheng@nhri.cn。
作者简介:何梦男 (1993—),男,重庆人,硕士,工程师,主要从事洪水灾害人员疏散和城市水环境模型研究。E-mail: mnhe@nhri.cn。
基金资助:
国家自然科学基金青年基金资助(51609142);中央级公益性科研院所基金资助(Y918011,Y919006);江苏省双创团队项目(SC917001)。

Shortest path optimal algorithm for emergency evacuation based on cellular automata

HE Mengnan¹, FU Yuling^1,2, CHEN Cheng¹, HE Hubin¹, LIN Yuqing¹, CHEN Qiuwen¹

1 Center for Eco-Environmental Research, Naning Hydraulic Research Institute, Nanjing Jiangsu 210029, China;
2 College of Hehai, Chongqing Jiaotong University, Chongqing 400074, China

Received:2018-12-19 Revised:2019-01-28 Online:2019-04-28 Published:2020-11-04

摘要/Abstract

摘要： 为科学、高效地规划应急疏散最短路径,建立人员对障碍物的绕行距离场,提出一种基于元胞自动机的全局最短路径(GSPCA)优化算法;设置GSPCA_2D和GSPCA_3D等2种求解模式,并将该算法与基于欧氏距离的启发式搜索算法(A^*算法)进行最短路径规划对比试验,分析GSPCA算法的特点和适用性。结果表明:与A^*算法相比,GSPCA优化算法搜索结果全局性更好,可避免出现贴壁绕行现象,其最短路径平均缩短12.39 %(GSPCA_2D)、16.82 %(GSPCA_3D);GSPCA算法能考虑地形因素,可根据地形特征和实际应用需求合理选择求解模式。

关键词: 应急疏散, 基于元胞自动机的全局最短路径(GSPCA), A^*算法, 欧氏距离, 绕行距离场

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

中图分类号:

X913

何梦男, 付瑜玲, 陈诚, 何湖滨, 林育青, 陈求稳. 基于元胞自动机的应急疏散最短路径优化算法[J]. 中国安全科学学报, 2019, 29(4): 51-57.

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.

参考文献

[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]	凤四海, 王志杰, 邓捷, 辛耀娇, 贺元骅. 引入恐慌因素的元胞自动机应急疏散模型[J]. 中国安全科学学报, 2022, 32(4): 148-154.
[2]	于萍. 邮轮应急疏散过程建模、模拟与布局优化分析^*[J]. 中国安全科学学报, 2021, 31(9): 142-149.
[3]	宋英华, 汪雅馨, 马亚萍, 吕伟. 考虑灾民类型多模式协同应急疏散调度研究^*[J]. 中国安全科学学报, 2021, 31(11): 135-140.
[4]	王立晓, 于江波, 孙小慧. 考虑心理异质性的地铁应急疏散行为决策建模^*[J]. 中国安全科学学报, 2021, 31(10): 119-126.
[5]	姜雪, 杨欢, 张培红. 基于蚁群算法的商业步行街应急疏散决策优化^*[J]. 中国安全科学学报, 2021, 31(10): 144-151.
[6]	吕伟, 秦霜霜, 穆治国, 汪京辉, 姜雅娟, 李加伟. CRH380AL型高铁列车应急疏散及影响因素模拟研究[J]. 中国安全科学学报, 2020, 30(8): 164-170.
[7]	杨冬冬, 陈国明, 师吉浩, 戴子良. 海洋平台爆炸事故后果动态评估方法[J]. 中国安全科学学报, 2020, 30(11): 121-126.
[8]	郑霞忠, 蔡莉莉, 张明, 晋良海, 陈艳. 多出口条件下应急疏散路径优化模型[J]. 中国安全科学学报, 2019, 29(3): 180-186.
[9]	马亚萍, 李丽华, 张辉. 考虑社会关系影响的小学生疏散行为研究[J]. 中国安全科学学报, 2019, 29(12): 144-151.
[10]	王景春, 赵福全, 王炳华, 何旭升. 多因素影响下的地铁车站深基坑韧性评估[J]. 中国安全科学学报, 2019, 29(10): 154-159.
[11]	王彦富, 李彪, 秦桃, 龚晓峰. 海洋钻井平台火灾疏散仿真研究[J]. 中国安全科学学报, 2018, 28(3): 68-73.
[12]	陈述, 申浩播, 王越, 王建平, 李智. 垂直升船机初期火灾应急疏散策略研究[J]. 中国安全科学学报, 2018, 28(2): 187-192.
[13]	王起全. 地铁拥挤踩踏事故脆弱性区域智能化预警研究[J]. 中国安全科学学报, 2018, 28(11): 162-167.
[14]	刘惠临, 沈非. 基于毒性伤害指标的疏散路径规划模型[J]. 中国安全科学学报, 2018, 28(1): 179-184.
[15]	郑霞忠, 向蕾蕾, 晋良海, 陈述, 陈雁高. 考虑人-环因素的地铁站疏散速度修正模型与仿真[J]. 中国安全科学学报, 2017, 27(8): 19-24.

基于元胞自动机的应急疏散最短路径优化算法

Shortest path optimal algorithm for emergency evacuation based on cellular automata

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

本文评价