Geoscience Reference
In-Depth Information
a more general class of facet defining inequalities which can be separated in
polynomial time.
Another important family of formulations, referred to as
flow-based formula-
tions
, use continuous variables to compute the amount of flow routed on a particular
arc originated at a given node. In the case of single assignments, we only need to
use one set of flow variables associated with the hub arcs. We thus define continuous
variables Y
ikm
, i;j;k
2
N, equal to the amount of flow originated at node i and
passing through hub arc .k;m/. The UHLPSA can be formulated as follows (Ernst
and Krishnamoorthy
1996
):
minimize
X
k2N
f
k
z
kk
C
X
i;k2N
.O
i
C
ıD
i
/d
ik
z
ik
C
X
i;k;m2N
Ǜd
km
Y
ikm
subject to
(
12.4
)-(
12.6
)
X
W
ij
z
jk
C
X
m2N
Y
ikm
D
X
m2N
Y
imk
C
O
i
z
ik
i;k
2
N (12.12)
j2N
Y
ikm
0
i;k;m
2
N:
(12.13)
Constraints (
12.12
) are the well-known flow conservation constraints for each
O/D node i at each (potential) hub node k, where the supply and demand at
each node is determined by the allocation pattern. The above formulation contains
O.n
3
/ variables and O.n
2
/ constraints and thus, fewer variables and constraints
as compared with the path-base formulation. However, it usually produces weaker
LP bounds. Contreras et al. (
2010
,
2013
) present some families of extended cut-set
inequalities that can help improve the LP bounds.
12.3.2
Multiple Assignments
Given that in HLPs with multiple assignments O/D nodes can be connected to more
than one hub facility, we can exploit the properties on the structure of O/D paths
to obtain path-based formulations with less variables than the ones required for
single assignment models. In particular, it is known that every flow uses at most
one direction of a hub arc, the one with lower flow cost (Hamacher et al.
2004
). We
thus define an
undirected
flow cost F
ije
for each e
D
.k;m/
2
E and i;j
2
N
as F
ije
D
min
f
F
ijkm
;F
ijmk
g
. We also define binary location variables Z
i
, i
2
N,
equal to 1 if and only if a hub is located at node i.The
Uncapacitated Hub Location
Problem with Multiple Assignments
(UHLPMA) can be stated as follows (Hamacher
et al.
2004
;Marín
2005a
):
minimize
X
k2N
f
k
Z
k
C
X
i;j2N
X
F
ije
x
ije
e2E
subject to
X
e2E
x
ije
D
1i;j
2
N
(12.14)
