M.G.C. Resende and R.F. Werneck
European J. of Operational Research, vol. 174, pp. 54-68, 2006.
We present a multistart
heuristic for the uncapacitated facility location problem, based on a
very successful method we originally developed for the P-median
problem. We show extensive empirical evidence to the effectiveness of
our algorithm in practice. For most benchmarks instances in the
literature, we obtain solutions that are either optimal or a fraction
of a percentage point away from it. Even for pathological instances
(created with the sole purpose of being hard to tackle), our algorithm
can get very close to optimality if given enough time. It consistently
outperforms other heuristics in the literature.
PDF file of full paper
DJVU file of full paper
Mauricio G.C. Resende's Home PageLast modified: 7 July 2006