高级搜索

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

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

引用本文: 曹祥红, 李欣妍, 魏晓鸽, 李森, 黄梦溪, 李栋禄. 基于Dijkstra-ACO混合算法的应急疏散路径动态规划[J]. 电子与信息学报, 2020, 42(6): 1502-1509. 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, 2020, 42(6): 1502-1509. 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]. 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]. 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. [1]

      姚敏立, 王旭健, 张峰干, 戴定成. 基于动态参数差分进化算法的多约束稀布矩形面阵优化. 电子与信息学报, 2020, 42(5): 1281-1287.

    2. [2]

      牛莹, 张勋才. 基于变步长约瑟夫遍历和DNA动态编码的图像加密算法. 电子与信息学报, 2020, 42(6): 1383-1391.

    3. [3]

      臧艺超, 周天阳, 朱俊虎, 王清贤. 领域独立智能规划技术及其面向自动化渗透测试的攻击路径发现研究进展. 电子与信息学报, 2020, 41(0): 1-13.

    4. [4]

      徐宇, 林郁, 杨海钢. FPGA双端口存储器映射优化算法. 电子与信息学报, 2020, 41(0): 1-8.

    5. [5]

      陈前斌, 谭颀, 魏延南, 贺兰钦, 唐伦. 异构云无线接入网架构下面向混合能源供应的动态资源分配及能源管理算法. 电子与信息学报, 2020, 42(6): 1428-1435.

    6. [6]

      高东, 梁子林. 基于能量效率的双层非正交多址系统资源优化算法. 电子与信息学报, 2020, 42(5): 1237-1243.

    7. [7]

      刘彬, 杨有恒, 赵志彪, 吴超, 刘浩然, 闻岩. 一种基于正则优化的批次继承极限学习机算法. 电子与信息学报, 2020, 42(7): 1734-1742.

    8. [8]

      宋人杰, 张元东. 基于感兴趣区域的高性能视频编码帧内预测优化算法. 电子与信息学报, 2020, 42(0): 1-7.

    9. [9]

      惠鏸, 张晓静. 无线自组织网络的联合安全路由选择和功率优化算法. 电子与信息学报, 2020, 41(0): 1-8.

    10. [10]

      陈勇, 郑瀚, 沈奇翔, 刘焕淋. 基于改进免疫粒子群优化算法的室内可见光通信三维定位方法. 电子与信息学报, 2020, 42(0): 1-7.

    11. [11]

      李劲松, 彭建华, 刘树新, 季新生. 一种基于线性规划的有向网络链路预测方法. 电子与信息学报, 2020, 41(0): 1-9.

    12. [12]

      王永娟, 王涛, 袁庆军, 高杨, 王相宾. 密码算法旁路立方攻击改进与应用. 电子与信息学报, 2020, 42(5): 1087-1093.

    13. [13]

      贾连印, 陈明鲜, 李孟娟, 游进国, 丁家满. 基于状态视图的高效Hilbert编码和解码算法. 电子与信息学报, 2020, 42(6): 1494-1501.

    14. [14]

      赵海霞, 韦永壮, 刘争红. 一种变体BISON分组密码算法及分析. 电子与信息学报, 2020, 42(7): 1796-1802.

    15. [15]

      董道广, 芮国胜, 田文飚. 时域流信号的多任务稀疏贝叶斯动态重构方法研究. 电子与信息学报, 2020, 42(7): 1758-1765.

    16. [16]

      游凌, 李伟浩, 张文林, 王科人. 基于深度神经网络的Morse码自动译码算法. 电子与信息学报, 2020, 41(0): 1-6.

    17. [17]

      陈根华, 陈伯孝. 复杂多径信号下基于空域变换的米波雷达稳健测高算法. 电子与信息学报, 2020, 42(5): 1297-1302.

    18. [18]

      归伟夏, 陆倩, 苏美力. 关于系统级故障诊断的烟花-反向传播神经网络算法. 电子与信息学报, 2020, 42(5): 1102-1109.

    19. [19]

      张斌, 吴浩明. 一种面向连接的快速多维包分类算法. 电子与信息学报, 2020, 42(6): 1526-1533.

    20. [20]

      赵国繁, 唐伦, 胡彦娟, 赵培培, 陈前斌. 面向可靠性的5G网络切片重构及映射算法. 电子与信息学报, 2020, 42(6): 1478-1485.

  • 图 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下载量:  26
  • 文章访问数:  1230
  • HTML全文浏览量:  182
文章相关
  • 通讯作者:  曹祥红, caoxhong@zzuli.edu.cn
  • 收稿日期:  2019-11-01
  • 录用日期:  2020-05-08
  • 网络出版日期:  2020-05-17
  • 刊出日期:  2020-06-01
通讯作者: 陈斌, bchen63@163.com
  • 1. 

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

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

/

返回文章