Information Technology Reference
In-Depth Information
We note that the dual of (
L2a
)is:
(
D
−
L2a
):
min
π
such that
π ≥ R
(
x, y, z
;
δ
q
)
,
for
q
=1
,
2
, ···,Q.
(22)
4.3 An Integrated Formulation
With the optimal value of the Level 3 formulation defined as
R
(
x, y, z
;
δ
) asso-
ciated with a given (
x, y, z
)and
δ
, we can consider the Level 3 optimization as
implicit within the Level 2 optimization. Thus, our model can be considered as
a bi-level programming problem. By adopting a column-generation formulation
for Level 2, the corresponding bi-level programme can be further re-formulated
as an integrated model as follows:
x,y,z
;
δ,π
i∈I
(
M
):
min
(
f
i
y
i
+
h
i
z
i
)+
π
subject to (1) to (7) and
π
≥
R
(
x, y, z
;
δ
)
∀
δ
∈F∈
(
x, y, z
)
.
(23)
The formulations for Level 2 and 3 are implicitly included as the constraints (23).
We note, of course, that (23) contains many constraints (even if we consider only
the
δ
's corresponding to the extreme points of
F∈
(
x, y, z
)), and the righthand
sides are obtainable only by solving NP-hard location-allocation problems.
5 A Dual Ascent Solution Approach
In this section, we present a dual ascent solution approach for the integrated
model for the case when no (re-)establishment of centres is possible after the
disaster. This corresponds to the situation when the time-frame of the recovery
stage is quite short.
5.1 Evaluation of
R
(
x, y, z
;
δ
)
In this case, the Level 3 formulation (
L
3) can be simplified as:
r,s,t,w
i∈I
H
i
s
i
+
i∈I
(
L3a
):
min
T
ik
t
ik
k∈I
subject to (12), (14), (15), (16), (17) and (19).
We introduce a new set of variables
v
ij
=
p
j
r
ij
representing the number of
people of community
j
accommodated at centre
i
. As discussed in Subsection 4.1,
for fixed values of
y,δ
and
z
,(
L3a
) becomes a min-cost network flow problem for
the network
G
=(
J
)), where
I
1
=
I
2
=
I
and node
n
represents the source of supply for new inventory. The nodes in
I
1
{
I
1
∪
n
}∪
I
2
∪
J,
(
{
I
1
∪
n
}×
I
2
)
∪
(
I
2
×