Geoscience Reference
In-Depth Information
(Contreras et al.
2010
). In the case of cycle-star topologies, connecting the hub
nodes by means of a cycle is equivalent to the
minimum flow cost Hamiltonian cycle
problem
, known to be NP-hard (Contreras et al.
2013
).
In the case of uncapacitated HLPs with multiple assignments, in which the
full interconnection assumption is used, once the location of the hubs is known
the allocation subproblem is equivalent to an
all pairs shortest path problem
and
thus, can be solved in polynomial time (Ernst and Krishnamoorthy
1998a
). When
considering capacities on the hub nodes and commodities can be split, Contreras
et al. (
2012
) show that the allocation subproblem remains polynomially solvable as
it is equivalent to a classical
transportation problem
. However, when commodities
cannot be split the subproblem is equivalent to a
generalized assignment problem
and thus becomes NP-hard.
Contreras and Fernández (
2014
) show that a general class of HLPs with multiple
assignments, known as
supermodular hub location problems
(Sect.
12.2.2
), is NP-
hard. We recall that SHLPs include several special cases such as p-hub median,
uncapacitated hub location, and q-hub arc location. The authors also present worst-
case performance results for simple greedy and local improvement heuristics for
particular classes of SHLPs in which the objective functions are also non-increasing,
as in p-hub median and q-hub arc location problems.
Kara and Tansel (
2003
) show that
hub set-covering problems with single
assignments
are NP-hard. Kara and Tansel (
2000
) prove that the
uncapac-
itated
p
-hub center problem with single assignments
is also NP-hard for
p<n
1. Ernst et al. (
2009
) show that the multiple assignments version of
this problem is also NP-hard. They also prove that the single allocation subproblem
with respect to a given set of hubs is already NP-hard, whereas for the multiple
assignment case is not. Liang (
2013
) considers the
star
p
-hub center problem
and shows that is strongly NP-hard and that there is no .5=4
/-approximation
algorithm for it for any >0, unless P
D
NP. This paper also provides a 7=2-
approximation algorithm for this problem.
12.5.2
Heuristic Algorithms
A considerable amount of hub location research on heuristic algorithms has focused
on fundamental HLPs. To the best of our knowledge, the best heuristic for the
uncapacitated
p
-hub location problem with single assignments
is the variable
neighborhood search algorithm of Ili´cetal.(
2010
). It outperforms all previous
heuristics and it yields solutions for very large-scale instances with up to 1,000
nodes and p
D
20 within reasonable CPU times. The best results for the UHLPSA
seem to be obtained using the memetic algorithm recently designed by Mari´cetal.
(
2013
). This heuristic has the best performance, especially on large instances with
up to 900 nodes. Contreras et al. (
2011d
) provide GRASP heuristics for capacitated
versions of this problem. Contreras et al. (
2011b
) design a GRASP heuristic for
the UHLPMA capable of obtaining high quality solutions for instances with up to
