Covering Location Problems - Location Science - page 92

location. More focused as a detailed tutorial than as a proper survey, Daskin ( 1995 )
is an excellent introduction to the basic properties of covering models.
At this point, it must be said that there are many different models involving
covering and that the goal of this chapter is not to cover them all but to provide
an insight on the main models and results on the topic. Particularly, we focus on
discrete models because they have received most of the attention in literature. The
rest of this chapter is organized as follows: the main models from the literature
are obtained in Sect. 5.2 as particular cases of a general model. Section 5.3
summarizes the main theoretical results on two of the main models (Set Covering
and Maximal Covering Location). Then, we survey exact (Sect. 5.4 ) and heuristic
(Sect. 5.5 ) solution methods. Since Lagrangian relaxation technique is widely used
for approaching covering models, we extend it to the general model described
in Sect. 5.6 . Finally, although the focus of this chapter is on discrete models,
some information on continuous covering is provided in Sect. 5.7 for the sake of
completeness.

5.2 Models

We will use a general covering model to present as particular cases the main
covering location problems in the literature as well as several other basic location
problems which can be also considered sophisticated extensions of covering models.
Let J Df 1;:::;n g be the set of customers (also called demand points) and let
I Df 1;:::;m g be the set of potential centers (facilities). Since many applications
of covering models come from Location, we will use indistinctively “sites” for
customers and potential centers. For each pair .i;j/ 2 I J, a known constant
a ij 2f 0;1 g represents whether demand point j can be covered (value one) or not
(value zero) by a center installed at site i. These constants can be obtained with
different procedures depending on the model under consideration as we will see
below.
Associated to each i 2 I, a fixed cost f i 0 has to be paid for opening a center
at site i. In some models it is possible to open more than one center at the same
site. In this case we assume that the cost of the centers to be opened in i 2 I is
equal (i.e., f i is the opening cost for all centers to be opened at site i). Each demand
point j 2 J must be covered by at least b j 2

0 facilities, where b j D 0 if site j
does not need to be covered. Besides, a maximum number of p 2

Z

Z C facilities can
be opened (note that when the fixed costs of the centers are zero, this maximum
number is always reached by some optimal solution).
Non-negative integer variables y i represent the number of facilities to be opened
at site i 2 I. These are the main location variables and they will be explicitly present
in all the particular cases that are obtained from the general model. The maximum
number of facilities that can be opened at site i is given by the constant e i 2 Z C .

Particularly, if e i D 1,theny i is a binary variable that takes value one if a facility is
located at site i (and zero otherwise).