Large scale local search heuristics for the Capacitated Vertex p-Center Problem

This paper investigates the application of very-large neighborhood search techniques for solving the capacitated vertex $p$-center problem. We characterize a local search neighborhood in terms of path and cyclic exchanges of customers among facilities, and exploit principles borrowed from network optimization theory to efficiently detect cost decreasing solutions in such a neighborhood. We complement the multi-exchange methodology with a local reoptimization mechanism specifically designed to perform facility location adjustments. The validity of the proposed approach is supported by empirical investigation and performance comparisons with the commercial code CPLEX.