Information Technology Reference
In-Depth Information
rare events. The interdiction approach can be viewed as a “worst-case” approach,
and sensitivity analysis can be performed on the parameter D which denotes the
number of facilities destroyed by the disaster in the second level.
4 Solution Methodology
As far as we know, there is no solution methodology developed for tri-level pro-
gramming. In this section, we present an integrated formulation for the tri-level
model. In the next section, we present a dual-ascent iterative solution approach.
An ecient solution approach is important, since the coverage of the planning
area could be quite extensive. According to a report by the World Bank, at the
peak of the relief effort after the Tohoku earthquake and tsunami, over 470,000
people were housed in 2,500 evacuation facilities (World Bank, 2012).
4.1 Level 3 as a Location-Allocation Problem
The decision variables u i for ( L3 ) represent location decisions. We note that once
these locations are selected, the remaining decisions can be optimised by solving
a network-flow problem. For fixed values of ( x, y, z ), δ and u ,( L3 ) is equivalent
to a min-cost network flow problem, where the supply nodes correspond to i
with u i + y i
δ i = 1 and a special node n represents the source of supply for
new inventory. The demand nodes correspond to J , each with demand p j .The
solution to this min-cost network flow problem gives the minimum recovery cost
given the initial preparedness decisions, the damage incurred in Level 2, and the
“location” decisions u i . The flows determine the allocation of the population in
the communities to the operational evacuation centres and the corresponding
delivery of supplies. Thus, ( L3 ) is a location-allocation problem, which is still
NP-hard. To facilitate subsequent discussion, we denote the optimal value to
( L3 ) for given x, y, z and δ as R ( x, y, z ; δ ).
4.2 Re-formulation of Level 2
For fixed x, y, z and δ , the optimal recovery cost for Level 3 can be determined
by solving a location-allocation problem as described in the previous subsection.
Next, we consider a re-formulation of Level 2 in a column-generation format. Let
{
δ 1 2 ,
···
Q }
be the extreme points of
B I :
i∈I
F∈
( x, y, z )= conv
{
δ
δ i
D ; δ i
y i ,
i
I
}
.
Then Level 2 can be re-formulated as:
Q
( L2a ):
max
λ
λ q R ( x, y, z ; δ q )
q =1
Q
subject to
λ q
=1 ,
(20)
q =1
λ q
0 ,
for q =1 , 2 ,
···
,Q.
(21)
Search WWH ::




Custom Search