-
With the improvement of people's living standards, large-scaled public activities have increased considerably, and the emergency probability has increased greatly. When an emergency occurs, the emergency evacuation can effectively reduce casualties and economic losses. Therefore, how to quickly evacuate crowd is a current research hotspot in this field. The path planning of emergency evacuation is one of the effective ways to implement the crowd evacuation. Aiming at the problem of path planning for emergency evacuation and taking the grid map as the background, the ant colony cellular optimization (ACCO) algorithm is proposed as the path planning algorithm based on the cellular automata theory and ant colony algorithm. Firstly, in order to solve the problem of inconsistent time steps in the quadrilateral grid map, the grid map based on hexagonal cell is established and the ACCO algorithm is developed based on the hexagonal grid map. And the method of solving grid coordinate is given. Then, in order to improve the convergence speed and search ability of the ACCO algorithm, the static field is used to optimize the heuristic function, and the segment update rule is used to optimize the pheromone update method. Finally, the parameters of ACCO algorithm are optimized through the particle swarm optimization (PSO) algorithm. The method of designing the fitness evaluation function is proposed, and the optimal combination of parameters of the ACCO algorithm is implemented according to the fitness function. In order to verify the scientificity and effectiveness of the algorithm proposed in this research and also to systematically verify the optimization strategy, in this research the exhibition hall on the B-deck of a large cruise ship is used as the engineering background, and the traditional algorithm and the ACCO algorithm are adopted to perform the simulations. The simulation results show that compared with the traditional quadrilateral grid, the hexagonal grid proposed in this research unifies the simulation time step and can be used as the division method of the simulation environment. At the same time, the ACCO algorithm can effectively perform the evacuation path planning, and the optimization strategy proposed in this research not only acceletates the search speed, but also increases the solution space and improves the search ability, which can effectively avoid falling into the local optimal solution.
-
Keywords:
- path planning /
- population evacuation /
- ant colony cellular optimization /
- partical swarm optimization
[1] Dorigo M, Gambardella L M 1997 Biosystems 43 73
Google Scholar
[2] Duchoň F, Babinec A, Kajan M, Beňo P, Florek M, Fico T, Jurišica L 2014 Procedia Eng. 96 59
Google Scholar
[3] Cui S G, Wang H, Li J G 2013 Third International Conference on Instrumentation & Measurement, Computer, Communication and Control Shenyang, China, September 21–23, 2013 p200
[4] Chaari I, Koubaa A, Bennaceur H, Ammar A, Trigui S, Tounsi M, Shakshuki E, Youssef H 2014 Procedia Comput. Sci. 32 604
Google Scholar
[5] Dorigo M, Gambardella L M 1997 IEEE Trans. Evol. Comput. 1 53
Google Scholar
[6] Stützle T, Hoos H 1999 Meta-heuristics (Boston: Springer) p313
[7] Stützle T, Hoos H 1998 Artificial Neural Nets and Genetic Algorithms Norwich, England, April 2–4, 1998 p245
[8] 张玮, 马炎, 赵捍东 2019 控制与决策 34 335
Zhang W, Ma Y, Zhao H D 2019 Control Decis. 34 335
[9] 胡启国, 胡小华, 吴泳龙 2013 重庆交通大学学报 (自然科学版) 32 543
Hu Q G, Hu X H, Wu Y L 2013 J. Chongqing Jiaotong Univ.(Natural Science). 32 543
[10] Hsu C C, Hou R Y, Wang W Y 2013 IEEE International Conference on Systems, Man, and Cybernetics Manchester, United Kingdom, October 13–16, 2013 p2777
[11] 李冬妮, 贾晓宇, 陈琳, 郑丹, 陶军 2017 北京理工大学学报 37 704
Li D N, Jia X Y, Chen L L, Zheng D, Tao J 2017 Trans. Beijing Inst. Technol. 37 704
[12] 王晓燕, 杨乐, 张宇, 孟帅 2018 控制与决策 33 1775
Wang X Y, Yang L, Zhang Y, Meng S 2018 Control Decis. 33 1775
[13] Zhao K, Sun X, Wang D 2017 Bull. Sci. Technol. 33 76
[14] 周金旺, 刘慕仁, 孔令江, 邝华 2009 58 3001
Google Scholar
Zhou W C, Liu M R, Kong L J, Kuang H 2009 Acta Phys. Sin. 58 3001
Google Scholar
[15] 刘毅, 沈斐敏 2018 控制与决策 33 1598
Liu Y, Shen F M 2018 Control Desci. 33 1598
[16] 董力耘, 陈立, 段晓茵 2015 64 220505
Google Scholar
Dong L Y, Chen L, Duan X Y 2015 Acta Phys. Sin. 64 220505
Google Scholar
[17] 禹尔东, 吴正, 郭明旻 2014 63 094501
Google Scholar
Yu E D, Wu Z, Guo M W 2014 Acta Phys. Sin. 63 094501
Google Scholar
[18] 陈亮, 郭仁拥, 塔娜 2013 62 050506
Google Scholar
Chen L, Guo R Y, Ta N 2013 Acta Phys. Sin. 62 050506
Google Scholar
[19] 岳昊, 邵春福, 姚智胜 2009 58 4523
Google Scholar
Yue H, Shao C F, Yao Z S 2009 Acta Phys. Sin. 58 4523
Google Scholar
[20] 张磊, 岳昊, 李梅, 王帅, 米雪玉 2015 64 060505
Google Scholar
Zhang L, Yue H, Li M, Wang S, Mi X Y 2015 Acta Phys. Sin. 64 060505
Google Scholar
[21] 谢积鉴, 薛郁 2012 61 194502
Google Scholar
Xie J J, Xue Y 2012 Acta Phys. Sin. 61 194502
Google Scholar
[22] Eberhart R, Kennedy J 1995 MHS'95. Proceedings of the Sixth International Symposium on Micro Machine and Human Science Nagoya, Japan, October 4-6, 1995 p39
[23] Eberhart R C, Shi Y 2000 Proceedings of the 2000 Congress on Evolutionary Computation La Jolla, USA, July 16–19, 2000 p84
-
图 1 栅格示意图 (a) Moore型邻域; (b) 传统四边形栅格; (c) 改进六边形栅格
Figure 1. Grid schematic: (a) Mooretype neighborhood; (b) traditional quadrilateral grid; (c) improved hexagon grid.
图 2 算法流程图
Figure 2. Simulation flow chart.
图 3 某邮轮B甲板构造图
Figure 3. B-deck structure diagram of a cruise ship.
图 4 展厅构造与仿真图 (a) 展厅构造图; (b) 仿真环境图
Figure 4. Exhibition hall construction and simulation: (a) Exhibition hall structure; (b) simulation environment diagram.
图 5 粒子适应度值曲线 (a) 参数组1; (b) 参数组2
Figure 5. The fitness value curves: (a) Parameter group 1; (b) parameter group 2.
图 6 仿真效果图
Figure 6. Simulation effect chart.
图 7 路径长度对比 (a) 传统算法路径统计; (b) 基于经验参数的ACCO算法路径统计; (c) 启发函数优化后的路径统计; (d) 信息素更新优化的路径统计; (e) 基于参数组1的路径统计; (f) 基于参数组2的路径统计
Figure 7. Path length comparison: (a) The path statistics for traditional algorithm; (b) the path statistics for ACCO algorithm with experience; (c) the path statistics for only optimizing heuristic function; (d) the path statistics for only optimizing pheromone update methods; (e) the path statistics for parameter group 1; (f) the path statistics for parameter group 2.
图 8 路径长度迭代对比 (a) 传统算法; (b) ACCO算法
Figure 8. Iteration comparison of path length: (a) Traditional algorithm; (b) ACCO algorithm.
表 1 PSO算法参数取值
Table 1. The parameters of PSO algorithm.
参数名称 参数取值 备注 c1, c2 1.49445 Tmax 50 最大迭代次数 ω $ 0.5 \times (T_{\max} - t)/ T_{\max} + 0.2 $ t 为当前迭代次数 λ1 0.7 λ2 0.1 λ3 0.1 λ4 0.1 
DownLoad: CSV
表 2 参数求解结果
Table 2. Parameter solution results.
参数名称 α β ρ 参数组1 3.50 8.05 0.68 参数组2 1.35 8.50 0.36
DownLoad: CSV
表 3 算法性能对比表
Table 3. Performances comparison of algorithms.
时间复杂度 运行时间/s 收敛
速率最优性/个 可重
复性传统
算法O(Nmaxn2m) 94.157737 –0.93 762 5% 本文
算法O(Nmaxn2m) 111.091862 –1.22 571 30%
DownLoad: CSV
-
[1] Dorigo M, Gambardella L M 1997 Biosystems 43 73
Google Scholar
[2] Duchoň F, Babinec A, Kajan M, Beňo P, Florek M, Fico T, Jurišica L 2014 Procedia Eng. 96 59
Google Scholar
[3] Cui S G, Wang H, Li J G 2013 Third International Conference on Instrumentation & Measurement, Computer, Communication and Control Shenyang, China, September 21–23, 2013 p200
[4] Chaari I, Koubaa A, Bennaceur H, Ammar A, Trigui S, Tounsi M, Shakshuki E, Youssef H 2014 Procedia Comput. Sci. 32 604
Google Scholar
[5] Dorigo M, Gambardella L M 1997 IEEE Trans. Evol. Comput. 1 53
Google Scholar
[6] Stützle T, Hoos H 1999 Meta-heuristics (Boston: Springer) p313
[7] Stützle T, Hoos H 1998 Artificial Neural Nets and Genetic Algorithms Norwich, England, April 2–4, 1998 p245
[8] 张玮, 马炎, 赵捍东 2019 控制与决策 34 335
Zhang W, Ma Y, Zhao H D 2019 Control Decis. 34 335
[9] 胡启国, 胡小华, 吴泳龙 2013 重庆交通大学学报 (自然科学版) 32 543
Hu Q G, Hu X H, Wu Y L 2013 J. Chongqing Jiaotong Univ.(Natural Science). 32 543
[10] Hsu C C, Hou R Y, Wang W Y 2013 IEEE International Conference on Systems, Man, and Cybernetics Manchester, United Kingdom, October 13–16, 2013 p2777
[11] 李冬妮, 贾晓宇, 陈琳, 郑丹, 陶军 2017 北京理工大学学报 37 704
Li D N, Jia X Y, Chen L L, Zheng D, Tao J 2017 Trans. Beijing Inst. Technol. 37 704
[12] 王晓燕, 杨乐, 张宇, 孟帅 2018 控制与决策 33 1775
Wang X Y, Yang L, Zhang Y, Meng S 2018 Control Decis. 33 1775
[13] Zhao K, Sun X, Wang D 2017 Bull. Sci. Technol. 33 76
[14] 周金旺, 刘慕仁, 孔令江, 邝华 2009 58 3001
Google Scholar
Zhou W C, Liu M R, Kong L J, Kuang H 2009 Acta Phys. Sin. 58 3001
Google Scholar
[15] 刘毅, 沈斐敏 2018 控制与决策 33 1598
Liu Y, Shen F M 2018 Control Desci. 33 1598
[16] 董力耘, 陈立, 段晓茵 2015 64 220505
Google Scholar
Dong L Y, Chen L, Duan X Y 2015 Acta Phys. Sin. 64 220505
Google Scholar
[17] 禹尔东, 吴正, 郭明旻 2014 63 094501
Google Scholar
Yu E D, Wu Z, Guo M W 2014 Acta Phys. Sin. 63 094501
Google Scholar
[18] 陈亮, 郭仁拥, 塔娜 2013 62 050506
Google Scholar
Chen L, Guo R Y, Ta N 2013 Acta Phys. Sin. 62 050506
Google Scholar
[19] 岳昊, 邵春福, 姚智胜 2009 58 4523
Google Scholar
Yue H, Shao C F, Yao Z S 2009 Acta Phys. Sin. 58 4523
Google Scholar
[20] 张磊, 岳昊, 李梅, 王帅, 米雪玉 2015 64 060505
Google Scholar
Zhang L, Yue H, Li M, Wang S, Mi X Y 2015 Acta Phys. Sin. 64 060505
Google Scholar
[21] 谢积鉴, 薛郁 2012 61 194502
Google Scholar
Xie J J, Xue Y 2012 Acta Phys. Sin. 61 194502
Google Scholar
[22] Eberhart R, Kennedy J 1995 MHS'95. Proceedings of the Sixth International Symposium on Micro Machine and Human Science Nagoya, Japan, October 4-6, 1995 p39
[23] Eberhart R C, Shi Y 2000 Proceedings of the 2000 Congress on Evolutionary Computation La Jolla, USA, July 16–19, 2000 p84
DownLoad:
Catalog
Metrics
- Abstract views: 7635
- PDF Downloads: 165
- Cited By: 0
