Geoscience Reference
In-Depth Information
at least two demand points on the border of the minimal circle. Although several
algorithms to solve this problem have been proposed over time, the best known is the
method published in Elzinga and Hearn (
1972
) for the case of Euclidean distances.
When the radius of the circle is fixed, it may be not large enough to cover all
the demand points and, as in the discrete Maximal Covering Location Problem,
the objective is now to cover as much demand as possible. These maximal covering
problems have usually multiple solutions, maybe even a region of optimal solutions,
and this region may not even be convex (see Plastria
2002
). However, it can be
proved that there is an optimal solution which is either a demand point or an
intersection point of two circles centered at demand points (see Drezner
1981
and Chazelle and Lee
1986
for details on algorithms). There is a similar property
when the facilities can be located on any part of a network (Church and Meadows
1979
). Church (
1984
) shows an analogous property for planar maximal covering
problems with Euclidean or rectilinear distances.
More recently, Drezner et al. (
2004
) studied a gradual covering problem with
Euclidean distances where a finite set of points needs to be covered with one single
facility. If the facility can be located anywhere on the plane and the total cost of non-
covered points is minimized, then the solution is in the convex hull of the demand
points.
5.8
Conclusions
In this chapter we have provided an overview on covering problems with a special
emphasis on discrete models. Instead of providing a list of the many covering
models that can be found in the literature, we have focused on detailing those that
are considered to be more relevant because of the attention received in the literature
in the last decades. Moreover, we show that many of the models discussed in this
review can be seen as particular cases of a general covering model that we introduce
here. As far as we know, this is the first attempt to develop such a unified approach
for the study of set covering problems.
Having set covering problems received so much attention in the literature, it
seems that the number of theoretical results is too small. These results reduce
basically to some preprocessing rules and to the study of some facets. And none
of them has been used to develop an algorithm that can be considered to be a major
breakthrough in the area. Therefore, future research should try to make better use
of these results or obtain new theoretical properties for these problems. Particularly,
developing exact methods for covering models that are not the SCP seems highly
desirable.
Acknowledgements
Research supported by Fundación Séneca, project 08716/PI/08, ERDF funds
and Plan Nacional de Investigación Científica, Desarrollo e Innovación Tecnológica (I+D+I),
project MTM2012-36163-C06-04.
