Solving the p‐Center problem with Tabu Search and Variable Neighborhood Search

The p ‐Center problem consists of locating p facilities and assigning clients to them in order to minimize the maximum distance between a client and the facility to which he or she is allocated. In this paper, we present a basic Variable Neighborhood Search and two Tabu Search heuristics for the p ‐Center problem without the 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.