Covering Location Problems - Location Science - page 96

Backup Set Covering Problems: Several models can be grouped under this name.
The common idea is to cover the demand points with more than one facility
in order to guarantee the coverage in case of either failure or overflow in one
or some of the centers (in this sense, the RCLP can be considered a backup
problem). There are two natural goals: minimization of the number of open
facilities and maximization of the backup coverage. Sometimes this problem
has been approached from the point of view of multiobjective optimization as,
for example, in Storbeck and Vohra ( 1988 ) and model BACOP1 in Hogan and
ReVelle ( 1986 ). Some other times, both objectives are combined into a unique
function as in model BACOP2 in Hogan and ReVelle ( 1986 ). Details are provided
next.
Coverage of all demand points is not mandatory, and each site can host several
facilities. Demands t j are associated to points j 2 J. A maximum number of
p facilities can be opened (h D p). Values a ij are obtained as in most of the
previous models. A parameter 0<LJ<1measures the relative importance of
covering once or twice each demand point: the smaller LJ is, the more importance
is given to cover each point twice. The goal here is to maximize the demand
covered by the facilities and also the demand covered twice, using LJ to give each
objective its relative importance. Taking this into account, we define f i D 0 8 i 2
I, e i D p 8 i 2 I, g jk D 0 8 j 2 J, 8 k 3 and b j D 0 8 j 2 J. Variables w j1
are used to represent whether customer j is covered or not and variables w j2
are used to check whether j is covered twice or not. We define g j1 D LJt j
and g j2 D .1 LJ/t j . Model (COV) is valid when LJ 1=2.WhenLJ<1=2,
constraints w j1 w j2 8 j 2 J must be included to preserve the correct definition
of the w -variables.
Batta and Mannur ( 1990 ) propose a different criterion for coverage which
can also be viewed as a particular case of (COV). Recently, Curtin et al.
( 2010 ) developed a backup coverage model in order to locate police patrols,
where a priority t j of crime incident in j 2 J is known, the number of police
patrols is limited to p and a ij takes value one if, and only if, a patrol located
at i can cover a crime incident located at j. The model is called PPAC and
is a particular case of (COV) obtained by defining f i D 0 8 i 2 I, h D p,
g jk D t j 8 k, b j D 0 8 j 2 J,ande i D 1 8 i 2 I.
Maximum Expected Covering Location Problem: Several covering location
models are based on probabilistic principles. One of the most important is
the Maximum Expected Covering Location Problem (MECLP) (Daskin 1983 ),
where each facility has a probability of 0<q<1of being busy or failing,
independently of any circumstance of the system. Therefore, a demand point
covered by ` facilities has a probability 1 q ` of receiving service. In this model,
demands t j associated to the demand points are also known, and the goal is to
locate at most p facilities in such a way that the total expected demand (the
sum of the demands of the points times their probability of being serviced) is
maximized. Apart from PPAC, this is the first model considered here where
all the w -variables really make sense, since it is necessary to know how many
facilities are covering each demand point in a given feasible solution. When