Geoscience Reference
In-Depth Information
compare the solutions obtained using the minmax regret and the expected regret
criteria.
When probabilities can be associated with the scenarios, an alternative robustness
measure proposed by Snyder and Daskin (
2006
)is“Ǜ-robustness”. The idea is to
look for a solution minimizing the expected cost/distance but such that the relative
regret in each scenario is less or equal than Ǜ. In the case of the p-median problem,
assuming
ex ante
location decisions and
ex post
allocation of customers to the
operating facilities, we obtain the following model:
Minimize
X
!2ǝ
X
X
!
d
j!
a
ij
!
x
ij
!
(8.24)
i2J
j2J
subject to
(
8.8
)-(
8.12
)
X
X
d
j!
a
ij
!
x
ij
!
.1
C
Ǜ/v
!
; !
2
ǝ:
(8.25)
i2J
j2J
As pointed out by Snyder and Daskin (
2006
), this model generalizes the well-
known models proposed by Weaver and Church (
1983
) and Mirchandani et al.
(
1985
). Snyder and Daskin (
2006
) also apply these ideas to the UFLP. They analyze
the complexity of both problems (the Ǜ-robustness p-median problem and the Ǜ-
robustness UFLP) and develop Lagrangian relaxation based approaches in order to
compute lower and upper bounds for the problems. The final gaps are closed using
branch-and-bound procedures.
All the robustness measures discussed and illustrated above involve all scenarios.
When the number of scenarios is too high, the large-scale models obtained may
become intractable. In this case, restricting the scenario set may be unavoidable.
This was done by Daskin et al. (
1997
) that introduced the Ǜ-reliable minmax regret
p-median problem. The authors seek to minimize the maximum regret over a subset
of scenarios. This subset is referred to as the reliability set. It is built from the
original set in such a way that the total probability associated with its scenarios is at
least some pre-specified value Ǜ. As pointed out by Baron et al. (
2011
), this idea has
a purpose similar to the use of ellipsoid uncertainty: the exclusion of low-probability
(typically extreme) scenarios. An extension of the above robustness measure was
introduced by Chen et al. (
2006
) who introduced the Ǜ-reliable mean-excess regret.
This measure weights the maximum regret over the reliability set and the conditional
expectation of the regret over the scenarios not included in the reliability set.
A different robustness concept was introduced by Carrizosa and Nickel (
2003
)
within the context of continuous facility location, although the concept can be
extended to network or discrete problems. In that paper, nominal values are assumed
to have been estimated for the (uncertain) weights of a set of nodes. A maximum
value is preset for the weighted distance between a single facility to be located and
the demand nodes. The robustness of a location is then defined as the minimum
deviation of the vector of weights with respect to the nominal vector that turns that
location an infeasible solution. The goal of the problem is to find the most robust
