Optimization Online


A Capacitated Network Flow Optimization Approach for Short Notice Evacuation Planning

Gino J Lim(ginolim***at***uh.edu)
Shabnam Zangeneh(shzangeneh***at***hotmail.com)
MohammadReza Banarnemati(baharnemati***at***gmail.com)
Tiravat Assavapokee(tiravata***at***gmail.com)

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 timeexpanded 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. 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 12 hours while ESA converged to a solution in less than 0.03 seconds.

Keywords: Capacitated Network Flow Problem, Evacuation Planning,

Category 1: Applications -- OR and Management Sciences

Citation: Accepted for publication, European Journal of Operational Research, May 2012.

Download: [PDF]

Entry Submitted: 06/02/2012
Entry Accepted: 06/03/2012
Entry Last Modified: 06/02/2012

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society