A GRASP with path-relinking for the p-median problem

Mauricio G. C. Resende (mgcrresearch.att.com)
Renato F. Werneck (rwerneckprinceton.edu)

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.

Keywords: location theory, GRASP, p-median, metaheuristic, path-relinking

Category 1: Applications -- OR and Management Sciences

Category 2: Combinatorial Optimization (Meta Heuristics )

Citation: AT&T Labs Research Technical Report TD-5E53XL, AT&T Labs Research, Florham Park, NJ 07932 USA. September 18, 2002.

Download: [PDF]

Entry Submitted: 09/18/2002
Entry Accepted: 09/18/2002
Entry Last Modified: 09/18/2002

Modify/Update this entry