A location-allocation model and algorithm for optimally locating shelters to minimize evacuation times

Abstract

Location â allocation models are designed to seek the concurrent location of a set of service facilities and an allocation scheme to satisfy the demands of a set of customers or users of a given system. If the location-allocation model is based on a graph-theoretic formulation, then the demand-fulfilling items will move from a designated origin or origins, through arcs and transshipment nodes, to a set of destinations selected by the model. It is suggested in this research effort that such a modeling structure may be employed to simulate transportation evacuation conditions that may arise in the case of a natural disaster, namely a hurricane. A nonlinear mixed integer mathematical program is formulated to route passengers in automobiles on paths in the transportation network, such that the endangered area is evacuated in the minimum amount of time. One heuristic and two exact, convergent, implicit enumeration algorithms based on the generalized Benders' decomposition method are presented. The algorithms are designed to exploit the inherent problem structure. Computational experience is provided against a set of realistic test problems formulated on the Virginia Beach network. Potential avenues for further research are also explored.