A conflict-based path-generation heuristic for evacuation planning

Victor Pillac, Pascal Van Hentenryck and Caroline Even

Transportation Research Part B: Methodological, 2016, vol. 83, issue C, 136-150

Abstract: Evacuation planning and scheduling is a critical aspect of disaster management and national security applications. This paper proposes a conflict-based path-generation approach for evacuation planning. Its key idea is to decompose the evacuation planning problem into a master and a subproblem. The subproblem generates new evacuation paths for each evacuated area, while the master problem optimizes the flow of evacuees and produce an evacuation plan. Each new path is generated to remedy conflicts in the evacuation flows and adds new columns and a new row in the master problem. The algorithm is applied to a set of large-scale evacuation scenarios ranging from the Hawkesbury-Nepean flood plain (West Sydney, Australia) which require evacuating in the order of 70,000 persons, to the New Orleans metropolitan area and its 1,000,000 residents. Experiments illustrate the scalability of the approach which is able to produce evacuation for scenarios with more than 1200 nodes, while a direct Mixed Integer Programming formulation becomes intractable for instances with more than 5 nodes. With this approach, realistic evacuations scenarios can be solved near-optimally in reasonable time, supporting both evacuation planning in strategic, tactical, and operational environments.

Keywords: Evacuation planning and scheduling; Regional evacuation; Disaster management; Conflict-based path generation (search for similar items in EconPapers)
Date: 2016
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (11)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0191261515002027
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:transb:v:83:y:2016:i:c:p:136-150

Ordering information: This journal article can be ordered from
http://www.elsevier.com/wps/find/supportfaq.cws_home/regional
https://shop.elsevie ... _01_ooc_1&version=01

DOI: 10.1016/j.trb.2015.09.008

Access Statistics for this article

Transportation Research Part B: Methodological is currently edited by Fred Mannering

More articles in Transportation Research Part B: Methodological from Elsevier
Bibliographic data for series maintained by Catherine Liu ().