Capacity Constrained Routing Algorithms for Evacuation Planning : A Summary of Results
2005-05-31
Loading...
View/Download File
Persistent link to this item
Statistics
View StatisticsJournal Title
Journal ISSN
Volume Title
Title
Capacity Constrained Routing Algorithms for Evacuation Planning : A Summary of Results
Authors
Published Date
2005-05-31
Publisher
Type
Report
Abstract
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 capaci ty 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. We also provide a discussion on the formulation of a new optimal algorithm that uses A* search to find the optimal solution for evacuation planning. We prove that the heuristic function used in this A* formulation is monotone and admissible.
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. (2005). Capacity Constrained Routing Algorithms for Evacuation Planning : A Summary of Results. Retrieved from the University Digital Conservancy, https://hdl.handle.net/11299/215664.
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.