A hybrid multistart heuristic for the uncapacitated facility location problem

Mauricio G. C. Resende (mgcrresearch.att.com)
Renato F. Werneck (rwerneckcs.princeton.edu)

Abstract: 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.

Keywords: facility location, local search, metaheuristics

Category 1: Applications -- Science and Engineering (Facility Planning and Design )

Category 2: Combinatorial Optimization

Category 3: Combinatorial Optimization (Meta Heuristics )

Citation: AT&T Labs Research Technical Report TD-5RELRR. September 15, 2003.

Download: [PDF]

Entry Submitted: 09/15/2003
Entry Accepted: 09/15/2003
Entry Last Modified: 09/22/2003

Modify/Update this entry