基于Dijkstra-ACO混合算法的應(yīng)急疏散路徑動(dòng)態(tài)規(guī)劃

曹祥紅; 李欣妍; 魏曉鴿; 李森; 黃夢(mèng)溪; 李棟祿

doi:10.11999/JEIT190854

基于Dijkstra-ACO混合算法的應(yīng)急疏散路徑動(dòng)態(tài)規(guī)劃

doi: 10.11999/JEIT190854 cstr: 32379.14.JEIT190854

鄭州輕工業(yè)大學(xué)建筑環(huán)境工程學(xué)院鄭州 450000

基金項(xiàng)目: 河南省科技攻關(guān)項(xiàng)目“高層住宅建筑家庭集聚疏散行為的實(shí)驗(yàn)與模擬研究”(172102310670)

詳細(xì)信息

作者簡(jiǎn)介:
曹祥紅：女，1972年生，副教授，研究方向?yàn)榻ㄖ姎夤?jié)能技術(shù)、智能照明控制技術(shù)、智能供配電技術(shù)

李欣妍：女，1994年生，碩士生，研究方向?yàn)橹悄苷彰骺刂萍夹g(shù)

魏曉鴿：女，1987年生，講師，研究方向?yàn)榻ㄖ茖W(xué)與工程、安全科學(xué)與災(zāi)害防治

李森：男，1987年生，講師，研究方向?yàn)榻ㄖ茖W(xué)與工程、安全科學(xué)與災(zāi)害防治

黃夢(mèng)溪：女，1995年生，碩士生，研究方向?yàn)榻ㄖ姎夤?jié)能技術(shù)

李棟祿：男，1994年生，碩士生，研究方向?yàn)橹悄芄┡潆娂夹g(shù)

通訊作者:
曹祥紅　caoxhong@zzuli.edu.cn

中圖分類號(hào): TP312
計(jì)量
- 文章訪問數(shù): 3972
- HTML全文瀏覽量: 1781
- PDF下載量: 165
- 被引次數(shù): 0
出版歷程
- 收稿日期: 2019-11-01
- 修回日期: 2020-05-08
- 網(wǎng)絡(luò)出版日期: 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)

摘要

摘要:
現(xiàn)代建筑設(shè)計(jì)趨于多樣化，內(nèi)部結(jié)構(gòu)和功能越來越復(fù)雜，而傳統(tǒng)疏散系統(tǒng)逃生指示方向固定、人員疏散時(shí)間較長(zhǎng)，火災(zāi)發(fā)生時(shí)，不能夠及時(shí)改變指示方向，易將逃生人員導(dǎo)向危險(xiǎn)區(qū)域，威脅被困人員生命安全。該文提出了一種Dijkstra-ACO混合路徑動(dòng)態(tài)規(guī)劃算法，在Dijkstra算法獲得全局最優(yōu)路徑的基礎(chǔ)上再采用蟻群優(yōu)化(ACO)算法對(duì)每個(gè)節(jié)點(diǎn)進(jìn)一步優(yōu)化以獲取最優(yōu)路徑，并節(jié)省算法運(yùn)行時(shí)間。通過實(shí)驗(yàn)仿真驗(yàn)證了混合算法的有效性，能夠根據(jù)起火點(diǎn)動(dòng)態(tài)規(guī)劃疏散路徑，及時(shí)調(diào)整疏散指示方向，為火場(chǎng)中人員疏散逃生贏得寶貴時(shí)間。
- 應(yīng)急疏散路徑 /
- 動(dòng)態(tài)規(guī)劃 /
- Dijkstra算法 /
- 蟻群優(yōu)化算法
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 應(yīng)急疏散環(huán)境模型

下載: 全尺寸圖片幻燈片

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

下載: 全尺寸圖片幻燈片

圖 3 Dijkstra算法仿真結(jié)果

下載: 全尺寸圖片幻燈片

圖 4 ACO算法仿真結(jié)果

