Geoscience Reference
In-Depth Information
the flow originated at i and destination j transits via a first hub node k and a second
hub node m. The UHLPSA can be stated as follows (Skorin-Kapov et al. 1997 ):
minimize X
k2N
f k z kk C X
i;j;k;m2N
F ijkm x ijkm
subject to
( 12.4 )-( 12.6 )
X
x ijkm D z ik
i;j;k 2 N
(12.7)
m2N
X
x ijkm D z jm
i;j;m 2 N
(12.8)
k2N
x ijkm 0
i;j;k;m 2 N:
(12.9)
Constraints ( 12.7 ) state that if node i is assigned to hub k then all the flow from
node i to any other node j must go through some other hub m. Constraints ( 12.8 )
have a similar interpretation relative to the flow arriving to a node j assigned to hub
m from some node i. There is no need to explicitly state the integrality on the x ijkm
variables because there always exists an optimal solution of ( 12.4 )-( 12.8 )inwhich
all x ijkm variables are integer. One of the attractive features of this formulation is that
it usually provides tight Linear Programming (LP) relaxation bounds, at the expense
of requiring O.n 4 / variables and O.n 3 / constraints. Saito et al. ( 2009 ) study the
polyhedral structure of the quadratic semi-assignment polytope, a relaxation of this
formulation, and provides strong valid inequalities to further improve its LP bound.
It is possible to project out the path-based variables x ijkm to obtain a formulation
with fewer variables (see Labbé and Yaman 2004 ; Labbé et al. 2005 ). We define
continuous variables y km , k;m 2 N, equal to the amount of flow routed on hub arc
.k;m/. The UHLPSA can be formulated as:
minimize X
k2N
f k Z k C X
i;k2N
.O i C ıD i /d ik z ik C X
k;m2N
Ǜd km y km
subject to
( 12.4 )-( 12.6 )
y km X
.i;j/2K
W ij z ik C z jm 1
k;m 2 N;K N N (12.10)
y km 0
;m 2 N:
(12.11)
For each arc .k;m/, constraints ( 12.10 )and( 12.11 )imply
X
W ij z ik C z jm 1 D X
.i;j/2K km
W ij z ik C z jm 1 ;
y km D max
KNN
.i;j/2K
where K km is the set of all demands which are routed on hub arc .k;m/.This
formulation contains only O.n 2 / variables but an exponential number of constraints.
Labbé and Yaman ( 2004 ) show that constraints ( 12.10 ) are a particular case of
Search WWH ::




Custom Search