Article ID: | iaor20073542 |
Country: | United States |
Volume: | 50 |
Issue: | 6 |
Start Page Number: | 749 |
End Page Number: | 760 |
Publication Date: | Jun 2004 |
Journal: | Management Science |
Authors: | Scutell Maria Grazia, Orlin James B., Ahuja R.K., Pallottino P., Scaparra M.P. |
Keywords: | heuristics: local search, facilities |
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.