Decomposition algorithms for the design of a nonsimultaneous capacitated evacuation tree network

April K. Andreas, J. Cole Smith

Research output: Contribution to journalArticlepeer-review

35 Scopus citations


In this article, we examine the design of an evacuation tree, in which evacuation is subject to capacity restrictions on arcs. The cost of evacuating people in the network is determined by the sum of penalties incurred on arcs on which they travel, where penalties are determined according to a nondecreasing function of time. Given a discrete set of disaster scenarios affecting network population, arc capacities, transit times, and penalty functions, we seek to establish an optimal a priori evacuation tree that minimizes the expected evacuation penalty. The solution strategy is based on Benders decomposition, in which the master problem is a mixed-integer program and each subproblem is a time-expanded network flow problem. We provide efficient methods for obtaining primal and dual subproblem solutions, and analyze techniques for improving the strength of the master problem formulation, thus reducing the number of master problem solutions required for the algorithm's convergence. We provide computational results to compare the efficiency of our methods on a set of randomly generated test instances.

Original languageEnglish (US)
Pages (from-to)91-103
Number of pages13
Issue number2
StatePublished - Mar 2009
Externally publishedYes


  • Asynchronous flows
  • Benders decomposition
  • Evacuation
  • Integer programming

ASJC Scopus subject areas

  • Information Systems
  • Computer Networks and Communications


Dive into the research topics of 'Decomposition algorithms for the design of a nonsimultaneous capacitated evacuation tree network'. Together they form a unique fingerprint.

Cite this