疏散规划的一种优化算法
|
摘要
疏散规划是一个特殊的空间网络分析应用,其核心问题是如何尽快为处于危险地区的公民制订合理有效的疏散路径以便尽快抵达安全的疏散地。求解这样的路径组合需在巨大的搜索空间中寻优,对于算法设计和实现是一个挑战。常用算法CCRP运算速度较慢,只能应用于小规模的路网。该文给出一种新型启发式算法CCRP++,使用双优先队列保存迭代计算过程中的有效信息,同时将多源最短路径搜索过程简化为单源最短路径搜索,有效压缩了CCRP算法中存在的冗余重复扩张。CCRP++算法将该问题的时间复杂度由CCRP的O(PNlog(N/S))降低为O(P(N/S)log(N/S)log(S))(P为疏散人数,N为网络节点数,S为源点数,假设源点均匀分布在网络中)。采用不同规模的实际路网数据进行实验,结果表明CCRP++算法在效率和可扩展性上均优于CCRP。
Evacuation Planning is a classical network flow optimization problem.It assigns optimized routes and schedules for each citizen to reach the safe destinations in case of huge disasters.Optimal evacuation plan should deliver routes considering evacuees′ personal location information and road network capacity.The goal is to let all the people not congested in the road segment and can arrive the destination as soon as possible.This problem is computationally challenging as it need to search in huge solution space.Until now,there is no efficient algorithm be able to generate evacuation plan efficiently.The recent heuristic algorithm CCRP lowered the complexity compared to previous solution.However,it still is not quick enough for the emergency system.Literature shows it needs more than one day to generate the evacuation plan even for a small town,need not to say the larger city.In this work,a novel heuristic algorithm CCRP++ was proposed,which greatly improved the efficiency of the algorithm.CCRP++ can use double priority queue to store the path information during the iterative computation,which helps to prune the "redundant expansion" in CCRP.Assuming the sources distributed evenly in the network,the complexity of CCRP is O(PNlog(N/S)) while CCRP++ is O(P(N/S)log(N/S)log(S))(where P is the number of evacuees,N is the number of nodes,S is the number of source.).The authors tested the two algorithms with real road network in 3 US cities and simulated evacuees,sources and destinations.The result shows CCRP++ outperforms CCRP in both efficiency and scalability.CCRP++ get 5 to 100 speedup depends on the size of the network.
Evacuation Planning is a classical network flow optimization problem.It assigns optimized routes and schedules for each citizen to reach the safe destinations in case of huge disasters.Optimal evacuation plan should deliver routes considering evacuees′ personal location information and road network capacity.The goal is to let all the people not congested in the road segment and can arrive the destination as soon as possible.This problem is computationally challenging as it need to search in huge solution space.Until now,there is no efficient algorithm be able to generate evacuation plan efficiently.The recent heuristic algorithm CCRP lowered the complexity compared to previous solution.However,it still is not quick enough for the emergency system.Literature shows it needs more than one day to generate the evacuation plan even for a small town,need not to say the larger city.In this work,a novel heuristic algorithm CCRP++ was proposed,which greatly improved the efficiency of the algorithm.CCRP++ can use double priority queue to store the path information during the iterative computation,which helps to prune the "redundant expansion" in CCRP.Assuming the sources distributed evenly in the network,the complexity of CCRP is O(PNlog(N/S)) while CCRP++ is O(P(N/S)log(N/S)log(S))(where P is the number of evacuees,N is the number of nodes,S is the number of source.).The authors tested the two algorithms with real road network in 3 US cities and simulated evacuees,sources and destinations.The result shows CCRP++ outperforms CCRP in both efficiency and scalability.CCRP++ get 5 to 100 speedup depends on the size of the network.
引文
[1]BAUMANN N,SKUTELLA M.Solving evacuation problems effi-ciently-earliest arrival flows with multiple sources[A].47th An-nual IEEE Symposium on Foundations of Computer Science[C].2006.FOCS'06.399-410.
[2]HAMACHER H W,TJANDRA S A.Mathematical Modeling of E-vacuation Problems:A State of the Art[R].Reports of theFraunhofer Institute for Technological and Industrial Mathe-matics(ITWM Report),2002,24,227-266.
[3]HPPPE B,TARDOS E.Polynomial time algorithms for some e-vacuation problems[A].5th Annual ACM-SIAM Symposium onDiscrete Algorithms[C].Arlington,VA,1994.433-441.
[4]LU Q,HUANG Y,SHEKHAR S.Evacuation planning:A ca-pacity constrained routing approach[J].Intelligence and Securi-ty Informatics,2003,2665:111-125.
[5]LU Q,GEORGY B,SHEKHAR S.Capacity constrained routing al-gorithms for evacuation planning:A summary of results[A].Proc.of 9th International Symposium on Spatial and TemporalDatabases[C].2005.291-307.
[6]SANGHO K,GEORGE B,SHEKHAR S.Evacuation route plan-ning:Scalable heuristics[A].15th ACM International Symposi-um on Advances in Geographic Information Systems[C].Seat-tle,WA,2007.1-8.
[7]AHUJA R K,MAGNANTI T L,ORLIN J B.Network Flows:Theory,Algorithms,and Applications[M].Prentice Hall,1993.
[8]CAI X,KLOKS T,WONG C K.Time-varying shortest path prob-lems with constraints[J].Networks,1997,29(3):141-149.
[9]CHABINI I.Discrete dynamic shortest path problems in trans-portation applications:Complexity and algorithms with optimalrun time[J].Transportation Research Record,1998,1645(1):170-175.
[10]CHALMET L,FRANCIS R,SAUNDERS P.Network modelsfor building evacuation[J].Fire Technology,1982,18:90-113.
[11]CHEN Y.Evacuation model and algorithms for emergency man-agement system[A].International Conference on TransportationEngineering[C].2007.3171-3177.
[12]KISKO T,FRANCIS R.Evacnet+:A computer program todetermine optimal building evacuation plans[J].Fire Safety,1985,9(2):211-222.
[13]尹大朏,方裕.应用于大规模灾害发生时进行人员疏散的快速疏散方法[P].专利授权号ZL201010279504.3.
[14]方裕,周成虎,景贵飞,等.第四代GIS软件研究[J].中国图象图形学报,2001(6):817-823.
[15]姜云昭,朱万红,邱国庆.地震次生灾害影响条件下人员疏散问题的研究[J].中国安全生产科学技术,2008(1):38-41.
[16]孔祥春.考虑交叉口延误的交通紧急疏散研究[D].天津大学,2007.
[17]潘忠.基于几何的人员疏散仿真研究[D].同济大学,2007.
[18]谢旭阳,任爱珠,周心权.高层建筑火灾最佳疏散路线的确定[J].自然灾害学报,2003,12(3):75-80.
[19]张江华,曹悦,朱道立,等.危险化学品事故应急疏散决策系统设计[J].科技导报,2005,25(7):47-51.
[20]何淑华,冯敏,陈伟玲.城市地震应急疏散规划编制研究——以《淄博市中心区地震应急疏散规划》为例[J].城市规划,2008(11):1-4.
[2]HAMACHER H W,TJANDRA S A.Mathematical Modeling of E-vacuation Problems:A State of the Art[R].Reports of theFraunhofer Institute for Technological and Industrial Mathe-matics(ITWM Report),2002,24,227-266.
[3]HPPPE B,TARDOS E.Polynomial time algorithms for some e-vacuation problems[A].5th Annual ACM-SIAM Symposium onDiscrete Algorithms[C].Arlington,VA,1994.433-441.
[4]LU Q,HUANG Y,SHEKHAR S.Evacuation planning:A ca-pacity constrained routing approach[J].Intelligence and Securi-ty Informatics,2003,2665:111-125.
[5]LU Q,GEORGY B,SHEKHAR S.Capacity constrained routing al-gorithms for evacuation planning:A summary of results[A].Proc.of 9th International Symposium on Spatial and TemporalDatabases[C].2005.291-307.
[6]SANGHO K,GEORGE B,SHEKHAR S.Evacuation route plan-ning:Scalable heuristics[A].15th ACM International Symposi-um on Advances in Geographic Information Systems[C].Seat-tle,WA,2007.1-8.
[7]AHUJA R K,MAGNANTI T L,ORLIN J B.Network Flows:Theory,Algorithms,and Applications[M].Prentice Hall,1993.
[8]CAI X,KLOKS T,WONG C K.Time-varying shortest path prob-lems with constraints[J].Networks,1997,29(3):141-149.
[9]CHABINI I.Discrete dynamic shortest path problems in trans-portation applications:Complexity and algorithms with optimalrun time[J].Transportation Research Record,1998,1645(1):170-175.
[10]CHALMET L,FRANCIS R,SAUNDERS P.Network modelsfor building evacuation[J].Fire Technology,1982,18:90-113.
[11]CHEN Y.Evacuation model and algorithms for emergency man-agement system[A].International Conference on TransportationEngineering[C].2007.3171-3177.
[12]KISKO T,FRANCIS R.Evacnet+:A computer program todetermine optimal building evacuation plans[J].Fire Safety,1985,9(2):211-222.
[13]尹大朏,方裕.应用于大规模灾害发生时进行人员疏散的快速疏散方法[P].专利授权号ZL201010279504.3.
[14]方裕,周成虎,景贵飞,等.第四代GIS软件研究[J].中国图象图形学报,2001(6):817-823.
[15]姜云昭,朱万红,邱国庆.地震次生灾害影响条件下人员疏散问题的研究[J].中国安全生产科学技术,2008(1):38-41.
[16]孔祥春.考虑交叉口延误的交通紧急疏散研究[D].天津大学,2007.
[17]潘忠.基于几何的人员疏散仿真研究[D].同济大学,2007.
[18]谢旭阳,任爱珠,周心权.高层建筑火灾最佳疏散路线的确定[J].自然灾害学报,2003,12(3):75-80.
[19]张江华,曹悦,朱道立,等.危险化学品事故应急疏散决策系统设计[J].科技导报,2005,25(7):47-51.
[20]何淑华,冯敏,陈伟玲.城市地震应急疏散规划编制研究——以《淄博市中心区地震应急疏散规划》为例[J].城市规划,2008(11):1-4.
版权所有：© 2023 中国地质图书馆 中国地质调查局地学文献中心