The continuous maximal covering location problem in large-scale natural disaster rescue scenes

Abstract

This study proposes a continuous maximal covering location problem (C-MCLP) that is often confronted in the rescuing scenes of natural disasters such as earthquakes, floods, and storms. The aim of the research is to optimize (dynamically and rapidly) the continuous locations of the communication hub-centers (e.g., moving vehicles or boats) of the self-organizing mobile network that is quickly established in such signal-free fields. The proposed C-MCLP well represents the real emergency rescues, but it is more complex to solve than the traditional discrete MCLP models, where the hub facilities are typically immobile and placed only within a limited set of candidate sites. We developed two mixed-integer linear programming (MILP) models for the C-MCLP. The first model is the single-period C-MCLP model, which is applicable to a stochastic rescuing environment where the rescue teams (RTs) do not have planned movements and can move towards any direction. The second one is the multi-period C-MCLP model, which is for cases where RTs have planned movements in multiple periods/phases. We introduced a new linearization method for the non-linear Euclidean distance with a controllable approximation error allowance, by which the proposed models are linearized and can be solved optimally using commercial MIP solvers such as CPLEX and Lingo. To solve large-sized problems, we provide a MILP-based fix-and-optimize heuristic approach to obtain near-optimal solutions with high computational efficiency. Then we conduct simulation experiments to verify the proposed models and heuristic approach with an intended time-limit setting on small-sized and large-sized test problem instances, respectively, with up to 1000 nodes of rescue teams. Finally, experimental results are analyzed and compared with those obtained using the traditional k-means clustering algorithms, which confirm that the proposed models and approach are applicable for the C-MCLPs in emergency rescue scenes, and can yield rapid and good solutions.