Geoscience Reference
In-Depth Information
where
ij
are continuous decision variables used to evaluate the flow cost of O/D
pair .i;j/. This new formulation has O.n
2
/ variables and O.n
4
/ constraints. It is
interesting to note that, for the particular case of the p-hub median problem, the
above supermodular formulation coincides with the
radius-based formulation
of
García et al. (
2012
).
As in the case of single assignments, we can also use flow-based formulations
to model the UHLPMA. However, we now need additional flow variables for the
collection and distribution legs. We define continuous variables X
ijm
, i;j;m
2
N,
equal to the amount of flow from hub m to destination j that originates at node i.
We also define continuous variables Z
ik
, i;k
2
N equal to the amount of flow from
origin node i to hub k. Using these sets of decision variables, we can formulate the
UHLPMA as follows (Ernst and Krishnamoorthy
1998b
):
minimize
X
k2N
f
k
Z
k
C
X
i;k2N
d
ik
Z
ik
C
X
i;k;m2N
Ǜd
km
Y
ikm
C
X
ijm
ıd
jm
X
ijm
subject to
(
12.17
)-(
12.13
)
X
Z
ik
D
O
i
i
2
N
(12.22)
k2N
X
X
ijm
D
W
ij
i;j
2
N
(12.23)
m
Z
ik
C
X
m2N
Y
ikm
D
X
m2N
Y
imk
C
X
j
X
ijm
i;k
2
N
(12.24)
Z
ik
;X
ijm
0
i;j;m
2
N:
(12.25)
Constraints (
12.22
) ensure that all flow from each origin is sent to a subset of
hubs. Constraints (
12.23
) forces the flow of each O/D pair to arrive at its destination.
Constraints (
12.24
) are the flow conservation constraints at hub facilities. The above
formulation contains O.n
3
/ variables and O.n
2
/ constraints. Boland et al. (
2004
)
presents some preprocessing procedures that can be used to reduce the number of
variables and constraints, and some valid inequalities to improve the LP bounds of
capacitated variants.
12.4
Main Developments and Recent Trends
Early hub location research focused mostly on a first generation of HLPs which
consider the assumptions introduced in Sect.
12.2.1
. In this section we present
some research areas that have attracted most attention in the literature over the last
decade, leading to more realistic models that relax some of these assumptions and
incorporate additional features of real applications. We focus on six particular areas:
hub network topologies, flow dependent discounted costs, capacitated models,
