改进蚁群算法的拥堵环境疏散路径规划研究

doi:10.3778/j.issn.1002-8331.2206-0493

摘要/Abstract

摘要： 针对突发事件疏散过程中人员拥堵对于疏散路径选择的影响，提出拥堵环境下的改进蚁群算法疏散路径规划模型。以二维栅格环境为基础，识别陷阱栅格，建立角栅格环境模型，对初始信息素进行差异化处理，改善蚁群算法初期搜索较为盲目的问题；结合路径拥堵程度和终点对蚂蚁路径选择的影响改进启发函数，避免陷入局部最优，提高搜索路径质量；引入信息素衰减系数惩罚经过拥堵区域的路径，并结合Dijkstra算法得到的次优路径，改进信息素的更新方式；通过最短路径优化操作，减少最短路径的无效节点与多余转折点，提高路径平滑度。仿真实验结果的对比分析表明，改进后的蚁群算法在有无拥堵情况下都能快速高效地规划出更平滑的最优疏散路径。

关键词: 拥堵环境, 疏散路径规划, 蚁群算法, 最短路径优化

Abstract: Aiming at the influence of personnel congestion on evacuation route selection in the process of emergency evacuation, an improved ant colony algorithm evacuation path planning model in congested environment is proposed. Based on the two-dimensional grid environment, trap grids are identified, the diagonal grid environment model is established, and the initial pheromones are differentiated to improve the problem of blind search in the initial stage of the ant colony algorithm. The heuristic function is improved by combining the degree of path congestion and the influence of the end point on the ant path selection, avoiding falling into local optimum and improving the quality of the search path. The pheromone attenuation coefficient is introduced to penalize the path passing through the congested areas, and the suboptimal path obtained by Dijkstra algorithm is combined to improve the update method of pheromone. Through the shortest path optimization operation, the invalid nodes and redundant inflection points of the shortest path are reduced, and the smoothness of the path is improved. The comparative analysis of the simulation experimental results shows that the improved ant colony algorithm can quickly and efficiently plan a smoother and optimal evacuation route with or without congestion.

Key words: congested environment, evacuation path planning, ant colony algorithm, shortest path optimization

霍非舟, 高帅云, 魏云飞, 马亚萍, 吴丽君. 改进蚁群算法的拥堵环境疏散路径规划研究[J]. 计算机工程与应用, 2023, 59(11): 263-271.

HUO Feizhou, GAO Shuaiyun, WEI Yunfei, MA Yaping, WU Lijun. Research on Evacuation Path Planning of Congested Environment with Improved Ant Colony Algorithm[J]. Computer Engineering and Applications, 2023, 59(11): 263-271.

参考文献

