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 Neighourhood 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) neighbourhood structure. We show how this neighbourhood can be used even more efficiently than for solving the p-Median problem. Multistart 1-interchange, Variable Neighbourhood Search, Tabu Search, and a few early heuristics are compared on small- and large-scale test problems from the literature.
