A Vertex Weighting-Based Double-Tabu Search Algorithm for the Classical P-Center Problem

The p-center problem, which is NP-hard, aims to select p centers from a set of candidates to serve all clients while minimizing the maximum distance between each client and its assigned center. To solve this challenging optimization problem, we transform the p-center problem into a series of decision subproblems, and propose a vertex weighting-based double-tabu search (VWDT) algorithm. It integrates a vertex weighting strategy and a double-tabu search which combines both solution-based and attribute-based tabu strategies to help the search escape the local optima. Computational experiments on 174 public benchmark instances in the literature show that VWDT is highly competitive comparing to the state-of-the-art methods. Specifically, VWDT improves the previous best known results for 26 out of 90 large instances and matches the best results for all the remaining 148 ones. Apart from the improvements in solution quality, VWDT is much faster than other state-of-the-art algorithms in the literature, especially on some large instances. Furthermore, we perform additional experiments to analyze the impact of the key components to VWDT, such as the vertex weighting and the double-tabu search strategy.