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 multiexchange 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. © 2004 Wiley Periodicals, Inc.