Capacity Constrained Routing Algorithms for Evacuation Route Planning
2006-05-04
Loading...
View/Download File
Persistent link to this item
Statistics
View StatisticsJournal Title
Journal ISSN
Volume Title
Title
Capacity Constrained Routing Algorithms for Evacuation Route Planning
Authors
Published Date
2006-05-04
Publisher
Type
Report
Abstract
Evacuation route planning identifies paths in a given transportation network to minimize the time needed to move vulnerable populations to safe destinations. Evacuation route planning is critical for numerous important applications like disaster emergency management and homeland defense preparation. It is computationally challenging because the number of evacuees often far exceeds the capacity, (ie.) the number of people that can move along the road segments in a unit time. Linear Programming(LP) based methods using time expanded networks can take hours to days of computation for metropolitan sized problems. In this paper, we propose a new approach, namely a capacity constrained routing planner which models capacity as a time series and generalizes shortest path algorithms to incorporate capacity constraints. We characterize the design space for reducing the computational cost. Analytical cost model and experiment results show that the proposed algorithm is faster than the LP based algorithms and requires less memory. Experimental evaluation using various network configurations also shows that the proposed algorithm produces solutions that are comparable to those produced by LP based algorithms while significantly reducing the computational cost.
Keywords
Description
Related to
Replaces
License
Series/Report Number
Funding information
Isbn identifier
Doi identifier
Previously Published Citation
Suggested citation
Lu, Qingsong; George, Betsy; Shekhar, Shashi. (2006). Capacity Constrained Routing Algorithms for Evacuation Route Planning. Retrieved from the University Digital Conservancy, https://hdl.handle.net/11299/215702.
Content distributed via the University Digital Conservancy may be subject to additional license and use restrictions applied by the depositor. By using these files, users agree to the Terms of Use. Materials in the UDC may contain content that is disturbing and/or harmful. For more information, please see our statement on harmful content in digital repositories.