Geoscience Reference
In-Depth Information
variable
w
jk
takes value one, this can be then be re-interpreted as
demand point
j
is covered at least
k
times
. Thus, in order to obtain the right total in the objective
function (
5.1
), we define g
jk
D
t
j
.1
q/q
k1
8
j
2
J;
8
k
2
K.Thisway,
we have that
P
kD1
g
jk
D
t
j
.1
q
`
/ which is the correct contribution of j
to objective function when j is covered by ` facilities and
w
jk
w
j;kC1
8
k.
But this last inequality is satisfied implicitly because q
k
q
kC1
means that
coefficients
f
g
jk
g
k
are sorted in increasing order for every demand point j.
Finally, we define f
i
D
0
8
i
2
I and b
j
D
0
8
j
2
J. It is also natural in this
problem to assume that a site can host more than one facility because it could
lead to better solutions which is why we define e
i
D
p
8
i
2
I.
Some of the strong assumptions of this model (e.g., servers are independent,
servers have the same failure probabilities) have been relaxed several times in
the literature. See, for example, Batta et al. (
1989
) and Galvão et al. (
2005
).
Probabilistic Location Set Covering Problem: In order to examine the relation-
ships between the number of facilities being located and their reliability, ReVelle
and Hogan (
1989a
) proposed a Probabilistic Location Set Covering Problem
(PLSCP) whose main (and almost unique) difference with the SCP is that
values b
j
can be greater than one and they are obtained in such a way that the
reliability of coverage of each point j
2
J is guaranteed to be at least equal to a
threshold value Ǜ. Particularly, b
j
is calculated as the minimum integer number
such that
F
j
b
j
b
j
1
Ǜ;
where F
j
is an average busy fraction associated with point j. Optionally, in this
model e
i
can take values greater than one since this can lead to better solutions.
Maximum Availability Location Problem: Suppose now that a profit
u
j
associ-
ated with each demand point j
2
J is obtained only if at least `
j
facilities
cover it. The total number of facilities is limited, a site can host more than
one facility and there is no facility opening cost. The Maximum Availability
Location Problem (MALP), first described in ReVelle and Hogan (
1989b
), is
a particular case of (COV) obtained by defining f
i
D
0
8
i
2
I, e
i
D
p
8
i
2
I,
b
j
D
0
8
j
2
J,andg
jk
D
0
8
j
2
J,
8
k
¤
`
j
, whereas g
j`
j
D
u
j
8
j
2
J.
Since now the g-values are not sorted in increasing order, constraints
w
jk
w
j;kC1
8
j
2
J;
8
k<h;must be included.
Covering Problem: The so-called Covering Problem (CP) in Kolen and Tamir
(
1990
) is that of minimizing the costs of opening some facilities plus the penalty
costs associated to uncovered demand points. It is obtained from (COV) by
defining p
D
m, e
i
D
1
8
i
2
I, b
j
D
0
8
j
2
J, g
jk
D
0
8
j
2
J,
8
k
2 and
g
j1
D
u
j
8
j
2
J where
u
j
is the penalty for not covering demand point j.
