Geoscience Reference
In-Depth Information
500 nodes within reasonable CPU times. Meyer et al. (
2009
) present an ant colony
optimization algorithm for the p
-hub center problem with single assignments
which
is able to obtain high quality solutions for large-scale instances with up to 400 nodes.
Some researchers have recently focused on the development of efficient heuristic
algorithms for more realistic extensions of HLPs. Calık et al. (
2009
) describe a tabu
search to solve hub covering problems over incomplete hub networks. Köksalan and
Soylu (
2010
) study evolutionary algorithms for two bicriteria uncapacitated p-hub
location problems considering congestion-related costs. Contreras et al. (
2013
)
describe a GRASP algorithm for the design of incomplete hub networks with a
cycle-star topology. Saboury et al. (
2013
) present two hybrid heuristics to design
of hub networks with fully interconnected backbone and access networks. Martins
de Sá et al. (
2014
) propose an adaptive large neighborhood search and GRASP
algorithms to design hub networks with multiple hub lines.
12.5.3
Lower Bounding Procedures and Exact Algorithms
Dual ascent and dual adjustments techniques have been used to efficiently obtain the
LP bound of MIP formulations for various HLPs. Yoon and Current (
2008
) use dual
based heuristics to solve HLPs with additional arc selection decisions. Cánovas et al.
(
2007
)presenta
Branch-and-Bound
(BB) algorithm based on dual techniques to
obtain optimal solutions to uncapacitated HLPs with multiple assignments. Meyer
et al. (
2009
) develop a two-phase exact algorithm for the p-hub center problem
with single assignments. In this algorithm the BB method presented in Ernst and
Krishnamoorthy (
1998a
) is used during the first phase to obtain a set of potential
optimal hub locations. This algorithm seems to be the best exact algorithm for hub
center problems, being able to solve to optimality large-scale instances with up to
400 nodes.
Lagrangean relaxation (LR) has been successfully used to obtain tight lower
and upper bounds on the value of the optimal solution of several classes of HLPs.
Pirkul and Schilling (
1998
) present efficient LR heuristics to approximately solve
uncapacitated HLPs with single assignments, whereas Yaman (
2008
), Contreras
et al. (
2009a
,
b
), and Elhedhli and Wu (
2010
) propose LR heuristics to solve various
capacitated HLPs. Exact BB methods based on LR have also been developed to
optimally solve HLPs. Marín (
2005a
) propose a relax-and-cut algorithm for the
UHLPMA, which adds violated facet-defining inequalities to a LR of the path-
based formulation presented in Sect.
12.3.2
, to optimally solve instances with up
to 50 nodes. Contreras et al. (
2011c
) present an exact BB method, that uses a LR
of an extension of the path-based formulation presented in Sect.
12.3.2
, to obtain
optimal solutions for uncapacitated dynamic hub location problems with up to 100
nodes and ten time periods.
Benders decomposition (BD) is another successful method used to optimally
solve several classes of HLPs. Camargo et al. (
2009
) use a BD algorithm to solve
large-scale instances of the challenging flow-dependent cost (FLOWLOC) model.
