A Fast Swap-based Local Search Procedure for Location Problems
Mauricio G. C. Resende (mgcrresearch.att.com)
Abstract: We present a new implementation of a widely used swap-based local search procedure for the P-median problem, proposed in 1968 by Teitz and Bart. Our method produces the same output as the best alternatives described in the literature and, even though it does not have a better worst-case complexity, it can be significantly faster in practice: speedups of up to three orders of magnitude were observed. We also show that our method can be easily adapted to handle the facility location problem and to implement related procedures, such as path-relinking and tabu search.
Keywords: Location problems, p-median, local search
Category 1: Applications -- Science and Engineering (Facility Planning and Design )
Category 2: Combinatorial Optimization
Citation: AT&T Labs Research Technical Report TD-5R3KBH, September 4, 2003.
Entry Submitted: 09/04/2003
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|