A GRASP with path-relinking for the p-median problem, with M. G. C. Resende. Technical Report TD-5E53XL, AT&T Labs Research, 2002.

Abstract: Given n customers and a set F of m potential facilities, the p-median problem consists in finding a subset of F with p facilities such that the cost of serving all customers is minimized. This is a well-known NP-complete problem with important applications in location science and classification (clustering). We present here a GRASP (Greedy Randomized Adaptive Search Procedure) with path-relinking to find near-optimal solutions to this problem. Empirical results on instances from the literature suggest that this is a very robust algorithm, performing at least as well as other methods, and often better in terms of both running time and solution quality.

Important note: Please see the most recent version of this paper.