Tech Report CS-02-05

A Simple Tabu Search for Warehouse Location

Laurent Michel and Pascal Van Hentenryck

April 2002


The uncapacitated warehouse location problem (UWLP) has been studied heavily in mathematical programming but has received limited attention from the local search community. This paper presents an simple, yet robust and efficient, tabu search algorithm for the UWLP. The algorithm was evaluated on the standard OR Library benchmarks and on the M* instances which are very challenging for mathematical programming approaches. The benchmarks include instances whose sizes are 100x1000 and 500x500. Despite its simplicity, the algorithm finds optimal solutions to all benchmarks quickly and with very high frequencies. It also compares favorably with state-of-the-art genetic algorithms.

(complete text in pdf or gzipped postscript)