On the Quickest Evacuation Location Problem in Humanitarian Operations : Multi-Objective Modelling and Matheuristic Solution

This paper 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, with the goal of enhancing 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. To secure flexible and realistic decision support, a multi-objective mixed integer programming model is developed, looking for 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 ε-constraint method is adopted as a solution scheme, and it is successfully combined with an original 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