A Two-Stage Iterated Local Search Algorithm for the Capacitated p-Center Problem

The capacitated p-center problem $(\mathrm{C}p\text{CP})$ is an extension of the classical p-center problem. It consists of choosing $p$ centers from a set of candidate centers and assigning each client to a center such that the total client demand assigned to each center does not exceed its given capacity. The objective of the $\mathrm{C}p\text{CP}$ is to minimize the maximum distance between each client and its assigned center. In this paper, we propose a two-stage iterated local search algorithm called TS-ILS to solve the $\mathbf{C}p\mathbf{CP}$ . The first stage uses a tabu search procedure to select centers and greedily assign clients to centers, while the second stage adopts a variable neighborhood search procedure to perform the fine-grained assignment of clients. Tested on 39 commonly studied instances in the literature, TS-ILS improves the best known results of the state-of-the-art metaheuristic algorithms on 18 instances and matches the records for the remaining ones within less run time.