Branch and Bound Algorithms for Static and Robust Dynamic Evacuation-Location Problem in Emergency Logistics

Evacuating people to the safe zones is the most crucial operation in many disasters. We have presented mathematical models in this paper, to combine the locational decisions with the max-flow problem in order to select the safe destination that maximizes the number of dispatched people, both for the static and dynamic cases.
Existing frameworks for emergency logistics, address the evacuation process based on fixed and pre-determined destinations usually with a strategic perspective. The unpredictable and turbulent nature of a disaster may, however, disrupt the predictions.
Furthermore, the primary goal in emergency situations is to dispatch people from the danger zone to a safe place, no matter where. A non-linear integer programming model is developed in this paper for selecting one destination in a capacitated network. We have also formulated the robust counterpart of the dynamic model in order to contribute the uncertainty of the capacity of routes during a disaster.
The special structure of the model and its similarity to the max-flow problem let us develop exact algorithms and heuristics for the single destination location problem. The solution methods are based on combining a branch and bound approach with the existing algorithms for the max-flow problem.
Our proposed heuristics use the idea of adding a super-sink to the network to generate upper bounds very fast. The exact algorithms as well as the heuristics are tested on randomly generated instances as well as a real world network. The mean and variance of their computation times are reported. They are compared according to their performance (gap to optimality) and their behavior amongst different categories of the graphs. We have also used the real data for Mitte-center berlin to implement our algorithms for an existing data set. The results of the algorithms for this case are also reported in the results section.