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.
Citation
Technical report RR-09-03, 2009. Limos, Université Blaise Pascal. Complexe scientifique des Cézeaux, Aubière, France.