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.
Citation
AT&T Labs Research Technical Report TD-5E53XL, AT&T Labs Research, Florham Park, NJ 07932 USA. September 18, 2002.