Geoscience Reference
In-Depth Information
HLPs constitute a challenging class of NP-hard problems involving joint location
and network design decisions. Their main difficulty stems from the inherent
interrelation between two levels of the decision process. The first level considers
the selection of a set of nodes to locate hub facilities, whereas the second level
deals with the design of the hub network, by selecting the links to connect origins,
destinations and hubs, as well as the routing of flows through the network.
HLPs lie at the heart of network design planning in transportation and telecom-
munication systems. Application areas of HLPs in transportation are abundant.
These include express package delivery, air freight and passenger travel, postal
delivery, trucking, and rapid transit systems. Demand corresponds to commodities
(i.e. express packages, passengers, mail, goods) carried by vehicles (i.e. trucks,
trains, airplanes, vessels) moved on physical networks such as roads and railways or
through the air of water. Hub facilities correspond to sorting centers or transportation
terminals in which one or more transportation modes interact. Consolidation of
flows at hubs enable economies of scale on the transportation costs, not only on
the routing of flows between hubs, but also between O/D nodes and hubs.
Applications of HLPS in telecommunications arise in the design of various
distributed data networks, where demand corresponds to electronic data that are
routed over a variety of physical links (i.e. fiber optic links and co-axial cables)
or through the air (i.e. satellite channels and microwave links). Hub facilities are
hardware such as switches, concentrators, multiplexors, and routers. Economies of
scale in data transmission and network utilization, in combination with large set-up
costs for hub facilities and communication links, motivate the use of hub-and-spoke
architectures.
The study of HLPs began with the pioneering work of O'Kelly ( 1986a ), for
continuous models, and O'Kelly ( 1986b , 1987 ), for discrete models, and has since
evolved into a rich research area. Over the last three decades hub location has been
studied by researchers around the globe from different disciplines such as location
science, geography, regional science, network optimization, transportation, telecom-
munications, and computer science. There exist several reviews and surveys on
HLPs, each one of them focusing on different aspects of these problems. The early
reviews dealing with HLPs, by O'Kelly and Miller ( 1994 ) and Campbell ( 1994a ),
contain classification schemes for fundamental models and for the topological
structures applicable to hub networks. Klincewicz ( 1998 ) concentrate on the design
of hub networks in the context of telecommunication networks, and Bryan and
O'Kelly ( 1999 ) present a survey focused on air transportation networks. Campbell
et al. ( 2001 ) wrote a comprehensive survey of HLPs in which the location of hubs
is the key decision. Alumur and Kara ( 2008 ) provide a classification and review of
the growing literature on network hub location models before 2008. Campbell and
O'Kelly ( 2012 ) provide an insight into early motivations for analyzing HLPs and
highlight recent research directions. Zanjirani Farahani et al. ( 2013 ) review solution
methods and applications for several classes of HLPs.
This chapter focuses on the role location and network design decisions play in the
formulation and solution of HLPs. It overviews features and assumptions commonly
considered in discrete HLPs, providing insights on their modeling implications
Search WWH ::




Custom Search