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

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

doi:10.11999/JEIT190854

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

doi: 10.11999/JEIT190854

郑州轻工业大学建筑环境工程学院郑州 450000

基金项目: 河南省科技攻关项目“高层住宅建筑家庭集聚疏散行为的实验与模拟研究”(172102310670)

详细信息

作者简介:
曹祥红：女，1972年生，副教授，研究方向为建筑电气节能技术、智能照明控制技术、智能供配电技术

李欣妍：女，1994年生，硕士生，研究方向为智能照明控制技术

魏晓鸽：女，1987年生，讲师，研究方向为建筑科学与工程、安全科学与灾害防治

李森：男，1987年生，讲师，研究方向为建筑科学与工程、安全科学与灾害防治

黄梦溪：女，1995年生，硕士生，研究方向为建筑电气节能技术

李栋禄：男，1994年生，硕士生，研究方向为智能供配电技术

通讯作者:
曹祥红　caoxhong@zzuli.edu.cn

中图分类号: TP312
计量
- 文章访问数: 3643
- HTML全文浏览量: 1584
- PDF下载量: 155
- 被引次数: 0
出版历程
- 收稿日期: 2019-11-01
- 修回日期: 2020-05-08
- 网络出版日期: 2020-05-17
- 刊出日期: 2020-06-22

Dynamic Programming of Emergency Evacuation Path Based on Dijkstra-ACO Hybrid Algorithm

School of Building Environmental Engineering, Zhengzhou University of Light Industry, Zhengzhou 450000, China

Funds: The Science and Technology in Henan Province Project “An Experimental and Simulated Study on Family Agglomeration and Evacuation Behavior in High-rise Residential Buildings” (172102310670)

摘要

摘要:
现代建筑设计趋于多样化，内部结构和功能越来越复杂，而传统疏散系统逃生指示方向固定、人员疏散时间较长，火灾发生时，不能够及时改变指示方向，易将逃生人员导向危险区域，威胁被困人员生命安全。该文提出了一种Dijkstra-ACO混合路径动态规划算法，在Dijkstra算法获得全局最优路径的基础上再采用蚁群优化(ACO)算法对每个节点进一步优化以获取最优路径，并节省算法运行时间。通过实验仿真验证了混合算法的有效性，能够根据起火点动态规划疏散路径，及时调整疏散指示方向，为火场中人员疏散逃生赢得宝贵时间。
- 应急疏散路径 /
- 动态规划 /
- Dijkstra算法 /
- 蚁群优化算法
Abstract:
With an increasing diversity in modern architectural design, the inner structure of buildings is much more complex than before, which makes the traditional fire emergency escape indication system fail to provide people with real-time instructions because of its inflexibility of changing direction. These failures always lead people to dangerous areas during a fire emergency, which is actual a threaten to people in buildings. A combined algorithm to find a path dynamically during a fire emergency based on Dijkstra and Ant Colony Optimization (ACO) algorithm is presented in this article. This new algorithm shortens the programming time by getting a globally optimal path based on Dijkstra algorithm and operates every single point with ACO algorithm in sequence to get a best path. The combined algorithm is tested by a simulation, in which it is proved effective in adjusting evacuation path depending on the point of ignition. The changeable real-time indication will extend the escaping time with people in a burning building, which is quite precious for saving lives.
- Emergency evacuation path /
- Dynamic programming /
- Dijkstra algorithm /
- Ant Colony Optimization (ACO) algorithm

HTML全文

图 1 应急疏散环境模型

下载: 全尺寸图片幻灯片

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

下载: 全尺寸图片幻灯片

图 3 Dijkstra算法仿真结果

下载: 全尺寸图片幻灯片

图 4 ACO算法仿真结果

下载: 全尺寸图片幻灯片

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

下载: 全尺寸图片幻灯片

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

下载: 全尺寸图片幻灯片

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

下载: 全尺寸图片幻灯片

表 1 4种算法仿真结果

Dijkstra ACO Dijkstra-ACO混合算法 Dijkstra-GA混合算法

运行时间(s) 0.237 19.804 1.175 5.134
最短路径(m) 41.6813 36.3848 33.8043 35.9051

下载: 导出CSV

参考文献(25)

十一届全国人大常委会第二十一次会议举行第二次全体会议听取关于消防工作情况的报告[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.

雷春英. 基于改进蚁群算法的火灾疏散路径优化研究[D]. [硕士论文], 武汉理工大学, 2014.

LEI Chunying. Route optimization of fire evacuation based on improved ant colony algorithm[D]. [Master dissertation], Wuhan University of Technology, 2014.

于振中, 李强, 樊启高. 智能仿生算法在移动机器人路径规划优化中的应用综述[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

杨雁莹, 徐仙伟, 曹霁. 基于仿生理论的新型优化算法综述[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

何梦男, 付瑜玲, 陈诚, 等. 基于元胞自动机的应急疏散最短路径优化算法[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

任伟建, 左方晨, 黄丽杰. 基于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

张银铃, 牛小梅. 蚁群算法在移动机器人路径规划中的仿真研究[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

陈月云, 简荣灵, 赵庸旭. 基于快速群体智能算法的毫米波天线设计[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

王晨旸, 张玉茹. 对基本蚁群算法的改进及其在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.

齐茁. 建筑火灾中人员疏散自适应蚁群算法的研究[D]. [硕士论文], 沈阳航空航天大学, 2011.

QI Zhuo. Adaptive ant colony algorithm based on evacuation in building fire[D]. [Master dissertation], Shenyang Aerospace University, 2011.

陈超, 张莉. 基于改进蚁群算法的三维路径规划[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

熊沂铖, 王栋. 基于蚁群算法的车辆路径问题研究[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.

段鹏飞. 面向校园疏散的均衡模型与疏导优化方法研究[D]. [博士论文], 武汉理工大学, 2013.

DUAN Pengfei. Research on equilibrium model and optimization method for campus evacuation[D]. [Ph. D. dissertation], Wuhan University of Technology, 2013.

杨桂华, 符士宾, 刘志毅, 等. 基于改进蚁群算法的室内移动机器人路径规划[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.

温正. 精通MATLAB科学计算[M]. 北京: 清华大学出版社, 2015: 55–59.

WEN Zheng. Proficient in MATLAB Scientific Computing[M]. Beijing: Tsinghua University Press, 2015: 55–59.

王辉, 朱龙彪, 王景良, 等. 基于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

石晓达, 孙连英, 葛娜, 等. 应急资源配送中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

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

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

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.

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.

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

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

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

张勇, 高鑫鑫, 王昱洁. 基于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

施引文献

资源附件(0)

访问统计