Some heuristic methods for solving p-median problems with a coverage constraint |
| |
Authors: | Jesú s Sá ez-Aguado,Paula Camelia Trandafir |
| |
Affiliation: | Departamento de Estad?´stica e Investigación Operativa Facultad de Ciencias, Universidad de Valladolid, c/Prado de la Magdalena s/n, 47005 Valladolid, Spain |
| |
Abstract: | The aim of this paper is to solve p-median problems with an additional coverage constraint. These problems arise in location applications, when the trade-off between distance and coverage is being calculated. Three kinds of heuristic algorithms are developed. First, local search procedures are designed both for constructing and improving feasible solutions. Second, a multistart GRASP heuristic is developed, based on the previous local search methods. Third, by employing Lagrangean relaxation methods, a very efficient Lagrangean heuristic algorithm is designed, which extends the well known algorithm of Handler and Zang, for constrained shortest path problems, to constrained p-median problems. Finally, a comparison of the computational efficiency of the developed methods is made between a variety of problems of different sizes. |
| |
Keywords: | Location p-Median Coverage constraint Local search GRASP Lagrangean relaxation |
本文献已被 ScienceDirect 等数据库收录! |
|