大型网络中容量受限的疏散路径规划方法
|
摘要
针对启发式算法利用Dijkstra算法求解大型动态网络中疏散路径规划问题时,存在疏散时间长、稳定性差等不足,该文提出了一种改进CCRP的方法,即用蚁群算法替代Dijkstra算法求解最优路径,进而减少疏散时间,增加估算疏散时间的精确性。实验表明,该方法能够在大型动态网络下实现路网容量受限的疏散路径规划有效求解,具有疏散时间短、疏散路径少、线性关系强等特点,相比原有CCRP算法更能满足实际疏散的需要。在寻找最优路径上采用蚁群算法求解,相比贪心算法更能支持全局最优、并行计算、疏散效率更高,在支持路况信息实时更新、大规模人群快速疏散、及时调整疏散路线等方面更具优势。
In view of the shortcomings such as long evacuation time,poor stability and so on,when the heuristic algorithm for CCRP using the Dijkstra algorithm to solving large-scale dynamic network evacuation route planning problem,this paper presented an improved CCRP method,which used ant colony algorithm to find the optimal path instead of Dijkstra algorithm,which reduced evacuation time and increased the accuracy of estimating evacuation time.Experiments showed that this method could effectively solve the evacuation route planning with capacity constraints in large-scale dynamic network.It has the characteristics of short evacuation time,less evacuation route and strong linear relationship.Compared with the original CCRP algorithm,this method could better meet the needs of actual evacuation.Ant colony algorithm was used to find the optimal path.Compared with greedy algorithm,it could support global optimization,parallel computing and higher evacuation efficiency.And more advantages in supporting real-time updating of road condition,rapid evacuation of large-scale crowd,timely adjustment of evacuation route and so on.
In view of the shortcomings such as long evacuation time,poor stability and so on,when the heuristic algorithm for CCRP using the Dijkstra algorithm to solving large-scale dynamic network evacuation route planning problem,this paper presented an improved CCRP method,which used ant colony algorithm to find the optimal path instead of Dijkstra algorithm,which reduced evacuation time and increased the accuracy of estimating evacuation time.Experiments showed that this method could effectively solve the evacuation route planning with capacity constraints in large-scale dynamic network.It has the characteristics of short evacuation time,less evacuation route and strong linear relationship.Compared with the original CCRP algorithm,this method could better meet the needs of actual evacuation.Ant colony algorithm was used to find the optimal path.Compared with greedy algorithm,it could support global optimization,parallel computing and higher evacuation efficiency.And more advantages in supporting real-time updating of road condition,rapid evacuation of large-scale crowd,timely adjustment of evacuation route and so on.
引文
[1]SHAHABI K,WILSON J P.Scalable evacuation routing in a dynamic environment[J].Computers Environment and Urban Systems,2018,67:29-40.
[2]刘永强,常青,熊华钢.改进蚁群算法求解时变网络中最短路径问题[J].北京航空航天大学学报,2009,35(10):1245-1248.(LIU Yongqiang,ChANG Qing,XIONG Huagang.Improved ant colony algorithm for shortest path problem in time-dependent networks[J].Journal of Beijing University of Aeronautics and Astronautics,2009,35(10):1245-1248.)
[3]HAMACHER H W,TJANDRA S A.Mathematical modelling of evacuation problems-a state of the art[EB/OL].[2019-03-28].https:∥www.mendeley.com/catalogue/mathematical-modelling-evacuation-problemsstate-art/.
[4]LU Q,HUANG Y,SHEKHAR S.Evacuation planning:a capacity constrained routing approach[C]∥International Conference on Intelligence and Security Informatics.[S.l.]:[s.n.],2003:111-125.
[5]LU Q,GEORGE B,SHEKHAR S.Capacity constrained routing algorithms for evacuation planning:a summary of results[C]∥International Symposium on Spatial&Temporal Databases.Berlin,Heidelberg:Springer,2005.
[6]KIM S,GEORGE B,SHEKHAR S.Evacuation route planning:Scalable heuristics[C]∥15th ACM International Symposium on Geographic Information Systems,ACM-GIS 2007.Seattle,Washington,USA:ACM,2007.
[7]SHEKHAR S,YANG K S,GUNTURI V M V,et al.Experiences with evacuation route planning algorithms[J].International Journal of Geographical Information Science,2012,26(12):2253-2265.
[8]李清泉,李秋萍,方志祥.一种基于时空拥挤度的应急疏散路径优化方法[J].测绘学报,2011,40(4):517-523.(LI Qingquan,LI Qiuping,FANG Zhixiang.An emergency evacuation routing optimization method based on space-time congestion concept[J].Acta Geodaetica et Cartographica Sinica,2011,40(4):517-523.)
[9]尹大朏,方裕.疏散规划的一种优化算法[J].地理与地理信息科学,2013,29(2):31-35,79.(YIN Dafei,FANG Yu.An optimization evacuation planning algorithm[J].Geography and Geo-Information Science,2013,29(2):31-35,79.)
[10]吴正言,张春勤,莫时旭.地震疏散路径规划算法[J].武汉理工大学学报(交通科学与工程版),2014,38(2):308-311.(WU Zhengyan,ZHANG Chunqin,MO Shixu.Earthquake evacuation route planning algorithm[J].Journal of Wuhan University of Technology(Transportation Science&Engineering),2014,38(2):308-311.)
[11]王婷婷,周建中,江焱生,等.基于网络流的避洪转移模型[J].自然灾害学报,2016,25(1):56-64.(WANGTingting,ZHOU Jianzhong,JIANG Yansheng,et al.Flood refuge and migration model based on network flow[J].Journal of Natural Disasters,2016,25(1):56-64.)
[12]李梦雅,王军,沈航.洪灾应急疏散路径规划算法优化[J].地球信息科学学报,2016,18(3):362-368.(LIMengya,WANG Jun,SHEN Hang.Optimization of evacuation routes planning algorithms for flood events[J].Journal of Geo-information Science,2016,18(3):362-368.)
[13]赵岩,高社生,姜微微.突发灾难下大型路网中的人员疏散模型[J].长安大学学报(自然科学版),2013,33(2):89-94.(ZHAO Yan,GAO Shesheng,JIANG Weiwei.Model of a large-scale transportation network for evacuation under emergency[J].Journal of Chang’an University(Natural Science Edition),2013,33(2):89-94.)
[14]孟永昌,杨赛霓,史培军.基于改进遗传算法的路网应急疏散多目标优化[J].武汉大学学报(信息科学版),2014,39(2):201-205.(MENG Yongchang,YANG Saini,SHI Peijun.Multi-objective optimization of emergency evacuation using improved genetic algorithm[J].Geomatics and Information Science of Wuhan University,2014,39(2):201-205.)
[15]丁雨淋,何小波,朱庆,等.实时威胁态势感知的室内火灾疏散路径动态优化方法[J].测绘学报,2016,45(12):1464-1475.(DING Yulin,HE Xiaobo,ZHUQing,et al.A dynamic optimization method of indoor fire evacuation route based on real-time situation awareness[J].Acta Geodaetica et Cartographica Sinica,2016,45(12):1464-1475.)
[16]COLORNI A,DORIGO M,MANIEZZO V.Distributed optimization by ant colonies[C]∥Proceedings of the first European Conference on Artificial Life.[S.l.]:[s.n.],1992:134-142.
[17]覃远年,梁仲华.蚁群算法研究与应用的新进展[J].计算机工程与科学,2019,41(1):173-184.(QIN Yuannian,LIANG Zhonghua.New progress of the ant colony algorithm in research and applications[J].Computer Engineering&Science,2019,41(1):173-184.)
[18]ZENG M,WANG C.Evacuation route planning algorithm:longer route preferential[C]∥The 6th International Symposium on Neural Networks on Advances in Neural Networks.Heidelberg:Springer,2009.
[19]刘纪平,吴立新,董春,等.一种大规模空间数据流式并行处理方法研究[J].测绘科学,2016,41(1):89-93,75.(LIU Jiping,WU Lixin,DONG Chun,et al.Study on a streaming parallel method for massive spatial data processing[J].Science of Surveying and Mapping,2016,41(1):89-93,75.)
[2]刘永强,常青,熊华钢.改进蚁群算法求解时变网络中最短路径问题[J].北京航空航天大学学报,2009,35(10):1245-1248.(LIU Yongqiang,ChANG Qing,XIONG Huagang.Improved ant colony algorithm for shortest path problem in time-dependent networks[J].Journal of Beijing University of Aeronautics and Astronautics,2009,35(10):1245-1248.)
[3]HAMACHER H W,TJANDRA S A.Mathematical modelling of evacuation problems-a state of the art[EB/OL].[2019-03-28].https:∥www.mendeley.com/catalogue/mathematical-modelling-evacuation-problemsstate-art/.
[4]LU Q,HUANG Y,SHEKHAR S.Evacuation planning:a capacity constrained routing approach[C]∥International Conference on Intelligence and Security Informatics.[S.l.]:[s.n.],2003:111-125.
[5]LU Q,GEORGE B,SHEKHAR S.Capacity constrained routing algorithms for evacuation planning:a summary of results[C]∥International Symposium on Spatial&Temporal Databases.Berlin,Heidelberg:Springer,2005.
[6]KIM S,GEORGE B,SHEKHAR S.Evacuation route planning:Scalable heuristics[C]∥15th ACM International Symposium on Geographic Information Systems,ACM-GIS 2007.Seattle,Washington,USA:ACM,2007.
[7]SHEKHAR S,YANG K S,GUNTURI V M V,et al.Experiences with evacuation route planning algorithms[J].International Journal of Geographical Information Science,2012,26(12):2253-2265.
[8]李清泉,李秋萍,方志祥.一种基于时空拥挤度的应急疏散路径优化方法[J].测绘学报,2011,40(4):517-523.(LI Qingquan,LI Qiuping,FANG Zhixiang.An emergency evacuation routing optimization method based on space-time congestion concept[J].Acta Geodaetica et Cartographica Sinica,2011,40(4):517-523.)
[9]尹大朏,方裕.疏散规划的一种优化算法[J].地理与地理信息科学,2013,29(2):31-35,79.(YIN Dafei,FANG Yu.An optimization evacuation planning algorithm[J].Geography and Geo-Information Science,2013,29(2):31-35,79.)
[10]吴正言,张春勤,莫时旭.地震疏散路径规划算法[J].武汉理工大学学报(交通科学与工程版),2014,38(2):308-311.(WU Zhengyan,ZHANG Chunqin,MO Shixu.Earthquake evacuation route planning algorithm[J].Journal of Wuhan University of Technology(Transportation Science&Engineering),2014,38(2):308-311.)
[11]王婷婷,周建中,江焱生,等.基于网络流的避洪转移模型[J].自然灾害学报,2016,25(1):56-64.(WANGTingting,ZHOU Jianzhong,JIANG Yansheng,et al.Flood refuge and migration model based on network flow[J].Journal of Natural Disasters,2016,25(1):56-64.)
[12]李梦雅,王军,沈航.洪灾应急疏散路径规划算法优化[J].地球信息科学学报,2016,18(3):362-368.(LIMengya,WANG Jun,SHEN Hang.Optimization of evacuation routes planning algorithms for flood events[J].Journal of Geo-information Science,2016,18(3):362-368.)
[13]赵岩,高社生,姜微微.突发灾难下大型路网中的人员疏散模型[J].长安大学学报(自然科学版),2013,33(2):89-94.(ZHAO Yan,GAO Shesheng,JIANG Weiwei.Model of a large-scale transportation network for evacuation under emergency[J].Journal of Chang’an University(Natural Science Edition),2013,33(2):89-94.)
[14]孟永昌,杨赛霓,史培军.基于改进遗传算法的路网应急疏散多目标优化[J].武汉大学学报(信息科学版),2014,39(2):201-205.(MENG Yongchang,YANG Saini,SHI Peijun.Multi-objective optimization of emergency evacuation using improved genetic algorithm[J].Geomatics and Information Science of Wuhan University,2014,39(2):201-205.)
[15]丁雨淋,何小波,朱庆,等.实时威胁态势感知的室内火灾疏散路径动态优化方法[J].测绘学报,2016,45(12):1464-1475.(DING Yulin,HE Xiaobo,ZHUQing,et al.A dynamic optimization method of indoor fire evacuation route based on real-time situation awareness[J].Acta Geodaetica et Cartographica Sinica,2016,45(12):1464-1475.)
[16]COLORNI A,DORIGO M,MANIEZZO V.Distributed optimization by ant colonies[C]∥Proceedings of the first European Conference on Artificial Life.[S.l.]:[s.n.],1992:134-142.
[17]覃远年,梁仲华.蚁群算法研究与应用的新进展[J].计算机工程与科学,2019,41(1):173-184.(QIN Yuannian,LIANG Zhonghua.New progress of the ant colony algorithm in research and applications[J].Computer Engineering&Science,2019,41(1):173-184.)
[18]ZENG M,WANG C.Evacuation route planning algorithm:longer route preferential[C]∥The 6th International Symposium on Neural Networks on Advances in Neural Networks.Heidelberg:Springer,2009.
[19]刘纪平,吴立新,董春,等.一种大规模空间数据流式并行处理方法研究[J].测绘科学,2016,41(1):89-93,75.(LIU Jiping,WU Lixin,DONG Chun,et al.Study on a streaming parallel method for massive spatial data processing[J].Science of Surveying and Mapping,2016,41(1):89-93,75.)