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/gean.1999.31.1.217
Subject(s) - set cover problem , lagrangian relaxation , covering problems , cover (algebra) , integer programming , fraction (chemistry) , mathematics , mathematical optimization , set (abstract data type) , relaxation (psychology) , center (category theory) , population , local search (optimization) , bisection method , 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.