Groupe d’études et de recherche en analyse des décisions

G-2000-35

Solving the p-Center Problem with Tabu Search and Variable Neighborhood Search

, et

The p-Center problem consists in locating p facilities and assigning clients to them in order to minimize the maximum distance between a client and the facility to which he is allocated. In this paper we present a basic Variable Neighborhood Search and two Tabu Search heuristics for the p-Center problem without triangle inequality. Both proposed methods use the 1-interchange (or vertex substitution) neighborhood structure. We show how this neighborhood can be used even more efficiently than for solving the p-Median problem. Multistart 1-interchange, Variable Neighborhood Search, Tabu search and a few early heuristics are compared on small and large scale test problems from the literature.

, 28 pages

Ce cahier a été révisé en avril 2001