The Quickest Evacuation Location Problem in Humanitarian Operations: A Multi-Objective Model Formulation and a Matheuristic Solution Approach

Disasters, both natural and man-made, affect millions of people every year. Recently, the frequency and severity of these disasters have been rising, emphasising the significance of humanitarian operations. Facility location problems and network flow problems are among the most important topics in humanitarian operations. This research introduces the Quickest Evacuation Location Problem (QELP), a novel optimisation problem aimed at supporting humanitarian operations by combining the quickest flow problem and the discrete facility location problem. Its scope falls into the field of evacuation planning and design, intending to enhance evacuation network design and planning by identifying, among a finite set of candidates, the set of shelters that would allow the quickest possible evacuation process. The QELP is first modelled by developing an ad-hoc network tool referred to as QELP-Time Expanded Network (QELP-TEN), which accounts for the lack of a predetermined set of sink nodes - as these need to be selected among the candidate sinks as part of the optimisation problem. To secure flexible and realistic decision support, a multi-objective mixed integer programming model is developed, aiming at minimising the evacuation makespan and the total budget required to install and operate the shelters while balancing the load of evacuees directed to each activated shelter. The Robust Augmented $\varepsilon$-constraint method (AUGMECON-R) is adopted as a solution scheme, and it is successfully combined with a novel Matheuristic approach to boost its performance while exploring the Pareto Set on increasing size networks. Despite the challenging complexity deriving from the use of time-expanded networks, experiments on realistic instances show scalable performance and the presence of regular trade-offs among the three objective functions (evacuation makespan, budget, and maximum load on shelters), thus confirming the suitability of the QELP to provide decision-makers with valuable support for real-world planning processes in humanitarian operations.