Geoscience Reference
In-Depth Information
assumptions presented in Sect.
12.2.1
. We next introduce the most important
families of MIP formulations for both single and multiple assignment variants
of p-hub median and hub location problems. These have been successfully used
in combination with sophisticated solution algorithms to obtain optimal solutions
for large-scale instances. They have also been extended to model more complex
variants of HLPs including additional features of real applications. We refer to
Campbell et al. (
2007
), Alumur and Kara (
2009
), Wagner (
2008a
), Ernst et al.
(
2009
), Yaman and Elloumi (
2012
), Hwang and Lee (
2013
), and Lowe and Sim
(
2013
) for formulations of p-hub center and hub covering problems.
12.3.1
Single Assignments
A
natural
way to formulate HLPs with single assignments is to consider them
as facility location problems with additional quadratic costs associated with the
interaction of hub facilities. For each pair i;k
2
N, we define location/allocation
variables
z
ik
, equal to one if node i is assigned to hub k and zero otherwise. When
i
D
k,variable
z
kk
represents the establishment or not of a hub at node k.The
Uncapacitated Hub Location Problem with Single Assignments
(UHLPSA) can be
stated as the following quadratic mixed integer program (O'Kelly
1987
):
minimize
X
k2N
f
k
z
kk
C
X
i;k2N
.O
i
C
ıD
i
/d
ik
z
ik
C
X
i;j;k;m2N
ǛW
ij
d
km
z
ik
z
jm
(12.3)
subject to
X
k2N
z
ik
D
1i
2
N
(12.4)
z
ik
z
kk
i;k
2
N
(12.5)
z
ik
2f
0;1
g
i;k
2
N; (12.6)
where O
i
D
P
j2N
W
ij
and O
i
D
P
j2N
W
ji
. The first term of the objective
function represents the total set-up cost of the hub facilities, whereas the second
and third term are the flow cost on the access and hub arcs, respectively. Con-
straints (
12.4
) guarantee that every O/D node is assigned to exactly one hub, whereas
constraints (
12.5
) impose that they can only be assigned to open hubs. Note that
constraints (
12.4
)-(
12.6
) define the set of feasible solutions of the
Uncapacitated
Facility Location Problem
(see Chap.
3
). However, objective (
12.3
) contains an
additional quadratic term associated with the inter-hub flow cost. Several linearized
formulations have been proposed to overcome this added difficulty of UHLPSAs.
An important family of formulations, referred to as
path-based formulations
,use
decision variables to characterize O/D paths visiting either one or two hub nodes.
We introduce binary routing variables x
ijkm
, i;j;k;m
2
N, equal to 1 if and only if
