A GRASP with path-relinking for the p-median problem
Mauricio G. C. Resende (mgcrresearch.att.com)
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.
Entry Submitted: 09/18/2002
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|