A simple tabu search for warehouse location

The uncapacitated warehouse location problem (UWLP) is a heavily studied combinatorial optimization problem, which has been tackled by various approaches, such as linear-programming, branch and bound, genetic algorithms, and local search. This paper presents a 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 of size 2000 × 2000. Despite its conceptual and programming simplicity, the algorithm finds optimal solutions to all benchmarks very quickly and with very high frequencies. It also compares favorably with state-of-the-art genetic algorithms and should be a very valuable addition to the repertoire of tools for uncapacitated warehouse location due to its simplicity and effectiveness.