Geoscience Reference
In-Depth Information
network. Asgari et al. (
2013
) study a game theoretic hub network design model that
investigates the competition and cooperation amongst two major hub ports and the
shipping companies, with the objective of minimizing the shipping companies' cost
and maximizing the hub ports' revenue.
12.5
Solving Hub Location Problems
The interrelation of location and network design decisions make HLPs particularly
difficult to solve. A considerable effort has thus been made over the past two
decades to develop algorithms capable of obtaining high quality solutions of various
classes of HLPs, particularly when considering more realistic, large-scale instances.
Some of these algorithms are able to provide an estimation of the quality of the
obtained solutions and some them are able to prove that the obtained solution is
optimal. In this section, we point out recent papers describing the most effective
solution algorithms for various classes of HLPs. The interested reader is referred to
Alumur and Kara (
2008
) and Zanjirani Farahani et al. (
2013
) for a detailed survey
of approximate and exact algorithms for HLPs.
12.5.1
Complexity Results
Most HLPs are known to be NP-hard. However, very little research has been done to
analyze the complexity and polynomial-time approximability of particular classes
of HLPs. In the case of fundamental HLPs with single assignments, in which the
full interconnection assumption is used, even if the location of the hub nodes is
given the remaining subproblem is still NP-hard. This problem is known as the
quadratic semi-assignment problem
or the
single allocation problem
(see Saito
et al.
2009
; Sohn and Park
2000
, and references therein). Sohn and Park (
1997
)
show that for the particular case of the
uncapacitated
p
-hub median problem with
single assignments
(UpHLPSA), when p
D
2 the problem can be polynomial solved
by reducing it to n.n
1/=2 independent minimum cut problems. Sohn and Park
(
2000
) prove that the single allocation problem becomes NP-hard as soon as the
number of hubs is three and thus, the UpHLPSA is NP-hard for p
3.Iwasa
et al. (
2009
) describe a deterministic 3-approximation algorithm and a randomized
2-approximation algorithm for the single allocation problem. Moreover, they pro-
vide a .5=4/-approximation algorithm for the particular case in which the number
of hubs is three.
When considering HLPs with incomplete hub networks, even if the location of
hubs and the assignment of O/D nodes to hubs is given, the subproblem associated
with the location of hub arcs remains challenging. For instance, when considering
tree-star topologies the design of a tree spanning the set of hub nodes is equivalent to
the so-called
optimum communication spanning tree problem
, known to be NP-hard
