Improving the Quality of Heuristic Solutions for the Capacitated Vertex p-Center Problem through Iterated Greedy Local Search and Variable Neighborhood Descent

Abstract: The capacitated vertex p-center problem is a well-known location problem that consists of placing p facilities and assigning customers to each of these facilities so as to minimize the largest distance between any customer and its assigned facility, subject to demand capacity constraints for each facility. In this work, a metaheuristic for this location problem that integrates several components such as greedy randomized adaptive search procedures with probabilistic sampling, iterated greedy local search and variable neighborhood descent, is presented. Empirical evidence over a widely used set of benchmarks on location literature reveals the positive impact of each of the developed components. Furthermore, it is found empirically the proposed heuristic outperforms the best existing heuristic for this problem.