Large-scale local search heuristics for the capacitated vertex p-center problem

This article 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 relocation 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.