Geoscience Reference
In-Depth Information
subject to
(
8.16
)-(
8.18
)
2
4
X
j2J
3
5
Ǜ
i
; i
2
I
P
d
j
x
ij
q
i
y
i
(8.73)
x
ij
2f
0;1
g
; i
2
I; j
2
J:
(8.74)
In this model, Ǜ
i
is the minimum probability of having the demand assigned to
facility i
2
I not exceeding the capacity of the facility. Typically, high values are
assumed for Ǜ
i
(e.g., 0:90 or 0:95).
One important feature in a model like the one above, is the possibility of obtain-
ing a deterministic equivalent formulation with the probabilistic constraints being
replaced by deterministic ones. Unfortunately, this is not always a straightforward
task. One successful example for the problem above is due to Lin (
2009
). The author
considers independent demands following a Poisson or a Gaussian distribution. For
illustrative purposes, we detail the procedure in the former case.
If the demands d
j
are independent and follow a Poisson distribution P.
j
/,
j
2
J, then the total demand assigned to facility i
2
I, i.e.,
P
j2J
d
j
x
ij
follows
a Poisson distribution P.
i
/ with
i
D
P
j2J
j
x
ij
. Accordingly, (
8.73
) becomes
equivalent to
q
i
y
i
X
e
i
i
`Š
Ǜ
i
; i
2
I
(8.75)
`D0
which, in turn, has a deterministic equivalent of the form
X
j
x
ij
i
y
i
; i
2
I:
(8.76)
j2J
In this model,
i
D
Œ,where is a random variable following a Poisson
distribution with an expectation that is equal to the largest value assuring that
P
E
.
q
i
/
Ǜ
i
. As detailed by Lin (
2009
), the value
i
can be easily obtained by a
search method in which the mean of is changed until P.
q
i
/ is approximately
equal to Ǜ
i
(i
2
I). After replacing the probabilistic constraints (
8.73
)by(
8.76
)
the resulting problem becomes a single-source capacitated facility location problem
that can be tackled by any of the available methods for such problem. Lin (
2009
)
also explores the possibility of having independent demands following a Gaussian
distribution. In this case, the deterministic equivalent of the probabilistic constraints
yields a non-convex feasible region. The author proposes a relaxation for the
problem that is then embedded into a heuristic approach.
A well-known facility location problem with chance constraints is the covering-
location problem proposed by ReVelle and Hogan (
1989
). The authors assume that
a server may be busy when a customer requests to be served. Let us denote by
the probability that this occurs. In a discrete covering-location problem, we have
