基于改进A*算法的多层邮轮疏散系统仿真

doi:10.16182/j.issn1004731x.joss.21-0075

摘要/Abstract

摘要：

为解决海上航行应急疏散效率低下的问题，提出一种基于改进A*算法的应急疏散系统。以网络流模型为基础，采用邻接节点的遍历方式完成路径搜索，并在代价值的计算中加入路径人员密度和路径障碍物的影响，使算法更具实用性。为提升算法效率，对网络进行节点优化，给出单层多出口情况下的多路径择优方案，并考虑在路径发生拥堵时进行二次规划。仿真结果表明：该系统能够为多层大型邮轮上的人员提供一条有效的疏散路径，不仅在安全性方面可以有效避免路段拥堵情况，而且在疏散时间方面较传统A*算法更短，疏散效果更好。

关键词: 应急疏散, A*算法, 路径规划, 网络流模型

Abstract:

Aiming at the low efficiency of emergency evacuation at sea, an emergency evacuation system based on improved A* algorithm is proposed. Based on the network flow model, the traversal mode of the adjacency node is used to complete the path search, and the influence of the path personnel density and path obstacles is added to the calculation of the cost, which makes the algorithm more practical. In order to improve the efficiency of the algorithm, the node optimization of the network is carried out, and a multi-path optimal scheme is proposed in the case of single layer with multiple exits, and the quadratic planning is considered in case of congestion in the path. The results show that the system can provide an effective evacuation path for the multi-storey large cruise ships. It can not only effectively avoid road congestion, but also shorten the evacuation time. The evacuation effect is better than the traditional A* algorithm.

Key words: emergency evacuation, A* algorithm, path planning, network flow models

中图分类号:

TP391.9

蒙盾, 胡卓, 张华军. 基于改进A^*算法的多层邮轮疏散系统仿真[J]. 系统仿真学报, 2022, 34(6): 1375-1382.

Dun Meng, Zhuo Hu, Huajun Zhang. Simulation of Multi-layer Ship Evacuation System Based on Improved A* Algorithm[J]. Journal of System Simulation, 2022, 34(6): 1375-1382.

图/表 11

图1

图2

图3

图4

表1

图5

图6

图7

图8

图9

图10

参考文献 20

1	高飞. 客轮人员应急疏散模型构建及仿真研究[D]. 大连: 大连海事大学, 2017.
	Gao Fei. Construction and Simulation Study of Emergency Evacuation Model for Passenger Ship Personnel [D]. Dalian: Dalian Maritime University, 2017.
2	郝会龙, 任鸿翔, 肖方兵. 基于A*算法的虚拟船员路径规划仿真[J]. 计算机工程与设计, 2015, 36(3): 733-737.
	Hao Huilong, Ren Hongxiang, Xiao Fangbing. Simulation of Virtual Crew Path Planning Based on A* Algorithm [J]. Computer Engineering and Design, 2015, 36(3): 733-737.
3	阳小涛, 杨克俭, 闫春香. 虚拟人几何建模及运动控制方法的研究[J]. 计算机与数字工程, 2008, 36(8): 132-135.
	Yang Xiaotao, Yang Kejian, Yan Chunxiang. Research on Geometric Modeling and Motion Control of Virtual Human [J]. Computer and Digital Engineering, 2008, 36(8): 132-135.
4	王军华, 吕克志. 面向艺术与设计虚拟人技术比较研究[J]. 计算机系统应用, 2009, 18(5): 123-127.
	Wang Junhua, Kezhi Lü. Comparative Study on Virtual Human Technology for Art and Design [J]. Computer System Application, 2009, 18(5): 123-127.
5	Dou Z, Mebarki A, Cheng Y, et al. Review on the Emergency Evacuation in Chemicals-Concentrated Areas (Review)[J]. Journal of Loss Prevention in the Process Industries(S0950-4230), 2019, 60: 35-45.
6	孙迪, 周进, 高学英, 等. 地铁站内行人疏散路径选择仿真研究[J]. 系统仿真学报, 2019, 31(9): 1819-1826.
	Sun Di, Zhou Jin, Gao Xueying, et al. Simulation Research on Pedestrian Evacuation Path Selection in the Metro Station[J]. Journal of System Simulation, 2019, 31(9): 1819-1826.
