Information Technology Reference
In-Depth Information
maximum additional recovery cost, until
D
centres are destroyed. The DROP
part of the heuristic starts with all centres destroyed, and greedily “releases”
centres from damage to minimize the reduction in recovery cost. We track the
recovery cost of the
δ
values considered in the course of the heuristic, and also
select the
δ
value with the maximum
R
(
x, y, z
;
δ
). Cuts corresponding to all three
δ
values will be added in the dual ascent algorithm.
Each iteration of the heuristic entails solving up to
I
network flow problems,
so could still be quite computationally expensive. We can consider experimenting
with other selection heuristics for
δ
for cut generation. One possibility to consider
is some way of approximating the Shapley value for each location
i
, by keeping
track of the solution values of (
L3a
)eachtimeitissolved.
|
|
6 Computational Results
This section reports on computational experiments on the eciency of the so-
lution approach proposed. By examining the results, we can also draw some
insights on disaster relief planning. As indicated in Section 5, our experiments
consider only the cases when no (re-)establishment of evacuation centres is pos-
sible after the disaster (i.e.
u
i
=0
I
). The computations were done on an
Intel(R) Core(TM)2 Quad CPU Q9400 2.66 GHz personal computer with 2.87
GB of RAM. We used CPLEX 12.1 as our mixed-integer solver (branch-and-cut),
with the optimality tolerance set as 0.5%.
∀
i
∈
6.1 Data Sets and Parameters
We generate our data sets in a similar fashion as Huang et al. (2012). The
locations of evacuation centres and communities are generated randomly with
a uniform distribution on a 1000
1000 square. The distance between two
locations,
d
ij
, is defined as the Euclidean distance. Some model parameters are
generated randomly according to the discrete uniform distributions listed in
Table 1. Other parameters are set as follows:
m
= 300,
E
= 20,
f
i
=10
C
i
and
T
ik
=
d
ik
. We consider seven different problem sizes: (i)
×
|
I
|
=30
,
|
J
|
= 50;
(ii)
|
I
|
=30
,
|
J
|
= 100; (iii)
|
I
|
=40
,
|
J
|
= 80; (iv)
|
I
|
=40
,
|
J
|
= 100; (v)
|
= 100, and
for each problem size, we consider three values for the maximum number of
evacuation centres destroyed by the disaster (i.e.
D
=3
,
6and9).Thus,there
are 21 instances in total.
I
|
=50
,
|
J
|
= 100; (vi)
|
I
|
=50
,
|
J
|
= 150; and (vii)
|
I
|
=60
,
|
J
|
Tabl e 1.
The probability distributions of the randomly generated parameters
Parameter
C
i
h
i
H
i
p
j
Probability distribution U(1,500) U(1,10) U(1,50) U(1,100)
