Solving large p-median problems using a Lagrangean heuristic
Andréa Cynthia Santos (andreaisima.fr)
Abstract: The p-median problem consists in locating p medians in a given graph, such that the total cost of assigning each demand to the closest median is minimized. In this work, a Lagrangean heuristic is proposed and it uses two dual information to build primal solutions. It outperforms a classic heuristic based on the same Lagrangean relaxation. Variable fixing tests are used to reduce the size of the problems and a local search procedure is also applied. Variable fixing strategies eliminate 90% of arcs on average. Computational results are reported for large graph instances with about 4000 nodes and 14 millions arcs.
Keywords: Lagrangean heuristics, primal-dual heuristics, p-median problem
Category 1: Combinatorial Optimization (Approximation Algorithms )
Category 2: Applications -- OR and Management Sciences (Telecommunications )
Category 3: Applications -- Science and Engineering (Facility Planning and Design )
Citation: Technical report RR-09-03, 2009. Limos, Université Blaise Pascal. Complexe scientifique des Cézeaux, Aubière, France.
Entry Submitted: 06/03/2009
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|