7	宋英华, 张宇, 霍非舟, 等. 考虑避让行为的人员疏散元胞自动机模型研究[J]. 系统仿真学报, 2020, 32(6): 975-981.
	Song Yinghua, Zhang Yu, Huo Feizhou, et al. Study on Evacuation Cellular Automaton Model Considering Avoidance Behavior[J]. Journal of System Simulation, 2020, 32(6): 975-981.
8	Kebel A, WahleJetal Klupfel H. Microscopic Simulation of Pedestrian Crowd Motion Pedestrian and Evacuation[C]//Pedestrian and Evacuation Dynamics 2001. Berlin Springer: Verlag Heidelberg, 2002: 193-200.
9	Andreas Schadscheider. Cellular Automaton Approach to Pedestrian Dynamics Theory Pedestrian and Evacuation[C]//Pedestrian and Evacuation Dynamics 2001. Berlin Springer: Verlag Heideberg, 2002: 75-85.
10	邓媛媛, 郑利平, 蔡瑞文. 社会行为驱动的疏散仿真方法研究[J]. 系统仿真学报, 2020, 32(1): 130-141.
	Deng Yuanyuan, Zheng Liping, Cai Ruiwen. Research on Evacuation Simulation Method Considering Social Behavior[J]. Journal of System Simulation, 2020, 32(1): 130-141.
11	Helbing D, Farkas I, Vicsek T. Simulating Dynamical Features of Escape Panic[J]. Nature(S1476-4687), 2000, 407(6803): 487-490.
12	杨琪, 王维莉, 胡志华. 突发事件下邮轮应急疏散模拟及其验证[J]. 大连海事大学学报, 2018, 44(2): 27-32.
	Yang Qi, Wang Weili, Hu Zhihua. Simulation and Verification of Cruise Ship Emergency Evacuation Under Emergencies [J]. Journal of Dalian Maritime University, 2018, 44(2): 27-32.
13	谌海云, 陈华胄, 刘强. 基于改进人工势场法的多无人机三维编队路径规划[J]. 系统仿真学报, 2020, 32(3): 414-420.
	Chen Haiyun, Chen Huazhou, Liu Qiang. Multi-UAV 3D Formation Path Planning Based on Improved Artificial Potential Field[J]. Journal of System Simulation, 2020, 32(3): 414-420.
14	杨卫, 曾亮, 康新晨. 基于蚁群算法的群机器人自组织聚集行为建模[J]. 系统仿真学报, 2020, 32(2): 191-200.
	Yang Wei, Zeng Liang, Kang Xinchen. Self-Organizing Aggregation Behavior Modeling of Swarm Robots Based on Ant Colony Algorithm[J]. Journal of System Simulation, 2020, 32(2): 191-200.
15	何明, 陈国华, 杜有翔, 等. 基于Dijkstra算法的火灾环境下人员疏散仿真方法[J]. 中国安全科学学报, 2010, 20(12): 46-51.
	He Ming, Chen Guohua, Du Youxiang, et al. A Simulation Method of Personnel Evacuation Under Fire Environment Based on Dijkstra algorithm [J].Chinese Journal of Safety Science, 2010, 20(12): 46-51.
16	Fu B, Chen L, Zhou Y, et al. An Improved A* Algorithm for the Industrial Robot Path Planning with High Success Rate and Short Length [J]. Robotics ＆ Autonomous Systems(S0921-8890), 2018, 106: 26-37.
17	Zhang H M, Li M L, Yang L. Safe Path Planning of Mobile Robot Based on Improved A* Algorithm in Complex Terrains[J]. Algorithms(S1999-4893), 2018, 11(4): 44-50.
18	靳海亮, 王赢乐, 袁鸣, 等. 改进A*的高层建筑逃生路径规划算法研究[J]. 测绘通报, 2019(11): 17-21.
	Jin Hailiang, Wang Yingle, Yuan Ming, et al. Research on Improved A* High-Rise Building Escape Path Planning Algorithm [J]. Bulletin of Surveying and Mapping, 2019(11): 17-21.
