Geoscience Reference
In-Depth Information
Contreras et al. (
2011b
) describe an exact algorithm for the UHLPMA which applies
an enhanced BD to the path-based formulation presented in Sect.
12.3.2
, to obtain
optimal solutions for large-scale instances with up to 500 nodes. Contreras et al.
(
2012
) provide an extension of the previous BD to solve multi-capacity HLPs with
multiple assignments, with splittable and non-splittable commodities, for instances
with up to 300 nodes. Contreras et al. (
2011a
) develops a Monte-Carlo simulation-
based algorithm that integrates a BD to solve uncapacitated HLPs having stochastic
flow costs. Camargo et al. (
2013
) describe a BD algorithm to solve hub location-
routing problems, in which additional routing decisions to serve O/D nodes are
considered. This algorithm can solve instances with up to 100 nodes. Several BD
algorithms have also been implemented for HLPs with congestion costs for both
multiple (Camargo et al.
2009
) and single (Camargo et al.
2011
; Camargo and
Miranda
2012
) assignments versions, HALPs with particular topological structures
such as tree-start networks (Martins de Sá et al.
2013
) and hub-line networks
(Martins de Sá et al.
2015
,
2014
), HLPs arising in public transportation networks
(Gelareh and Nickel
2011
), and liner shipping applications (Gelareh and Nickel
2011
; Gelareh and Pisinger
2011
).
Branch-and-cut (BC) methods have also been developed to optimally solve
various HLPs. Labbé et al. (
2005
) develop a BC algorithm based on the two-index
formulation presented in Sect.
12.3.1
for various classes of capacitated HLPs with
single assignments. This method is able to solve to optimality instances with up to
50 nodes. García et al. (
2012
) presents a BC algorithm for the uncapacitated p-hub
median problem with multiple assignments. This algorithm uses an extension of
the two-index formulation presented in Sect.
12.3.2
and is able to optimally solve
large-scale instances with up to 200 nodes with very large values of p. Contreras
and Fernández (
2014
) also introduce a BC algorithm based on the two-index
formulation for the general class of
supermodular hub location problems
presented
in Sect.
12.2.2
. This method is able to solve q-hub arc location problems with up
to 125 nodes. Contreras et al. (
2010
) and Contreras et al. (
2013
) use an adaptation
of the flow-based formulation introduced in Sect.
12.3.1
to develop BC algorithms
to solve HLPs with tree-star and cycle-star topologies, respectively. Contreras et al.
(
2013
) is able to solve to optimality instances with up to 100 nodes. Catanzaro
et al. (
2011
) study a incomplete hub network design problem with additional graph
partitioning and routing decisions. Rodríguez-Martín et al. (
2014
) introduce a BC
algorithm for a hub location-routing problem, which is able to solve instances with
up to 50 nodes.
Column generation (CG) is the method that has received the least attention in the
hub location literature. Thomadsen and Larsen (
2007
) presents a branch-and-price
method for solving a HLP with fully interconnected access networks. Contreras
et al. (
2011d
) presents and exact algorithm, that combines LR and CG methods as
a bounding procedure, to obtain optimal solutions of large-scale capacitated HLPs
with single assignments with up to 200 nodes.
