A capacitated network flow optimization approach for short notice evacuation planning

Gino J. Lim, Shabnam Zangeneh, M. Reza Baharnemati and Tiravat Assavapokee

European Journal of Operational Research, 2012, vol. 223, issue 1, 234-245

Abstract: We present a capacity constrained network flow optimization approach for finding evacuation paths, flows and schedules so as to maximize the total evacuees for short notice evacuation planning (SNEP). Due to dynamic nature of this optimization problem, we first construct a time-expanded network that expands the static network over the planning horizon for every time interval. Since the resulting evacuation networks become extremely large to solve, we have developed Evacuation Scheduling Algorithm (ESA) to expedite the solution process. ESA utilizes Dijkstra’s algorithm for finding the evacuation paths and a greedy algorithm for finding the maximum flow of each path and the schedule to execute the flow for each time interval. We show that the complexity of ESA is O(|Nc|·n2)+O(|Nc|·m·T). Numerical experiments show a tremendous advantage of ESA over an exact algorithm (CCEP) in computation time by running up to 41,682 faster than CCEP. In many test network instances, CCEP failed to find a solution within 12hours while ESA converged to a solution in less than 0.03seconds.

Keywords: Capacitated network flow problem; Evacuation planning; Time-expanded network; Shortest path (search for similar items in EconPapers)
Date: 2012
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (23)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221712004596
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:ejores:v:223:y:2012:i:1:p:234-245

DOI: 10.1016/j.ejor.2012.06.004

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().