[1] 吕伟，穆治国，刘丹.大型购物中心人员疏散引导模拟优化研究[J].中国安全生产科学技术，2019，15（5）：136-141.
LYU W，MU Z G，LIU D.Study on optimal simulation of pedestrian evacuation guidance in large shopping mall[J].Journal of Safety Science and Technology，2019，15（5）：136-141.
[2] 江锦成.面向重大突发灾害事故的应急疏散研究综述[J].武汉大学学报（信息科学版），2021，46（10）：1498-1518.
JIANG J C.A review on emergency evacuation methods for major sudden disasters and accidents[J].Geomatics and Information Science of Wuhan University，2021，46（10）：1498-1518.
[3] 胡佳斌，王祥澍，张琪，等.优化多步长蚁群算法求解机器人路径规划问题[J].传感器与微系统，2021，40（10）：121-124.
HU J B，WANG X S，ZHANG Q，et al.Optimized multi-step ant colony algorithm for robot path planning problem solving[J].Transducer and Microsystem Technologies，2021，40（10）：121-124.
[4] 李理，李鸿，单宁波.多启发因素改进蚁群算法的路径规划[J].计算机工程与应用，2019，55（5）：219-225.
LI L，LI H，SHAN N B.Path planning based on improved ant colony algorithm with multiple inspired factor[J].Computer Engineering and Applications，2019，55（5）：219-225.
[5] 毛嘉琪.改进蚁群算法的机器人路径规划研究[J].计算机应用与软件，2021，38（5）：300-306.
MAO J Q.Robot path planning based on improved ant colony algorithm[J].Computer Applications and Software，2021，38（5）：300-306.
[6] YANG L，FU L，LI P，et al.LF-ACO：an effective formation path planning for multi-mobile robot[J].Mathematical Biosciences and Engineering，2022，19（1）：225-252.
[7] 袁福龙，朱建平.基于改进蚁群算法的移动机器人最优路径规划[J].现代制造工程，2021（7）：38-47.
YUAN F L，ZHU J P.Optimal path planning of mobile robot based on improved ant colony algorithm[J].Modern Manufacturing Engineering，2021（7）：38-47.
[8] LUO Q，WANG H，ZHENG Y，et al.Research on path planning of mobile robot based on improved ant colony algorithm[J].Neural Computing and Applications，2020，32（6）：1555-1566.
[9] 王培良，张婷，肖英杰.蚁群元胞优化算法在人群疏散路径规划中的应用[J].物理学报，2020，69（8）：234-242.
WANG P L，ZHANG T，XIAO Y J.Application research of ant colony cellular optimization algorithm in population evacuation path planning[J].Acta Physica Sinica，2020，69（8）：234-242.
[10] SUN S L，ZHAO Q，XIE W Z.Study on safe evacuation routes based on crowd density map of shopping mall[J].IEEE Access，2020，8：153981-153992.
[11] 曹祥红，李欣妍，魏晓鸽，等.基于Dijkstra-ACO混合算法的应急疏散路径动态规划[J].电子与信息学报，2020，42（6）：1502-1509.
CAO X H，LI X Y，WEI X G，et al.Dynamic programming of emergency evacuation path based on Dijkstra-ACO hybrid algorithm[J].Journal of Electronics & Information Technology，2020，42（6）：1502-1509.
[12] 贾进章，李雪娇.基于遗传-蚁群算法的单层建筑火灾疏散路径规划研究[J].中国安全生产科学技术，2020，16（6）：122-126.
JIA J Z，LI X J.Research on evacuation path planning in single-story building fire based on genetic-ant colony algorithm[J].Journal of Safety Science and Technology，2020，16（6）：122-126.
[13] 张苏英，郭宝樑，赵国花，等.基于改进蚁群算法的大型综合建筑火灾疏散路径规划[J].科学技术与工程，2019，19（36）：258-264.
ZHANG S Y，GUO B L，ZHAO G H，et al.Large-scale integrated building fire evacuation path planning based on improved ant colony algorithm[J].Science Technology and Engineering，2019，19（36）：258-264.
[14] 江奎东，毛占利，陈浩楠，等.基于蚁群算法的烟气中人员疏散路径选择优化[J].中国安全生产科学技术，2018，14（11）：133-137.
JIANG K D，MAO Z L，CHEN H N，et al.Optimization of evacuation route selection for personnel in smoke environment based on ant colony algorithm[J].Journal of Safety Science and Technology，2018，14（11）：133-137.
[15] 赵江，孟晨阳，王晓博，等.特征点提取下的AGV栅格法建模与分析[J].计算机工程与应用，2022，58（8）：156-167.
ZHAO J，MENG C Y，WANG X B，et al.Modeling and analysis of AGV grid method based on feature points extraction[J].Computer Engineering and Applications，2022，58（8）：156-167.
[16] 李二超，齐款款.改进双向蚁群算法的移动机器人路径规划[J].计算机工程与应用，2021，57（18）：281-288.
LI E C，QI K K.Improved bidirectional ant colony algorithm mobile robot path planning[J].Computer Engineering and Applications，2021，57（18）：281-288.
[17] 张苏英，郭宝樑，陈灵芝，等.双向蚁群算法的智能消防疏散图路径规划[J].计算机工程与应用，2021，57（14）：259-266.
ZHANG S Y，GUO B L，CHEN L Z，et al.Path planning of intelligent fire evacuation map based on bidirectional ant colony algorithm[J].Computer Engineering and Applications，2021，57（14）：259-266.
[18] DORIGO M，MANIEZZO V，COLORNI A.Ant system：optimization by a colony of cooperating agents[J].IEEE Transactions on Systems，Man，and Cybernetics，Part B：Cybernetics，1996，26（1）：29-41.
[19] 张天瑞，吴宝库，周福强.面向机器人全局路径规划的改进蚁群算法研究[J].计算机工程与应用，2022，58（1）：282-291.
ZHANG T R，WU B K，ZHOU F Q.Research on improved ant colony algorithm for robot global path planning[J].Computer Engineering and Applications，2022，58（1）：282-291.
[20] LIU L，ZHANG H，XIE J，et al.Dynamic evacuation planning on cruise ships based on an improved ant colony system（IACS）[J].Journal of Marine Science and Engineering，2021，9（2）：220.