下載: 全尺寸圖片幻燈片

圖 5 Dijkstra-ACO混合算法仿真結(jié)果

下載: 全尺寸圖片幻燈片

圖 6 Dijkstra-GA混合算法仿真結(jié)果

下載: 全尺寸圖片幻燈片

圖 7 假設(shè)著火點(diǎn)位置混合算法仿真結(jié)果

下載: 全尺寸圖片幻燈片

表 1 4種算法仿真結(jié)果

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

運(yùn)行時(shí)間(s) 0.237 19.804 1.175 5.134
最短路徑(m) 41.6813 36.3848 33.8043 35.9051

下載: 導(dǎo)出CSV

參考文獻(xiàn)(25)

十一屆全國(guó)人大常委會(huì)第二十一次會(huì)議舉行第二次全體會(huì)議聽取關(guān)于消防工作情況的報(bào)告[J]. 中國(guó)消防, 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.

雷春英. 基于改進(jìn)蟻群算法的火災(zāi)疏散路徑優(yōu)化研究[D]. [碩士論文], 武漢理工大學(xué), 2014.

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

于振中, 李強(qiáng), 樊啟高. 智能仿生算法在移動(dòng)機(jī)器人路徑規(guī)劃優(yōu)化中的應(yīng)用綜述[J]. 計(jì)算機(jī)應(yīng)用研究, 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

楊雁瑩, 徐仙偉, 曹霽. 基于仿生理論的新型優(yōu)化算法綜述[J]. 計(jì)算機(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

何夢(mèng)男, 付瑜玲, 陳誠(chéng), 等. 基于元胞自動(dòng)機(jī)的應(yīng)急疏散最短路徑優(yōu)化算法[J]. 中國(guó)安全科學(xué)學(xué)報(bào), 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ìn)研究[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

張銀鈴, 牛小梅. 蟻群算法在移動(dòng)機(jī)器人路徑規(guī)劃中的仿真研究[J]. 計(jì)算機(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

陳月云, 簡(jiǎn)榮靈, 趙庸旭. 基于快速群體智能算法的毫米波天線設(shè)計(jì)[J]. 電子與信息學(xué)報(bào), 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

王晨旸, 張玉茹. 對(duì)基本蟻群算法的改進(jìn)及其在TSP中的應(yīng)用[J]. 哈爾濱商業(yè)大學(xué)學(xué)報(bào): 自然科學(xué)版, 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.

齊茁. 建筑火災(zāi)中人員疏散自適應(yīng)蟻群算法的研究[D]. [碩士論文], 沈陽航空航天大學(xué), 2011.

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

陳超, 張莉. 基于改進(jìn)蟻群算法的三維路徑規(guī)劃[J]. 計(jì)算機(jī)工程與應(yīng)用, 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]. 信息技術(shù), 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ǎo)優(yōu)化方法研究[D]. [博士論文], 武漢理工大學(xué), 2013.

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

楊桂華, 符士賓, 劉志毅, 等. 基于改進(jìn)蟻群算法的室內(nèi)移動(dòng)機(jī)器人路徑規(guī)劃[J]. 科學(xué)技術(shù)與工程, 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科學(xué)計(jì)算[M]. 北京: 清華大學(xué)出版社, 2015: 55–59.

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

王輝, 朱龍彪, 王景良, 等. 基于Dijkstra-蟻群算法的泊車系統(tǒng)路徑規(guī)劃研究[J]. 工程設(shè)計(jì)學(xué)報(bào), 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

石曉達(dá), 孫連英, 葛娜, 等. 應(yīng)急資源配送中Dijkstra改進(jìn)算法的研究[J]. 北京聯(lián)合大學(xué)學(xué)報(bào), 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混合算法求解時(shí)間最優(yōu)的旅行商問題[J]. 電子與信息學(xué)報(bào), 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

相關(guān)文章

施引文獻(xiàn)

資源附件(0)

訪問統(tǒng)計(jì)