On the quickest evacuation location problem in humanitarian operations: multi-objective modelling and matheuristic solution

Effective evacuation planning is critical in humanitarian operations to save lives. This paper introduces the Quickest Evacuation Location Problem (QELP), a novel optimisation model that combines the quickest flow problem with discrete facility location to support humanitarian operations. Its scope falls into the field of enhancing evacuation planning and design 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, aiming to minimise the evacuation makespan and the total budget required to install and operate the shelters, while also balancing the utilisation rate of activated shelters. 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 approximating the Pareto Set on increasing-size networks. Despite the complexity of time-expanded networks, experiments on realistic instances demonstrate scalable performance and clear trade-offs among the three objectives, confirming the suitability of the QELP in providing decision-makers with valuable support for real-world planning processes in humanitarian operations.