Premium
Two New Location Covering Problems: The Partial P ‐Center Problem and the Partial Set Covering Problem
Author(s) -
Daskin Mark S.,
Owen Susan Hesse
Publication year - 1999
Publication title -
geographical analysis
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.773
H-Index - 65
eISSN - 1538-4632
pISSN - 0016-7363
DOI - 10.1111/j.1538-4632.1999.tb00979.x
Subject(s) - lagrangian relaxation , set cover problem , covering problems , cover (algebra) , integer programming , mathematics , relaxation (psychology) , set (abstract data type) , fraction (chemistry) , mathematical optimization , center (category theory) , population , local search (optimization) , computer science , mechanical engineering , psychology , social psychology , chemistry , demography , organic chemistry , sociology , engineering , crystallography , programming language
Two new covering problems are introduced. The partial covering P ‐center problem minimizes a coverage distance in such a way that a given fraction of the population is covered. The partial set covering problem seeks the minimum number of facilities needed to cover an exogenously specified fraction of the population within a given coverage distance. The problems are formulated as integer linear programming problems. Bisection search algorithms are outlined for the two problems. The search algorithm repeatedly solves a Lagrangian relaxation of the maximal covering problem. Computational results for the Lagrangian relaxation of the maximal covering problem and for the bisection search algorithms are presented on problems with up to 150 nodes.