Capacity Constrained Routing Algorithms for Evacuation Planning: A Summary of Results
Capacity Constrained Routing Algorithms for Evacuation Planning: A Summary of Results
复制标题
DOI：
10.1007/11535331_17
复制
发表时间：
2005-08
期刊：
影响因子：
--
通讯作者：
Qingsong Lu;Betsy George;S. Shekhar
中科院分区：
文献类型：
--
作者：
Qingsong Lu;Betsy George;S. Shekhar
疏散规划对于许多重要应用至关重要，例如灾害应急管理和国土防御准备。需要有效的工具来制定疏散计划，确定在发生自然灾害或恐怖袭击时将受影响人口疏散到安全地带的路线和时间表。现有的线性规划方法使用时间扩展网络来计算最优疏散计划，并且需要用户提供疏散时间的上界。它具有高计算成本，并且可能无法扩展到城市场景中的大型交通网络。在本文中，我们提出了一种启发式算法，即容量约束路径规划（CCRP），它产生的疏散规划问题的次优解。CCRP模型容量作为一个时间序列，并使用容量约束路由的方法，将路由容量的限制。它解决了线性规划方法的局限性，只使用原始的疏散网络，它不需要事先知道的疏散时间。各种网络配置的性能评估表明，CCRP算法产生高质量的解决方案，并显着降低了计算成本相比，线性规划方法，产生最佳的解决方案。CCRP还可以根据疏散人数和网络规模进行扩展。
Evacuation planning is critical for numerous important applications, e.g. disaster emergency management and homeland defense preparation. Efficient tools are needed to produce evacuation plans that identify routes and schedules to evacuate affected populations to safety in the event of natural disasters or terrorist attacks. The existing linear programming approach uses time-expanded networks to compute the optimal evacuation plan and requires a user-provided upper bound on evacuation time. It suffers from high computational cost and may not scale up to large transportation networks in urban scenarios. In this paper we present a heuristic algorithm, namely Capacity Constrained Route Planner(CCRP), which produces sub-optimal solution for the evacuation planning problem. CCRP models capacity as a time series and uses a capacity constrained routing approach to incorporate route capacity constraints. It addresses the limitations of linear programming approach by using only the original evacuation network and it does not require prior knowledge of evacuation time. Performance evaluation on various network configurations shows that the CCRP algorithm produces high quality solutions, and significantly reduces the computational cost compared to linear programming approach that produces optimal solutions. CCRP is also scalable to the number of evacuees and the size of the network.