带约束条件的煤矿火灾避灾路线算法研究
|
摘要
为了解决常见煤矿井下避灾路线算法在带约束条件问题方面的局限性以及运行效率待提升等问题,提出一种带约束条件的煤矿火灾避灾路线算法。该算法在当量长度的计算中引入了体能消耗指数,实现了巷道起伏对避灾路线影响的量化;考虑了灾变因子对巷道网络的影响,特别地,以具有累积量危害的定量属性为约束条件对算法进行改进;引入SPFA(Shortest Path Faster Algorithm)算法,相比经典Dijkstra算法,本算法在时间效率上有较大提升。最后,以寺家庄煤矿为例进行了测试,验证了算法设计的有效性,同时实现了时间效率的数量级提升。
As for common algorithms for coal mine escape route solving,there exist the problems including the limit of carrying constraints and the efficiency to be improved. Therefore,this paper proposes a restricted SPFA algorithm to solve escape routes problem during coal mine fire. Compared with traditional algorithms,the algorithm introduces energy consumption index while calculating equivalent length,thus quantitating the influence of tunnel rugged topography; considers the influence of disaster factors to tunnel network,particularly takes quantitative attributes that have cumulative hazard as constraint conditions to improve the algorithm; introduces SPFA algorithm,achieving remarkable efficiency improvement relative to the classical Dijkstra algorithm. In the end,we take Sijiazhuang Coal Mine as an example to test the algorithm,the experiment results prove the effectiveness of the algorithm design; The efficiency has also improved by an order of magnitude.
As for common algorithms for coal mine escape route solving,there exist the problems including the limit of carrying constraints and the efficiency to be improved. Therefore,this paper proposes a restricted SPFA algorithm to solve escape routes problem during coal mine fire. Compared with traditional algorithms,the algorithm introduces energy consumption index while calculating equivalent length,thus quantitating the influence of tunnel rugged topography; considers the influence of disaster factors to tunnel network,particularly takes quantitative attributes that have cumulative hazard as constraint conditions to improve the algorithm; introduces SPFA algorithm,achieving remarkable efficiency improvement relative to the classical Dijkstra algorithm. In the end,we take Sijiazhuang Coal Mine as an example to test the algorithm,the experiment results prove the effectiveness of the algorithm design; The efficiency has also improved by an order of magnitude.
引文
[1]王金华,汪有刚,张雷,等.基于实时数据的井下避灾路线动态规划与发布方法研究[J].中国煤炭,2015,41(2):67-71.WANG Jinhua,WANG Yougang,ZHANG Lei,et al.Dynamic programming and release system of underground emergency escape route based on real-time data[J].China Coal,2015,41(2):67-71.
[2]赵作鹏,宗元元.面向矿井突水避险的双向搜索多最优路径算法[J].中国矿业大学学报,2015,44(3):590-596.ZHAO Zuopeng,ZONG Yuanyuan.A multi-path algorithm implemented with bidirectional search of mine water inrush hedge[J].Journal of China University of Mining&Technology,2015,44(3):590-596.
[3]康晓龙,王伟,赵耀华,等.城市地下快速通道坡度与风速变化对隧道内人员逃生的影响[J].建筑科学,2011,27(4):100-103.KANG Xiaolong,WANG Wei,ZHAO Yaohua,et al.Study on the influences of slope and velocity in urban underground express tunnel on personnel evacuation[J].Building Science,2011,27(4):100-103.
[4]贾进章.矿井火灾仿真与避灾路线的数学模型[J].自然灾害学报,2008,17(1):163-168.JIA Jinzhang.Mathematic models for mine fire simulation and determination of refuge route[J].Journal of Natural Disasters,2008,17(1):163-168.
[5]程卫民,姚玉静,吴立荣,等.基于Fluent的矿井火灾时期温度及浓度分布数值模拟[J].煤矿安全,2012,43(2):20-24.CHENG Weimin,YAO Yujing,WU Lirong,et al.Fluent-based numerical simulation of temperature and concentration during mine fire[J].Safety in Coal Mines,2012,43(2):20-24.
[6]张志华.矿山巷道三维网络模型的构建及其路径分析方法研究[D].西安:西安科技大学,2010.
[7]武玥.矿山巷道路径搜索及可视化[D].西安:西安科技大学,2014.
[8]毕林,崔君,林格,等.矿井火灾最优逃生路径优化数学模型的构建与实现[J].黄金科学技术,2017,25(2):104-109.BI Lin,CUI Jun,LIN Ge,et al.Construction and realization of optimal mathematical model of mine fire escape route[J].Gold Science and Technology,2017,25(2):104-109.
[9]赵文涛,张改丽,王丽娜.基于Dijkstra的煤矿井下紧急避灾路径搜索方法研究[J].矿山机械,2014,42(9):133-138.ZHAO Wentao,ZHANG Gaili,WANG Lina.Research on method of searching emergency refuge route in underground colliery based on Dijkstra[J].Mining&Processing Equipment,2014,42(9):133-138.
[10]成韶辉,张雪英,李凤莲,等.K则最优路径在矿井水害避灾中的应用研究[J].金属矿山,2014,43(1):137-140.CHENG Shaohui,ZHANG Xueying,LI Fenglian,et al.Application of K shortest path algorithm in avoiding from mine water disaster[J].Metal Mine,2014,43(1):137-140.
[11]卢国菊.矿井灾变时期最优避灾救灾路径研究[D].太原:太原理工大学,2013.
[12]姜雷.A*算法在矿井灾害应急救援中的应用[J].煤炭技术,2011,30(5):109-111.JIANG Lei.Application of A*algorithm in mine emergency response and rescue[J].Coal Technology,2011,30(5):109-111.
[13]黄萍,李兵磊.基于加权聚合粒子群算法的矿井火灾救援研究[J].福州大学学报:自然科学版,2016,44(6):868-873.HUANG Ping,LI Binglei.Mine fire rescue based on weighted aggregation particle swarm optimization[J].Journal of Fuzhou University:Natural Science Edition,2016,44(6):868-873.
[14]刘勇.基于蚁群算法的应急救援最优路径研究[D].武汉:中国地质大学(武汉),2010.
[15]WANG Q,SHI H,ZHOU Z.Escape route planning in underground mines[J].Revista De La Facultad De Ingeniería,2017,32(4):368-374.
[16]段凡丁.关于最短路径的SPFA快速算法[J].西南交通大学学报,1994,29(2):207-212.DUAN Fanding.A faster algorithm for shortest-path:SPFA[J].Journal of Southwest Jiaotong University,1994,29(2):207-212.
[17]严瑞,龙毅,郑玥,等.顾及地形起伏的步行最优路径分析算法[J].武汉大学学报:信息科学版,2012,37(5):564-568.YAN Rui,LONG Yi,ZHENG Yue,et al.An optimal walking path algorithm considering terrain influence[J].Geomatics and Information Science of Wuhan University,2012,37(5):564-568.
[18]张俊文,王凯,丁超南.基于元胞自动机的巷网火灾逃生路径分析[J].能源技术与管理,2017,42(5):4-7.ZHANG Junwen,WANG Kai,DING Chaonan.Path analysis of fire escape in lane network based on Cellular Automata[J].Energy Technology and Management,2017,42(5):4-7.
[19]MINETTI A E,MOIA C,ROI G S,et al.Energy cost of walking and running at extreme uphill and downhill slopes[J].Journal of Applied Physiology,2002,93(3):1039-1043.
[20]盖文妹,蒋仲安,邓云峰,等.重大事故救灾路线双目标优化模型及算法[J].北京科技大学学报,2014,36(4):535-542.GAI Wenmei,JIANG Zhongan,DENG Yunfeng,et al.Biobjective optimization model and algorithm of rescue routes during major accident time[J].Journal of University of Science and Technology Beijing,2014,36(4):535-542.
[21]LORENZ D H,RAZ D.A simple efficient approximation scheme for the restricted shortest path problem[J].Operations Research Letters,2001,28(5):213-219.
[22]HASSIN R.Approximation schemes for the restricted shortest path problem[J].Mathematics of Operations Research,1992,17(1):36-42.
[23]夏正冬,卜天明,张居阳.SPFA算法的分析及改进[J].计算机科学,2014,41(6):180-184.XIA Zhengdong,BU Tianming,ZHANG Juyang.Analysis and Improvement of SPFA Algorithm[J].Computer Science,2014,41(6):180-184.
[24]SUN Y,YU X,BIE R,et al.Discovering time-dependent shortest path on traffic graph for drivers towards green driving[J].Journal of Network&Computer Applications,2017,83:204-212.
[2]赵作鹏,宗元元.面向矿井突水避险的双向搜索多最优路径算法[J].中国矿业大学学报,2015,44(3):590-596.ZHAO Zuopeng,ZONG Yuanyuan.A multi-path algorithm implemented with bidirectional search of mine water inrush hedge[J].Journal of China University of Mining&Technology,2015,44(3):590-596.
[3]康晓龙,王伟,赵耀华,等.城市地下快速通道坡度与风速变化对隧道内人员逃生的影响[J].建筑科学,2011,27(4):100-103.KANG Xiaolong,WANG Wei,ZHAO Yaohua,et al.Study on the influences of slope and velocity in urban underground express tunnel on personnel evacuation[J].Building Science,2011,27(4):100-103.
[4]贾进章.矿井火灾仿真与避灾路线的数学模型[J].自然灾害学报,2008,17(1):163-168.JIA Jinzhang.Mathematic models for mine fire simulation and determination of refuge route[J].Journal of Natural Disasters,2008,17(1):163-168.
[5]程卫民,姚玉静,吴立荣,等.基于Fluent的矿井火灾时期温度及浓度分布数值模拟[J].煤矿安全,2012,43(2):20-24.CHENG Weimin,YAO Yujing,WU Lirong,et al.Fluent-based numerical simulation of temperature and concentration during mine fire[J].Safety in Coal Mines,2012,43(2):20-24.
[6]张志华.矿山巷道三维网络模型的构建及其路径分析方法研究[D].西安:西安科技大学,2010.
[7]武玥.矿山巷道路径搜索及可视化[D].西安:西安科技大学,2014.
[8]毕林,崔君,林格,等.矿井火灾最优逃生路径优化数学模型的构建与实现[J].黄金科学技术,2017,25(2):104-109.BI Lin,CUI Jun,LIN Ge,et al.Construction and realization of optimal mathematical model of mine fire escape route[J].Gold Science and Technology,2017,25(2):104-109.
[9]赵文涛,张改丽,王丽娜.基于Dijkstra的煤矿井下紧急避灾路径搜索方法研究[J].矿山机械,2014,42(9):133-138.ZHAO Wentao,ZHANG Gaili,WANG Lina.Research on method of searching emergency refuge route in underground colliery based on Dijkstra[J].Mining&Processing Equipment,2014,42(9):133-138.
[10]成韶辉,张雪英,李凤莲,等.K则最优路径在矿井水害避灾中的应用研究[J].金属矿山,2014,43(1):137-140.CHENG Shaohui,ZHANG Xueying,LI Fenglian,et al.Application of K shortest path algorithm in avoiding from mine water disaster[J].Metal Mine,2014,43(1):137-140.
[11]卢国菊.矿井灾变时期最优避灾救灾路径研究[D].太原:太原理工大学,2013.
[12]姜雷.A*算法在矿井灾害应急救援中的应用[J].煤炭技术,2011,30(5):109-111.JIANG Lei.Application of A*algorithm in mine emergency response and rescue[J].Coal Technology,2011,30(5):109-111.
[13]黄萍,李兵磊.基于加权聚合粒子群算法的矿井火灾救援研究[J].福州大学学报:自然科学版,2016,44(6):868-873.HUANG Ping,LI Binglei.Mine fire rescue based on weighted aggregation particle swarm optimization[J].Journal of Fuzhou University:Natural Science Edition,2016,44(6):868-873.
[14]刘勇.基于蚁群算法的应急救援最优路径研究[D].武汉:中国地质大学(武汉),2010.
[15]WANG Q,SHI H,ZHOU Z.Escape route planning in underground mines[J].Revista De La Facultad De Ingeniería,2017,32(4):368-374.
[16]段凡丁.关于最短路径的SPFA快速算法[J].西南交通大学学报,1994,29(2):207-212.DUAN Fanding.A faster algorithm for shortest-path:SPFA[J].Journal of Southwest Jiaotong University,1994,29(2):207-212.
[17]严瑞,龙毅,郑玥,等.顾及地形起伏的步行最优路径分析算法[J].武汉大学学报:信息科学版,2012,37(5):564-568.YAN Rui,LONG Yi,ZHENG Yue,et al.An optimal walking path algorithm considering terrain influence[J].Geomatics and Information Science of Wuhan University,2012,37(5):564-568.
[18]张俊文,王凯,丁超南.基于元胞自动机的巷网火灾逃生路径分析[J].能源技术与管理,2017,42(5):4-7.ZHANG Junwen,WANG Kai,DING Chaonan.Path analysis of fire escape in lane network based on Cellular Automata[J].Energy Technology and Management,2017,42(5):4-7.
[19]MINETTI A E,MOIA C,ROI G S,et al.Energy cost of walking and running at extreme uphill and downhill slopes[J].Journal of Applied Physiology,2002,93(3):1039-1043.
[20]盖文妹,蒋仲安,邓云峰,等.重大事故救灾路线双目标优化模型及算法[J].北京科技大学学报,2014,36(4):535-542.GAI Wenmei,JIANG Zhongan,DENG Yunfeng,et al.Biobjective optimization model and algorithm of rescue routes during major accident time[J].Journal of University of Science and Technology Beijing,2014,36(4):535-542.
[21]LORENZ D H,RAZ D.A simple efficient approximation scheme for the restricted shortest path problem[J].Operations Research Letters,2001,28(5):213-219.
[22]HASSIN R.Approximation schemes for the restricted shortest path problem[J].Mathematics of Operations Research,1992,17(1):36-42.
[23]夏正冬,卜天明,张居阳.SPFA算法的分析及改进[J].计算机科学,2014,41(6):180-184.XIA Zhengdong,BU Tianming,ZHANG Juyang.Analysis and Improvement of SPFA Algorithm[J].Computer Science,2014,41(6):180-184.
[24]SUN Y,YU X,BIE R,et al.Discovering time-dependent shortest path on traffic graph for drivers towards green driving[J].Journal of Network&Computer Applications,2017,83:204-212.