19	Fruin J J. Design for Pedestrians a Level of Service[D]. New York: Polytechnic Institute of Brooklyn, 1970.
20	张学锋, 白晨曦. 双层教学楼人员疏散仿真研究[J]. 系统仿真学报, 2017, 29(5): 1070-1076.
	Zhang Xuefeng, Bai Chenxi. Study of Crowd Evacuation in Two-storey Teaching Building[J]. Journal of System Simulation, 2017, 29(5): 1070-1076.

路径号	走向
1	P_start→stair_{1_1}→stair_{2_1}→stair_{3_1}→P_des
2	P_start→stair_{1_1}→stair_{2_1}→stair_{2_2}→stair_{3_2}→P_des
3	P_start→stair_{1_2}→stair_{2_2}→stair_{3_2}→P_des
4	P_start→stair_{1_2}→stair_{2_2}→stair_{2_1}→stair_{3_1}→P_des

[1]	张莉, 张惠珍, 刘冬, 陆雨欣. 考虑紧迫度的应急物资调度及粒子群算法求解[J]. 系统仿真学报, 2022, 34(9): 1988-1998.
[2]	李腾, 丁佩佩, 刘金芳. 货到人拣选系统多阶段可穿行多AGV路径规划[J]. 系统仿真学报, 2022, 34(7): 1512-1523.
[3]	陆淼嘉, 黄承媛, 滕靖. 基于多智能体的网购生鲜无人车配送调度仿真[J]. 系统仿真学报, 2022, 34(6): 1185-1195.
[4]	张森, 张孟炎, 邵敬平, 普杰信. 基于随机策略搜索的多机三维路径规划方法[J]. 系统仿真学报, 2022, 34(6): 1286-1295.
[5]	倪凌佳, 黄晓霞, 李红旮, 张子博. 基于协作式深度强化学习的火灾应急疏散仿真研究[J]. 系统仿真学报, 2022, 34(6): 1353-1366.
[6]	梁江涛, 王慧琴. 基于改进蚁群算法的建筑火灾疏散路径规划研究[J]. 系统仿真学报, 2022, 34(5): 1044-1053.
[7]	邓向阳, 张立民, 方伟, 汤淼. 基于双向汇聚引导蚁群算法的机器人路径规划[J]. 系统仿真学报, 2022, 34(5): 1101-1108.
[8]	李兆强, 张时雨. 基于快速RRT算法的三维路径规划算法研究[J]. 系统仿真学报, 2022, 34(3): 503-511.
[9]	王启明, 宗高强, 胥津铭. 多段式自动泊车最优路径规划与仿真分析[J]. 系统仿真学报, 2022, 34(2): 385-395.
[10]	陈志梅, 李敏, 邵雪卷, 赵志诚. 基于改进RRT算法的桥式起重机避障路径规划[J]. 系统仿真学报, 2021, 33(8): 1832-1838.
[11]	李颀, 汪伟. 多全向轮协同分拣平台的路径规划[J]. 系统仿真学报, 2021, 33(3): 698-709.
[12]	郭海湘, 曾杨, 陈卫明. 基于社会力模型的多出口室内应急疏散仿真研究[J]. 系统仿真学报, 2021, 33(3): 721-731.
[13]	黄晓冬, 苑海涛, 毕敬, 刘涛. 基于DQN的海战场舰船路径规划及仿真[J]. 系统仿真学报, 2021, 33(10): 2440-2448.
[14]	林彬, 韩光辉, 宋晨晨, 张雅静. 基于辐射扫描算法的机器人路径规划与仿真[J]. 系统仿真学报, 2021, 33(1): 84-90.
[15]	朱大奇, 朱婷婷, 颜明重. 基于改进神经网络的多AUV全覆盖路径规划[J]. 系统仿真学报, 2020, 32(8): 1505-1514.