【摘要】 疏散规划是一个特殊的空间网络分析应用,其核心问题是如何尽快为处于危险地区的公民制订合理有效的疏散路径以便尽快抵达安全的疏散地。求解这样的路径组合需在巨大的搜索空间中寻优,对于算法设计和实现是一个挑战。常用算法CCRP运算速度较慢,只能应用于小规模的路网。该文给出一种新型启发式算法CCRP++,使用双优先队列保存迭代计算过程中的有效信息,同时将多源最短路径搜索过程简化为单源最短路径搜索,有效压缩了CCRP算法中存在的冗余重复扩张。CCRP++算法将该问题的时间复杂度由CCRP的O(PNlog(N/S))降低为O(P(N/S)log(N/S)log(S))(P为疏散人数,N为网络节点数,S为源点数,假设源点均匀分布在网络中)。采用不同规模的实际路网数据进行实验,结果表明CCRP++算法在效率和可扩展性上均优于CCRP。更多还原

【Abstract】 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.更多还原