Exploiting flat subspaces in local search for p-Center problem and two fault-tolerant variants

In this paper, local search algorithms are proposed for the p-Center, α-Neighbour p-Center and p-Next Center facility location problems. The α-Neighbour p-Center and p-Next Center problems may be viewed as two fault-tolerant variants of the p-Center problem. The algorithm proposed for p-Center outperforms the most recent state-of-the-art metaheuristic for this problem using standard datasets. The proposed algorithm for p-Next Center also outperforms an existing, more complex, state-of-the-art metaheuristic for this problem. The algorithm proposed for α-Neighbour p-Center is the first metaheuristic for this problem, to the best of the author's knowledge. The proposed algorithms share a common design, which is the integration of the first-improvement local search with strategies to exploit flat subspaces in the search space. The overall success of this design paradigm motivates further investigation about its properties and applications to similar NP-hard optimisation problems.