A Multi-Exchange Heuristic for the Single-Source Capacitated Facility Location Problem

We present a very large-scale neighborhood (VLSN) search algorithm for the capacitated facility location problem with single-source constraints. The neighborhood structures are induced by customer multi-exchanges and by facility moves. We consider both traditional single-customer multi-exchanges, detected on a suitably defined customer improvement graph, and more innovative multicustomer multi-exchanges, detected on a facility improvement graph dynamically built through the use of a greedy scheme. Computational results for some benchmark instances are reported that demonstrate the effectiveness of the approach for solving large-scale problems. A further test on real data involving an Italian factory is also presented.

• 저널Management Science · 50(6) · 749–760
• 토픽Vehicle Routing Optimization Methods · Industrial and Manufacturing Engineering
• DOI10.1287/mnsc.1030.0193
• 저자Ravindra K. Ahuja, James B. Orlin, Stefano Pallottino, Maria Paola Scaparra, Maria Grazia Scutellà