Geoscience Reference
In-Depth Information
and consequences. We point out how these assumptions simplify network design
decisions, creating a first generation of HLPs that focuses mostly on the location and
allocation decisions. We also show how network decisions become more involved
when relaxing some of these assumptions.
We start with an introduction to the fundamentals of HLPs, including their
distinguishing features, assumptions, properties, as well as commonly used objec-
tives. A review of the most interesting and useful
Mixed Integer Programming
(MIP) formulations for fundamental HLPs considering cost-based objectives is
then presented. We also highlight some of the main developments and most recent
trends in hub location. We would like to clarify that, due to space limitations,
this is not intended to be a comprehensive survey of all diverse topics associated
with hub location research, but rather our personal view-point on some of the
most interesting research on this filed. In particular, we include hub network
topologies, flow dependent discounted cost models, capacitated models, models
dealing with uncertainty, dynamic and multi-modal models, and competition and
collaboration. A summary of successful integer programming methods that have
given rise to efficient approximate and exact solution algorithms for solving HLPs
is also presented.
This chapter does not cover continuous HLPs or models in which locational
decisions are not present. The reader is referred to O'Kelly (
1986a
), O'Kelly
and Miller (
1991
), Aykin (
1988
), Campbell (
1990
,
2013
), Saberi and Mahmassani
(
2013
), and references therein for continuous variants of HLPs, and to Klincewicz
(
1998
), Gendron et al. (
1999
), and Wieberneit (
2008
) for hub-and-spoke network
design models in which the set of hub facilities is given a priori. The reader is also
referred to Contreras and Fernández (
2012
) for a survey of other general network
design problems that also combine location and network design decisions.
12.2
Fundamentals
HLPs are closely related to classical
Facility Location Problems
(FLPs). As a result,
for several classical facility location problems such as p-median, uncapacitated
facility location, p-center, and covering problems, analogous HLPs have been
studied: p-hub median, uncapacitated hub location, p-hub center, and hub covering
problems. Due to their multiple applications, inside these classes of HLPs there
exist several variants that differ with respect to a number of assumptions like the
topological structure, the allocation pattern of O/D nodes to hubs, and capacity
constraints on the hub network, among others.
The key difference between FLPs and HLPs relies on the type of service demand
required by the users and on the function the facilities provide. In the case of
FLPs, service is given at (from) the facilities and flows thus originate at demand
nodes (facilities) and their destination are the facilities (demand nodes). Network
design and routing decisions are usually determined by the assignment pattern of
demand nodes to their allocated facilities. In HLPs, service demand is between
