Geoscience Reference
In-Depth Information
The first mentions to covering problems in literature can be found in Berge (
1957
)
where the problem of finding a minimum cover on a graph is introduced and a
theorem that provides an algorithm to find a minimum cover using a matching is
stated and in Hakimi (
1965
) where it must be decided on the minimum number of
police patrols required to protect a highway network. However, the problem was
mathematically formulated for the first time in the Location area in Toregas et al.
(
1971
), although out of a Location context it had already been formulated in Roth
(
1969
).
In general, there are two types of covering problems:
set covering
and
maximal
covering
. In a set covering problem (Toregas et al.
1971
), the total cost of locating a
set of facilities so that every customer is covered must be minimized. Particularly, if
all the facilities have the same location cost, this is equivalent to minimize the total
number of facilities to be located. A quick analysis of a solution to the set covering
problem will usually show that with just a few facilities it is possible to cover an
important percentage of the demand and that only by locating a high number full
coverage can be achieved. Since locating as many facilities as needed may not
be possible (e.g., due to budget constraints), a natural variant is to maximize the
number of customers that are covered (or, equivalently, minimize the non-covered
customers) by locating a fixed number of facilities. This problem is the maximal
covering problem which was introduced in Church and ReVelle (
1974
).
According to Balas and Padberg (
1976
), the set covering problem is one of the
three special structures in pure integer programming with the most wide-spread
applications, together with set partitioning and the traveling salesman problem. Just
to mention a few, set covering models have been applied in the following areas:
analysis of markets (Storbeck
1988
), archaeology (Bell and Church
1985
), crew
scheduling (Ceria et al.
1998
), deployment of emergency services (Toregas et al.
1971
; Eaton et al.
1986
), mail advertising (Dwyer and Evans
1981
), metallurgy
(Vasko et al.
1989
), nature reserve selection (Church et al.
1996
) and Steiner
matrices (Feo and Resende
1989
).
Due to its importance and the rich literature on this topic, it is not surprising that
reviews have been published regularly. The first one is Christofides and Korman
(
1975
), a comparison of five computational methods for the set covering problem.
Later, we have Chung (
1986
) which examines several applications of the maximal
covering model to problems that do not belong to the Location field, and ReVelle
(
1989
), a review focused on emergency service. Broader reviews are Schilling et al.
(
1993
), an exhaustive survey on covering models in Location reviewing 96 papers,
and Caprara et al. (
2000
), a comparison of recent algorithms (exact and heuristic)
for the set covering problem. Plastria (
2002
) is an exhaustive review of continuous
covering models and it is a perfect complement to this chapter. More recently, we
have Berman et al. (
2010
) which considers some of the latest trends by reviewing
gradual coverage, cooperative coverage, and variable radius coverage models, and
Snyder (
2011
) which reviews the seminal covering models plus some extensions.
Finally, the most recent survey is Farahani et al. (
2012
), an exhaustive list of models
reviewing more than 150 papers that study covering problems in the area of facility
