高级搜索

基于Dijkstra-ACO混合算法的应急疏散路径动态规划

曹祥红 李欣妍 魏晓鸽 李森 黄梦溪 李栋禄

引用本文: 曹祥红, 李欣妍, 魏晓鸽, 李森, 黄梦溪, 李栋禄. 基于Dijkstra-ACO混合算法的应急疏散路径动态规划[J]. 电子与信息学报, doi: 10.11999/JEIT190854 shu
Citation:  Xianghong CAO, Xinyan LI, Xiaoge WEI, Sen LI, Mengxi HUANG, Donglu LI. Dynamic Programming of Emergency Evacuation Path Based on Dijkstra-ACO Hybrid Algorithm[J]. Journal of Electronics and Information Technology, doi: 10.11999/JEIT190854 shu

基于Dijkstra-ACO混合算法的应急疏散路径动态规划

    作者简介: 曹祥红: 女,1972年生,副教授,研究方向为建筑电气节能技术、智能照明控制技术、智能供配电技术;
    李欣妍: 女,1994年生,硕士生,研究方向为智能照明控制技术;
    魏晓鸽: 女,1987年生,讲师,研究方向为建筑科学与工程;安全科学与灾害防治;
    李森: 男,1987年生,讲师,研究方向为建筑科学与工程;安全科学与灾害防治;
    黄梦溪: 女,1995年生,硕士生,研究方向为建筑电气节能技术;
    李栋禄: 男,1994年生,硕士生,研究方向为智能供配电技术
    通讯作者: 曹祥红,caoxhong@zzuli.edu.cn
  • 基金项目: 河南省科技攻关项目“高层住宅建筑家庭集聚疏散行为的实验与模拟研究”(172102310670)

摘要: 现代建筑设计趋于多样化,内部结构和功能越来越复杂,而传统疏散系统逃生指示方向固定、人员疏散时间较长,火灾发生时,不能够及时改变指示方向,易将逃生人员导向危险区域,威胁被困人员生命安全。该文提出了一种Dijkstra-ACO混合路径动态规划算法,在Dijkstra算法获得全局最优路径的基础上再采用ACO算法对每个节点进一步优化以获取最优路径,并节省算法运行时间。通过实验仿真验证了混合算法的有效性,能够根据起火点动态规划疏散路径,及时调整疏散指示方向,为火场中人员疏散逃生赢得宝贵时间。

