A fast swap-based local search procedure for location problems |
| |
Authors: | Mauricio G. C. Resende Renato F. Werneck |
| |
Affiliation: | (1) AT&T Labs Research, 180 Park Avenue, Florham Park, NJ 07932, USA;(2) Department of Computer Science, Princeton University, 35 Olden Street, Princeton, NJ 08544, USA |
| |
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. R. F. Werneck: The results presented in this paper were obtained while this author was a summer intern at AT&T Labs Research. |
| |
Keywords: | Local search p-Median Facility location Experimental analysis Reordering problem |
本文献已被 SpringerLink 等数据库收录! |
|