Optimization Online


A fast swap-based local search procedure for location problems

Mauricio G. C. Resende (mgcr***at***research.att.com)
Renato F. Werneck (rwerneck***at***cs.princeton.edu)

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 its worst-case complexity is similar, 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: p-median problem, location theory, local search

Category 1: Applications -- OR and Management Sciences

Category 2: Global Optimization (Applications )

Category 3: Combinatorial Optimization (Other )

Citation: AT&T Labs Research Technical Report TD-5E4QKA, AT&T Labs Research, Florham Park, NJ 07932 USA, September 2002. Revised December 2004.

Download: [PDF]

Entry Submitted: 09/24/2002
Entry Accepted: 09/24/2002
Entry Last Modified: 12/10/2004

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society