English

    1. [1]

      十一届全国人大常委会第二十一次会议举行第二次全体会议听取关于消防工作情况的报告[J]. 中国消防, 2011(13): 4–5. (查阅所有网上资料, 未找到作者信息, 请联系作者补充)
      The 21st meeting of the Standing Committee of the 11th National People's Congress holds the second plenary session to hear a report on the work of fire protection[J]. China Fire, 2011(13): 4–5. (查阅所有网上资料, 未找到对应的英文翻译, 请联系作者确认).

    2. [2]

      雷春英. 基于改进蚁群算法的火灾疏散路径优化研究[D]. [硕士论文], 武汉理工大学, 2014.
      LEI Chunying. Route optimization of fire evacuation based on improved ant colony algorithm[D]. [Master dissertation], Wuhan University of Technology, 2014.

    3. [3]

      于振中, 李强, 樊启高. 智能仿生算法在移动机器人路径规划优化中的应用综述[J]. 计算机应用研究, 2019, 36(11): 3210–3219. doi: 10.19734/j.issn.1001-3695.2018.07.0483
      YU Zhenzhong, LI Qiang, and FAN Qigao. Survey on application of bioinspired intelligent algorithms in path planning optimization of mobile robots[J]. Application Research of Computers, 2019, 36(11): 3210–3219. doi: 10.19734/j.issn.1001-3695.2018.07.0483

    4. [4]

      杨雁莹, 徐仙伟, 曹霁. 基于仿生理论的新型优化算法综述[J]. 计算机仿真, 2016, 33(6): 233–237, 293. doi: 10.3969/j.issn.1006-9348.2016.06.051
      YANG Yanying, XU Xianwei, and CAO Ji. Overview of new optimization algorithms based on bionic theory[J]. Computer Simulation, 2016, 33(6): 233–237, 293. doi: 10.3969/j.issn.1006-9348.2016.06.051

    5. [5]

      何梦男, 付瑜玲, 陈诚, 等. 基于元胞自动机的应急疏散最短路径优化算法[J]. 中国安全科学学报, 2019, 29(4): 51–57. doi: 10.16265/j.cnki.issn1003-3033.2019.04.009
      HE Mengnan, FU Yuling, CHEN Cheng, et al. Shortest path optimal algorithm for emergency evacuation based on cellular automata[J]. China Safety Science Journal, 2019, 29(4): 51–57. doi: 10.16265/j.cnki.issn1003-3033.2019.04.009

    6. [6]

      任伟建, 左方晨, 黄丽杰. 基于GIS的Dijkstra算法改进研究[J]. 控制工程, 2018, 25(2): 188–191. doi: 10.14107/j.cnki.kzgc.150340
      REN Weijian, ZUO Fangchen, and HUANG Lijie. The improvement research of Dijkstra algorithm based on GIS[J]. Control Engineering of China, 2018, 25(2): 188–191. doi: 10.14107/j.cnki.kzgc.150340

    7. [7]

      张银铃, 牛小梅. 蚁群算法在移动机器人路径规划中的仿真研究[J]. 计算机仿真, 2011, 28(6): 231–234. doi: 10.3969/j.issn.1006-9348.2011.06.057
      ZHANG Yinling and NIU Xiaomei. Simulation research on mobile robot path planning based on ant colony optimization[J]. Computer Simulation, 2011, 28(6): 231–234. doi: 10.3969/j.issn.1006-9348.2011.06.057

    8. [8]

      陈月云, 简荣灵, 赵庸旭. 基于快速群体智能算法的毫米波天线设计[J]. 电子与信息学报, 2018, 40(2): 493–499. doi: 10.11999/JEIT170455
      CHEN Yueyun, JIAN Rongling, and ZHAO Yongxu. Millimeter wave antenna design based on fast swarm intelligence algorithm[J]. Journal of Electronics &Information Technology, 2018, 40(2): 493–499. doi: 10.11999/JEIT170455

    9. [9]

      王晨旸, 张玉茹. 对基本蚁群算法的改进及其在TSP中的应用[J]. 哈尔滨商业大学学报: 自然科学版, 2017, 33(5): 561–564.
      WANG Chenyang and ZHANG Yuru. Improvement of basic ant colony algorithm and its application in TSP[J]. Journal of Harbin University of Commerce:Natural Sciences Edition, 2017, 33(5): 561–564.

    10. [10]

      齐茁. 建筑火灾中人员疏散自适应蚁群算法的研究[D]. [硕士论文], 沈阳航空航天大学, 2011.
      QI Zhuo. Adaptive ant colony algorithm based on evacuation in building fire[D]. [Master dissertation], Shenyang Aerospace University, 2011.

    11. [11]

      陈超, 张莉. 基于改进蚁群算法的三维路径规划[J]. 计算机工程与应用, 2019, 55(20): 192–196. doi: 10.3778/j.issn.1002-8331.1904-0212
      CHEN Chao and ZHANG Li. Three-dimensional path planning based on improved ant colony algorithm[J]. Computer Engineering and Applications, 2019, 55(20): 192–196. doi: 10.3778/j.issn.1002-8331.1904-0212

    12. [12]

      熊沂铖, 王栋. 基于蚁群算法的车辆路径问题研究[J]. 信息技术, 2019(7): 15–17, 23.
      XIONG Yicheng and WANG Dong. Vehicle routing problem based on ant colony algorithm[J]. Information Technology, 2019(7): 15–17, 23.

    13. [13]

      段鹏飞. 面向校园疏散的均衡模型与疏导优化方法研究[D]. [博士论文], 武汉理工大学, 2013.
      DUAN Pengfei. Research on equilibrium model and optimization method for campus evacuation[D]. [Ph. D. dissertation], Wuhan University of Technology, 2013.

    14. [14]

      杨桂华, 符士宾, 刘志毅, 等. 基于改进蚁群算法的室内移动机器人路径规划[J]. 科学技术与工程, 2019, 19(19): 175–179.
      YANG Guihua, FU Shibin, LIU Zhiyi, et al. Path planning of indoor mobile robot based on improved ant colony algorithm[J]. Science Technology and Engineering, 2019, 19(19): 175–179.

    15. [15]

      温正. 精通MATLAB科学计算[M]. 北京: 清华大学出版社, 2015: 55–59.
      WEN Zheng. Proficient in MATLAB Scientific Computing[M]. Beijing: Tsinghua University Press, 2015: 55–59. (查阅所有网上资料, 未找到对应的英文翻译, 请联系作者确认).

    16. [16]

      王辉, 朱龙彪, 王景良, 等. 基于Dijkstra-蚁群算法的泊车系统路径规划研究[J]. 工程设计学报, 2016, 23(5): 489–496. doi: 10.3785/j.issn.1006-754X.2016.05.012
      WANG Hui, ZHU Longbiao, WANG Jingliang, et al. Research on path planing of parking system based on Dijkstra-ant colony hybrid algorithm[J]. Chinese Journal of Engineering Design, 2016, 23(5): 489–496. doi: 10.3785/j.issn.1006-754X.2016.05.012

    17. [17]

      石晓达, 孙连英, 葛娜, 等. 应急资源配送中Dijkstra改进算法的研究[J]. 北京联合大学学报, 2018, 32(2): 61–66. doi: 10.16255/j.cnki.ldxbz.2018.02.011
      SHI Xiaoda, SUN Lianying, GE Na, et al. Research on the improved algorithm of Dijkstra in emergency resource distribution[J]. Journal of Beijing Union University, 2018, 32(2): 61–66. doi: 10.16255/j.cnki.ldxbz.2018.02.011

    18. [18]

      WANG Han, ZHANG Hongjun, WANG Kun, et al. Off-road path planning based on improved ant colony algorithm[J]. Wireless Personal Communications, 2018, 102(2): 1705–1721. doi: 10.1007/s11277-017-5229-5

    19. [19]

      DENTLER J, ROSALIE M, DANOY G, et al. Collision avoidance effects on the mobility of a UAV swarm using chaotic ant colony with model predictive control[J]. Journal of Intelligent & Robotic Systems, 2018, 93(1/2): 227–243. doi: 10.1007/s10846-018-0822-8

    20. [20]

      CHEN Zhiping, LI Zhijun, LIU Zhen, et al. The research and application of improved ant colony algorithm with multi-thresholds in edge detection[C]. Proceedings of International Conference on Industrial Informatics-Computing Technology, Intelligent Technology, Industrial Information Integration, Wuhan, China, 2017: 5–9. doi: 10.1109/ICIICII.2017.27.

    21. [21]

      CHIN W, SAPUTRA A A, and KUBOTA N. A neuro-based network for on-line topological map building and dynamic path planning[C]. Proceedings of 2017 International Joint Conference on Neural Networks, Anchorage, USA, 2017: 2805–2810. doi: 10.1109/IJCNN.2017.7966202.

    22. [22]

      YAO Baozhen, CHEN Chao, SONG Xiaolin, et al. Fresh seafood delivery routing problem using an improved ant colony optimization[J]. Annals of Operations Research, 2017, 273(1/2): 163–185. doi: 10.1007/s10479-017-2531-2

    23. [23]

      FATHI M, RODRÍGUEZ V, and ALVAREZ M J. A novel memetic ant colony optimization-based heuristic algorithm for solving the assembly line part feeding problem[J]. The International Journal of Advanced Manufacturing Technology, 2014, 75(1/4): 629–643. doi: 10.1007/s00170-014-6068-0

    24. [24]

      DU Baigang and GUO Shunsheng. Production planning conflict resolution of complex product system in group manufacturing: A novel hybrid approach using ant colony optimization and Shapley value[J]. Computers & Industrial Engineering, 2016, 94: 158–169. doi: 10.1016/j.cie.2015.12.015

    25. [25]

      张勇, 高鑫鑫, 王昱洁. 基于SFLA-GA混合算法求解时间最优的旅行商问题[J]. 电子与信息学报, 2018, 40(2): 363–370. doi: 10.11999/JEIT170484
      ZHANG Yong, GAO Xinxin, and WANG Yujie. Solving the time optimal traveling salesman problem based on hybrid shuffled frog leaping algorithm-genetic algorithm[J]. Journal of Electronics &Information Technology, 2018, 40(2): 363–370. doi: 10.11999/JEIT170484

  • 图 1  应急疏散环境模型

    图 2  Dijkstra-ACO混合算法流程图

    图 3  Dijkstra算法仿真结果

    图 4  ACO算法仿真结果

    图 5  Dijkstra-ACO混合算法仿真结果

    图 6  Dijkstra-GA混合算法仿真结果

    图 7  假设着火点位置混合算法仿真结果

    表 1  4种算法仿真结果

    DijkstraACODijkstra-ACO混合算法Dijkstra-GA混合算法
    运行时间(s)0.23719.8041.1755.134
    最短路径(m)41.681336.384833.804335.9051
    下载: 导出CSV
  • 加载中
图(7)表(1)
计量
  • PDF下载量:  15
  • 文章访问数:  519
  • HTML全文浏览量:  70
文章相关
  • 通讯作者:  曹祥红, caoxhong@zzuli.edu.cn
  • 收稿日期:  2019-11-01
  • 录用日期:  2020-05-08
  • 网络出版日期:  2020-05-17
通讯作者: 陈斌, bchen63@163.com
  • 1. 

    沈阳化工大学材料科学与工程学院 沈阳 110142

  1. 本站搜索
  2. 百度学术搜索
  3. 万方数据库搜索
  4. CNKI搜索

/

返回文章