Solving the planar p-median problem by variable neighborhood and concentric searches

Zvi Drezner (1) , Jack Brimberg (2) , Nenad Mladenovic (3) , Said Salhi (4)

1 CSU - California State University [Fullerton]
2 Royal Military College of Canada
3 LAMIH - Laboratoire d'Automatique, de Mécanique et d'Informatique industrielles et Humaines - UMR 8201
4 UK - University of Kentucky

Two new approaches for the solution of the p-median problem in the plane are proposed. One is a Variable Neighborhood Search and the other one is a concentric search. Both approaches are enhanced by a front-end procedure for finding good starting solutions and a decomposition heuristic acting as a post optimization procedure. Computational results confirm the effectiveness of the proposed algorithms.

Domaines: Informatique [cs]

Zvi Drezner, Jack Brimberg, Nenad Mladenovic, Said Salhi. Solving the planar p-median problem by variable neighborhood and concentric searches. Journal of Global Optimization, 2015, 63 (3), pp.501-514. ⟨10.1007/s10898-014-0183-1⟩. ⟨hal-03401536⟩