This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via HighWire Citing Articles via Google Scholar Google Scholar Articles by Ahuja, R. K. Articles by Scutellà, M. G. Search for Related Content

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

Department of Industrial and Systems Engineering, University of Florida, Gainesville, Florida 32611
Sloan School of Management, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139
Dipartimento di Informatica, Università di Pisa, Pisa, Italy
Dipartimento di Informatica, Università di Pisa, Pisa, Italy
Dipartimento di Informatica, Università di Pisa, Pisa, Italy
ahuja(ufl.edu
jorlin(mit.edu
pallo(di.unipi.it
scaparra(di.unipi.it
scut(di.unipi.it

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.

Key Words: location problems; large-scale optimization; neighborhood search; negative cycles
History: Received: June 11, 2003;

This article has been cited by other articles:

				R. K. Ahuja, K. C. Jha, and J. Liu Solving Real-Life Railroad Blocking Problems Interfaces, September 1, 2007; 37(5): 404 - 419. [Abstract] [PDF]

				A. Lim and X. Zhang A Two-Stage Heuristic with Ejection Pools and Generalized Ejection Chains for the Vehicle Routing Problem with Time Windows INFORMS Journal on Computing, January 1, 2007; 19(3): 443 - 457. [Abstract] [PDF]