A New Heuristic for the Capacitated Vertex p-Center Problem

Abstract: A metaheuristic for the capacitated vertex p-center problem is presented. This is a well-known location problem that consists of placing p facilities and assigning customers to these in such a way that the largest distance between any customer and its associated facility is minimized. In addition, a capacity on demand for each facility is considered. The proposed metaheuristic framework integrates several components such as a greedy randomized adaptive procedure with biased sampling in its construction phase and iterated greedy with a variable neighborhood descent in its local search phase. The overall performance of the heuristic is numerically assessed on widely used benchmarks on location literature. The results indicate the proposed heuristic outperforms the best existing heuristic.