Journal
NETWORKS
Volume 53, Issue 2, Pages 91-103Publisher
WILEY
DOI: 10.1002/net.20278
Keywords
evacuation; benders decomposition; asynchronous flows; integer programming
Ask authors/readers for more resources
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. (C) 2008 Wiley Periodicals, Inc. NETWORKS, Vol. 53(2), 91-103 2009
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available