Geoscience Reference
In-Depth Information
Chapter 12
Hub Location Problems
Ivan Contreras
Abstract
Hub Location Problems
(HLPs) lie at the heart of network design
planning in transportation and telecommunication systems. They are a challenging
class of optimization problems that focus on the location of hub facilities and on
the design of hub networks. This chapter overviews the key distinguishing features,
assumptions and properties commonly considered in HLPs. We highlight the role
location and network design decisions play in the formulation and solution of HLPs.
We also provide a concise overview of the main developments and most recent
trends in hub location research. We cover various topics such as hub network topolo-
gies, flow dependent discounted costs, capacitated models, uncertainty, dynamic and
multi-modal models, and competition and collaboration. We also include a summary
of the most successful integer programming formulations and efficient algorithms
that have been recently developed for the solution of HLPs.
Keywords
Hub location Hub networks Integer programming
12.1
Introduction
Transportation, telecommunications and computer networks frequently employ
hub-and-spoke architectures to efficiently route flows between many origins and
destinations. Their key feature lies in the use of transshipment, consolidation, or
sorting points, called
hub facilities
, to connect a large number of origin/destination
(O/D) pairs by using a small number of links. Flows having the same origin but
different destinations are consolidated when routed to the hubs and then, combined
with other flows having different origins but the same destination. This helps reduce
setup costs, centralize commodity handling and sorting operations, and achieve
economies of scale on routing costs through the consolidation of flows. Broadly
speaking,
Hub Location Problems
(HLPs) consist of locating hub facilities and of
designing hub networks so as to optimize a cost-based (or service-based) objective.
