Premium
Large‐scale local search heuristics for the capacitated vertex p ‐center problem
Author(s) -
Scaparra Maria Paola,
Pallottino Stefano,
Scutellà Maria Grazia
Publication year - 2004
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.20000
Subject(s) - heuristics , facility location problem , mathematical optimization , computer science , local search (optimization) , exploit , complement (music) , vertex (graph theory) , parameterized complexity , relocation , variable neighborhood search , combinatorial optimization , metaheuristic , theoretical computer science , mathematics , algorithm , graph , biochemistry , chemistry , computer security , complementation , programming language , gene , phenotype
Abstract 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.