Geoscience Reference
In-Depth Information
12.6
Conclusions
In this chapter we have provided an overview of hub location problems in which
both the location of hubs and the design of the hub network are key decisions. We
have highlighted how the commonly used assumptions presented in Sect.
12.2.1
simplify network design decisions, which have created a first generation of
idealized
hub location models focusing mostly on location and allocation decisions. Several
researchers have exploited the rich structure of these models and as a consequence, a
significant progress has been made on the development of strong MIP formulations
and efficient algorithms for their solution.
Strong path-based formulations, used in combination with sophisticated decom-
position methods, have proven to be amongst the most effective formulations to
solve to optimality large-scale instances (with hundreds of nodes) for several classes
of hub location problems. Flow-based formulations, having fewer variables and
constraints, have been particularly useful when used with general purpose MIP
solvers to solve small to medium-size instances (containing usually no more than
50 nodes) for a wide range of problems without having to develop ad-hoc solution
algorithms. These formulations have also been strengthened with the addition of
valid inequalities and used within a cutting plane framework to solve challenging
hub location variants. Over the past few years, promising two-index formulations
have started to arise. However, a substantial amount of work still needs to be done
to analyze how these can be used as a basis for sophisticated algorithms.
We have also pointed out how location and network design decisions become
more involved when relaxing some of the
simplifying
assumptions presented in
Sect.
12.2.1
. In particular, Sect.
12.4.1
described several classes of hub network
topologies, arising from different areas of application, that have started to be
studied. The resulting hub location problems contain additional hub arc and access
arc selection decisions, making them substantially more difficult to model and
solve than first generation problems considering fully interconnection between
hubs and access networks characterized by single or multiple assignment patterns.
Section
12.4.2
focused on more realistic models with discounting levels that depend
on the amount of flow passing through each arc to better model the flow cost.
Although some flow-dependent models have already been presented in the literature,
alternative modeling approaches need to be studied to more accurately represent
flow costs, specially on transportation applications. Section
12.4.3
reviewed several
capacitated hub location models, most of which focus on capacity restrictions on the
hub nodes and only a few of them on the links. More complex problems combining
both types of capacities need to be studied. Section
12.4.4
described some models
in which specific sources of uncertainty were considered, mostly from a stochastic
programming perspective. However, additional aspects such as congestion on hubs
and arcs, reliability, and disruptions, among other things, need to be further studied.
Very few models considering dynamic and multi-modal features have been proposed
(Sect.
12.4.5
). Additional models need to be developed to better model the optimal
evolution of hub networks and the choice for mode of transportation. Given that
