Journal of Transport Geography 1994 2(1)31-40 The hub network design problem A review and synthesis Morton E.O'Kelly Department of Geography,The Ohio State University,Columbus,Ohio 43210,USA Harvey J.Miller Department of Geography,University of Utah,Salt Lake City,Utah 84112.USA Hubs,or central trans-shipment facilities,allow the construction of a network where large numbers of direct connections can be replaced with fewer,indirect connections.Hub-and- spoke configurations reduce and simplify network construction costs,centralize commodity handling and sorting,and allow carriers to take advantage of scale economies through consolidation of flows.Such networks have widespread application in transportation.This paper presents a structured review of research on the hub network design problem.Three critical design questions need to be considered:(a)are the nodes in the network assigned exclusively to a single hub?(b)are direct node-to-node linkages permitted to bypass the hub facilities?and,(c)are the hub facilities fully interconnected?The nature and difficulty of the hub network design problem depends on the analyst's judgement with respect to these questions.We review analytical research papers,and give brief empirical examples of eight different network design protocols. Keywords:hub and spoke,network design.location Flows of people,commodities,information and approaches to the problem,it is difficult to form any energy all require a complex network of interlinkages generalizations.Indeed,there exists a disconcerting between origins and destinations.A special kind of number of definitions and ideas about what con- network,namely,the hub network is designed for stitutes a hub.The following paragraphs discuss servicing human,commodity or information flows briefly the various concepts of hub which have been between multiple origins and destinations,ie,the used in the operations research literature,in air many-to-many distribution problem.Hubs,or central passenger transportation and in air package trans-shipment facilities,allow the construction of a delivery network where direct connections between all origin In the case of the early literature on management and destination pairs can be replaced with fewer, science and operations research,the concept of hub indirect connections.These configurations reduce seems to have been synonymous with a central and simplify network construction costs,centralize warehouse or facility.(See Minas and Mitten [1958] commodity handling and sorting,and allow carriers where a model for scheduling truck movements in to take advantage of scale economies through and out of a depot or hub is presented without any consolidation of flows (Chestler,1985;Devany and notion of sorting or throughput.)Thus,a hub is in Garges,1972;Kanafani and Ghobrial,1985;Toh essence a warehouse or a central depot,which is and Higgins,1985). located at the centre of a set of demand regions Hub-and-spoke networks are applicable to many Conversely,Goldman (1969)analysed what is different types of transport problem.Examples of actually a hub facility,but referred to it as a 'center'. hub-and-spoke systems include:airline passenger As noted by Campbell (1991a)Goldman located carriers (Shaw,1993);overnight package delivery centres to minimize the sum of transport costs over a services (Chestler,1985);and rail sorting yards set of origin-destination pairs,and so formulated a (Bodin et al,1980).While these diverse applications general multiple-hub assignment problem. are very well known,the prospects for a compre- In air passenger transportation,as defined by the hensive model for hub network optimization are US Federal Aviation Administration (FAA),the limited at the moment.There are so many different term 'hub'is not based on the hub-and-spoke 0966-6923/94/010031-10 1994 Butterworth-Heinemann Ltd
Journal of Transport Geography 19942(1) 31-40 The hub network design problem A review and synthesis Morton E. O'Kelly Department of Geography, The Ohio State University, Columbus, Ohio 43210, USA Harvey J. Miller Department of Geography, University of Utah, Salt Lake City, Utah 84112, USA Hubs, or central trans-shipment facilities, allow the construction of a network where large numbers of direct connections can be replaced with fewer, indirect connections. Hub-andspoke configurations reduce and simplify network construction costs, centralize commodity handling and sorting, and allow carriers to take advantage of scale economies through consolidation of flows. Such networks have widespread application in transportation. This paper presents a structured review of research on the hub network design problem. Three critical design questions need to be considered: (a) are the nodes in the network assigned exclusively to a single hub? (b) are direct node-to-node linkages permitted to bypass the hub facilities? and, (c) are the hub facilities fully interconnected? The nature and difficulty of the hub network design problem depends on the analyst's judgement with respect to these questions. We review analytical research papers, and give brief empirical examples of eight different network design protocols. Keywords: hub and spoke, network design, location Flows of people, commodities, information and energy all require a complex network of interlinkages between origins and destinations. A special kind of network, namely, the hub network is designed for servicing human, commodity or information flows between multiple origins and destinations, ie, the many-fo-many distribution problem. Hubs, or central trans-shipment facilities, allow the construction of a network where direct connections between all origin and destination pairs can be replaced with fewer, indirect connections. These configurations reduce and simplify network construction costs, centralize commodity handling and sorting, and allow carriers to take advantage of scale economies through consolidation of flows (Chestler, 1985; Devany and Garges, 1972; Kanafani and Ghobrial, 1985; Toh and Higgins, 1985). Hub-and-spoke networks are applicable to many different types of transport problem. Examples of hub-and-spoke systems include: airline passenger carriers (Shaw, 1993); overnight package delivery services (Chestler, 1985); and rail sorting yards (Bodin et ai, 1980). While these diverse applications are very well known, the prospects for a comprehensive model for hub network optimization are limited at the moment. There are so many different 0966-6923/94/010031-10 © 1994 Butterworth-Heinemann Ltd approaches to the problem, it is difficult to form any generalizations. Indeed, there exists a disconcerting number of definitions and ideas about what constitutes a hub. The following paragraphs discuss briefly the various concepts of hub which have been used in the operations research literature, in air passenger transportation and in air package delivery. In the case of the early literature on management science and operations research, the concept of hub seems to have been synonymous with a central warehouse or facility. (See Minas and Mitten [1958] where a model for scheduling truck movements in and out of a depot or hub is presented without any notion of sorting or throughput.) Thus, a hub is in essence a warehouse or a central depot, which is located at the centre of a set of demand regions. Conversely, Goldman (1969) analysed what is actually a hub facility, but referred to it as a 'center'. As noted by Campbell (1991a) Goldman located centres to minimize the sum of transport costs over a set of origin-destination pairs, and so formulated a general multiple-hub assignment problem. In air passenger transportation, as defined by the US Federal Aviation Administration (FAA), the term 'hub' is not based on the hub-and-spoke
The hub network design problem:M.E.O'Kelly und H.J.Miller switching operation which is the basis for the A set of convenient but restrictive modelling definitions in this paper.For the FAA the term hub assumptions can be exploited in order to manage the is taken to mean a geographical area,classified on hub network design problem.The standard hub the basis of the percentage of total passengers network topology,which we call Protocol A,consists enplaned in that area.For example,in the 1991 of a relatively large number of nodes each directly Airport activity statistics publication,the FAA connected to only one of a small number of defined a large hub in 1991 as an area which completely interconnected hubs,ie,the pure hub enplaned at least 4 283 192 passengers (ie at least and spoke'configuration.Protocol A serves as the 1%of total passengers).These large hubs accounted basis for many efforts to solve the hub network for 28 community areas,with 55 airports,and design problem (eg,Campbell,1991a,1991b; enplaned 73.16%of all passengers (see also Shaw, Klincewicz,.1991,1992;O'Kelly,1986,1987,1992a, 1993,p.48;and Dempsey and Goetz,1992) 1992b:O'Kelly and Miller,1991;Skorin-Kapov and In package delivery systems,such as United Skorin-Kapov,1992).Later in this paper,we discuss Parcel Service,the hub terminology is used to variants on the hub network design problem,and we denote almost all major sorting centres.The call them Protocol B,C,...,H. company,in 1992,had over 2250 operating facilities; Although the standard hub network topology is of these,over 200 are identified as hubs!Clearly, convenient from an analytical point of view,re- however,their major air hubs are the kind of centre searchers have had to relax some of its restrictions in we are concerned with here.There are four such order to remain relevant to real-world distribution facilities:a main hub (Louisville.KY),and three problems.In general,these extensions greatly com- regional air hubs (in Philadelphia PA,Dallas TX. plicate the design problem,requiring the use of and Ontario CA).In this paper,the term hub refers additional simplifying assumptions in order to be to this more specialized meaning;that is,it is used to tractable.As a result,approaches to the hub denote a major sorting or switching centre in a problem have become extremely non-standardized. many-to-many distribution system.Therefore,the Partly due to these disparate approaches even basic key idea is that the flow between a set of origin and definitional issues regarding the components of a destination cities passes through one or more hubs, hub network are unresolved in the literature,as en route to the final destination reflected in our discussion of varying hub definitions. The hub network design problem,as it is discussed Our goal in this paper is to organize the growing in this paper,is a complex mixture of locational literature on hub network design and provide a analysis and spatial interaction theory (O'Kelly, framework for standardizing the hub network design 1986).In its most general form,this problem problem.In this paper,we review the characteristics involves:(1)finding the optimal locations for the of the hub network design problem and develop a hub facilities;(2)assigning non-hub origins and series of design features that clearly specify the rules destinations to the hubs:(3)determining linkages for constructing a particular hub network type.This between the hubs;and,(4)routeing flows through framework can serve as a standard language for the network.Not only is the number of the decision comparing different hub network design applica- variables large,but the solutions to these individual tions. In addition,the protocols indicate the problems are highly interdependent.In practical complexity of different design problems and suggest terms,there are at least three approaches to handling a broad strategy for addressing these problems. the complexity.The first is to adopt a partial In the next section of this paper,we discuss approach,whereby some aspects of the decision properties of the standard hub network design variables are simplified for mathematical conveni- problem.In the third section,we identify common ence.An example of this strategy is the common departures from Protocol A restrictions in real- assumption that transportation costs are independent world hub networks and review attempts by of flow volume,despite the well-known importance researchers to accommodate these complexities.In of scale effects in reality (Campbell,1990a).The the fourth section,we develop a series of hub second is to find a decomposition of the problem network designs as a standard classification system into convenient subproblems as exemplified by the for this problem.This includes a formal statement of division of the network into backbone and feeder definitional issues that have been neglected in the subnets (see examples in Chan and Ponder.1979 literature,presentation of the classification system Chung et al,1992).Finally,the third approach is to and discussion of the system's implications for the recognize the inherent mathematical difficulty,and design problem.The fifth and final section provides to seek a local rather than a global optimum to the some concluding comments. problem.Thus several researchers have begun to develop sophisticated mathematical programming Hub network design under Protocol A heuristics for hub design (Abdinnour and Venkataramanan,1992;Klincewicz,1991,1992: The standard hub network Protocol A is defined as O'Kelly,1987;O'Kelly et al,1993;Skorin-Kapov the product of three simplifying restrictions:(1)all and Skorin-Kapov,1992). hubs are fully interconnected;(2)all nodes are 32 Journal of Transport Geography 1994 Volume 2 Numher I
The hub network design problem: M. E. O'Kelly and H..J. Miller switching operation which is the basis for the definitions in this paper. For the FAA the term hub is taken to mean a geographical area, classified on the basis of the percentage of total passengers enplaned in that area. For example, in the 1991 Airport activity statistics publication, the FAA defined a large hub in 1991 as an area which enplaned at least 4 283 192 passengers (ie at least 1% of total passengers). These large hubs accounted for 28 community areas, with 55 airports, and enplaned 73.16% of all passengers (see also Shaw, 1993, p. 48; and Dempsey and Goetz, 1992). In package delivery systems, such as United Parcel Service, the hub terminology is used to denote almost all major sorting centres. The company, in 1992, had over 2250 operating facilities; of these, over 200 are identified as hubs! Clearly, however, their major air hubs are the kind of centre we are concerned with here. There are four such facilities: a main hub (Louisville, KY), and three regional air hubs (in Philadelphia PA, Dallas TX, and Ontario CA). In this paper, the term hub refers to this more specialized meaning; that is, it is used to denote a major sorting or switching centre in a many-to-many distribution system. Therefore, the key idea is that the flow between a set of origin and destination cities passes through one or more hubs, en route to the final destination. The hub network design problem, as it is discussed in this paper, is a complex mixture of locational analysis and spatial interaction theory (O'Kelly, 1986). In its most general form, this problem involves: (1) finding the optimal locations for the hub facilities; (2) assigning non-hub origins and destinations to the hubs: (3) determining linkages between the hubs; and, (4) routeing flows through the network. Not only is the number of the decision variables large, but the solutions to these individual problems are highly interdependent. In practical terms, there are at least three approaches to handling the complexity. The first is to adopt a partial approach, whereby some aspects of the decision variables are simplified for mathematical convenience. An example of this strategy is the common assumption that transportation costs are independent of flow volume, despite the well-known importance of scale effects in reality (Campbell, 1990a). The second is to find a decomposition of the problem into convenient subproblems as exemplified by the division of the network into backbone and feeder subnets (see examples in Chan and Ponder, 1979; Chung et al, 1992). Finally, the third approach is to recognize the inherent mathematical difficulty, and to seek a local rather than a global optimum to the problem. Thus several researchers have begun to develop sophisticated mathematical programming heuristics for hub design (Abdinnour and Venkataramanan, 1992; Klincewicz, 1991, 1992; O'Kelly, 1987; O'Kelly et al, 1993; Skorin-Kapov and Skorin-Kapov, 1992). 32 A set of convenient but restnctlVe modelling assumptions can be exploited in order to manage the hub network design problem. The standard hub network topology, which we call Protocol A, consists of a relatively large number of nodes each directly connected to only one of a small number of completely interconnected hubs, ie, the pure 'hub and spoke' configuration. Protocol A serves as the basis for many efforts to solve the hub network design problem (eg, Campbell, 1991a, 1991b; Klincewicz, 1991, 1992; O'Kelly, 1986, 1987, 1992a, 1992b; O'Kelly and Miller, 1991; Skorin-Kapov and Skorin-Kapov, 1992). Later in this paper, we discuss variants on the hub network design problem, and we call them Protocol B, C, ..., H. Although the standard hub network topology is convenient from an analytical point of view, researchers have had to relax some of its restrictions in order to remain relevant to real-world distribution problems. In general, these extensions greatly complicate the design problem, requiring the use of additional simplifying assumptions in order to be tractable. As a result, approaches to the hub problem have become extremely non-standardized. Partly due to these disparate approaches even basic definitional issues regarding the components of a hub network are unresolved in the literature, as reflected in our discussion of varying hub definitions. Our goal in this paper is to organize the growing literature on hub network design and provide a framework for standardizing the hub network design problem. In this paper, we review the characteristics of the hub network design problem and develop a series of design features that clearly specify the rules for constructing a particular hub network type. This framework can serve as a standard language for comparing different hub network design applications. In addition, the protocols indicate the complexity of different design problems and suggest a broad strategy for addressing these problems. In the next section of this paper, we discuss properties of the standard hub network design problem. In the third section, we identify common departures from Protocol A restrictions in realworld hub networks and review attempts by researchers to accommodate these complexities. In the fourth section, we develop a series of hub network designs as a standard classification system for this problem. This includes a formal statement of definitional issues that have been neglected in the literature, presentation of the classification system and discussion of the system's implications for the design problem. The fifth and final section provides some concluding comments. Hub network design under Protocol A The standard hub network Protocol A is defined as the product of three simplifying restrictions: (1) all hubs are fully interconnected; (2) all nodes are Journal of Transport Geography /1)1)4 Volume 2 Numher /
The hub network design problem:M.E.O'Kelly and H.J.Miller connected to only one hub;and,(3)there are no problem with constraints similar to the p-median direct non-hub to non-hub(internodal)connections. problem (O'Kelly,1987).While this latter problem An example can be seen in Figure 1.The conceptual- is difficult to solve optimally (Aykin,1988;Aykin ization of the standard hub network is similar to and Brown,1992;O'Kelly,1986,1987),several Aykin (1993)who refers to a network like Protocol heuristic procedures have been developed.These A as a 'strict hubbing policy'. procedures differ mostly with regard to node-hub The Protocol A design has two important proper- assignment methods (see Campbell,1991a,1991b; ties.One property is deterministic routeing.Given Klincewicz.1991.1992:O'Kelly.1987:Skorin- fixed hub locations,allocations of non-hub origins Kapov and Skorin-Kapov,1992). and destination to hubs,and the triangle inequality It may also be noted from Table that several with respect to distance,there is only one shortest Protocol A design problems are either trivial,or path between any origin-destination pair in the unsolved to date.In the former category are single- network.Since each non-hub origin and destination facility problems in discrete space:under both is connected to only one hub and all hubs are minisum and minimax objectives,this problem can interconnected,the triangular distance inequality be solved through simple enumeration.More com- means that the shortest path can be found simply by plex,and still unsolved,is the multiple-hub,minimax choosing the direct connections between a non-hub problem in both planar and discrete space,although origin or destination and its hub and between the Campbell (1991a,1991b)has introduced a number hubs if necessary.A second property is a p-median of formulations which extend covering models to the problem constraint set:Protocol A network charac- hub network design problem teristics allow the hub network design problem to be stated in similar format to a traditional optimal Relaxing Protocol A restrictions location problem.The location literature has in turn been a fruitful source of algorithms for the hub The generic 'hub and spoke'topology serves as the location problem.These two properties allow the basis for the many-to-many distribution problem in a hub network design problem to be stated as variety of empirical transport and communication analogues to traditional location problems.Table I applications.However,the characteristics of these summarizes these linkages. real-world distribution problems have resulted in Under Protocol A,the minisum (ie minimize hub network configurations that typically violate one aggregate flow cost)single-hub problem in planar or more of the Protocol A restrictions. space can be stated as an easily solved Weber least- Figures 2 and 3 illustrate empirical hub network cost location problem (O'Kelly,1986).Also,the applications in air and ground transportation, minimax (ie minimize the most costly network flow) respectively.Figure 2 provides the route structure single-hub problem in planar space can be solved as (as of May 1991)for Skyway Airlines,a regional air a round-trip location problem for which efficient passenger carrier based in Milwaukee,Wisconsin. solution algorithms exist (O'Kelly and Miller,1991). Several of the network properties violate Protocol A The minisum,multihub problem in planar space can restrictions.Internodal connections are present (eg be treated as a multifacility location-allocation Madison-Rockford,Saginaw-Flint,Kalamazoo- problem (Aykin and Brown,1992).If distances are Lansing).Also evident is a feature known as a measured as squared Euclidean distances,con- 'spider leg'(Marsten and Mueller,1980)in which venient mathematical properties facilitate the service locations are arranged in purely linear solution of very large planar hub location models fashion (eg Peoria-Bloomington/Normal-Detroit). (O'Kelly,1992b).The objective function for the Figure 3 illustrates the US route structure for Yellow minisum,multihub problem in discrete space under Freight systems.Figure 3a provides the feeder Protocol A can be stated as a quadratic assignment (spoke)linkages to regional hubs,while Figure 3b indicates the interhub 'linehaul'linkages.Protocol A restrictions are violated at both network levels: several nodes are connected to more than one hub and the interhub network is not fully interconnected. Several researchers have examined design problems for hub networks with more complex NODE HUB LINK topologies than allowed hitherto.In some special ○HUB-HUBL.INK cases,modification of the Protocol A restrictions actually simplifies the design problem.For example, OHUB when multiple-hub assignment is allowed,the alloca- o NODE tion of nodes to hubs can be expressed under certain conditions as a linear assignment problem (Campbell,1991a,1991b).O'Kelly and Lao (1991) show that a model with allocations to both a mini- Figure I Example Protocol A network and a master-hub can be solved optimally using Journal of Transport Geography 1994 Volume 2 Number I 33
The hub network design problem: M.E. O'Kelly and H.i. Miller Figure 1 Example Protocol A network connected to only one hub; and, (3) there are no direct non-hub to non-hub (internodal) connections. An example can be seen in Figure I. The conceptualization of the standard hub network is similar to Aykin (1993) who refers to a network like Protocol A as a 'strict hubbing policy'. The Protocol A design has two important properties. One property is deterministic routeing. Given fixed hub locations, allocations of non-hub origins and destination to hubs, and the triangle inequality with respect to distance, there is only one shortest path between any origin-destination pair in the network. Since each non-hub origin and destination is connected to only one hub and all hubs are interconnected, the triangular distance inequality means that the shortest path can be found simply by choosing the direct connections between a non-hub origin or destination anc its hub and between the hubs if necessary. A second property is a p-median problem constraint set: Protocol A network characteristics allow the hub network design problem to be stated in similar format to a traditional optimal location problem. The location literature has in turn been a fruitful source of algorithms for the hub location problem. These two properties allow the hub network design problem to be stated as analogues to traditional location problems. Table I summarizes these linkages. Under ~rotocol A, the minisum (ie minimize aggregate flow cost) single-hub problem in planar space can be stated as an easily solved Weber leastcost location problem (O'Kelly, 1986). Also, the minimax (ie minimize the most costly network flow) single-hub problem in planar space can be solved as a round-trip location problem for which efficient solution algorithms exist (O'Kelly and Miller, 1991). The minisum, multihub problem in planar space can be treated as a multifacility location-allocation problem (Aykin and Brown, 1992). If distances are measured as squared Euclidean distances, convenient mathematical properties facilitate the solution of very large planar hub location models (O'Kelly, 1992b). The objective function for the minisum, multihub problem in discrete space under Protocol A can be stated as a quadratic assignment 5 6 4 2~ ~Q3 8 INODE - HUB LINK ~B-HUBLINK o HUB o NODE 7 problem with constraints similar to the p-median problem (O'Kelly, 1987). While this latter problem is difficult to solve optimally (Aykin, 1988; Aykin and Brown, 1992; O'Kelly, 1986, 1987), several heuristic procedures have been developed. These procedures differ mostly with regard to node-hub assignment methods (see Campbell, 1991a, 1991b; Klincewicz, 1991, 1992; O'Kelly, 1987; SkorinKapov and Skorin-Kapov, 1992). It may also be noted from Table I that several Protocol A design problems are either trivial, or unsolved to date. In the former category are singlefacility problems in discrete space: under both minisum and minimax objectives, this problem can be solved through simple enumeration. More complex, and still unsolved, is the multiple-hub, minimax problem in both planar and discrete space, although Campbell (199Ia, 1991b) has introduced a number of formulations which extend covering models to the hub network design problem. Relaxing Protocol A restrictions The generic 'hub and spoke' topology serves as the basis for the many-to-many distribution problem in a variety of empirical transport and communication applications. However, the characteristics of these real-world distribution problems have resulted in hub network configurations that typically violate one or more of the Protocol A restrictions. Figures 2 and 3 illustrate empirical hub network applications in air and ground transportation, respectively. Figure 2 provides the route structure (as of May 1991) for Skyway Airlines, a regional air passenger carrier based in Milwaukee, Wisconsin. Several of the network properties violate Protocol A restrictions. Internodal connections are present (eg Madison-Rockford, Saginaw-Flint, KalamazooLansing). Also evident is a feature known as a 'spider leg' (Marsten and Mueller, 1980) in which service locations are arranged in purely linear fashion (eg Peoria-Bioomington/Normal-Detroit). Figure 3 illustrates the US route structure for Yellow Freight systems. Figure 3a provides the feeder (spoke) linkages to regional hubs, while Figure 3b indicates the interhub 'linehaul' linkages. Protocol A restrictions are violated at both network levels: several nodes are connected to more than one hub and the interhub network is not fully interconnected. Several researchers have examined design problems for hub networks with more complex topologies than allowed hitherto. In some special cases, modification of the Protocol A restrictions actually simplifies the design problem. For example, when multiple-hub assignment is allowed, the allocation of nodes to hubs can be expressed under certain conditions as a linear assignment problem (Campbell, 1991a, 1991b). O'Kelly and Lao (1991) show that a model with allocations to both a miniand a master-hub can be solved optimally using Journal of Transport Geography 1994 Volume 2 Numher I 33
The hub network design problem:M.E.O'Kelly and H.J.Miller Table 1 Traditional location problem analogues under Protocol A restrictions Number of hubs Spatial constraint Design objective Problem characteristics Source Single Planar Minisum Weber least-cost location problem O'Kelly (1986) Single Planar Minimax Round-trip location problem O'Kelly and Miller (1991) Single Discrete Minisum Trivial;complete enumeration Single Discrete Minimax Trivial:complete enumeration Multiple Planar Minisum Location-allocation problem Aykin and Brown (1992):O'Kelly (1992b) Multiple Planar Minimax Unsolved Multiple Discrete Minisum Quadratic assignment problem with Avkin (1988): p-median constraints Klincewicz (1991): O'Kelly (1987). O'Kelly (1992a) Multiple Discrete Minimax Integer programming formulation Proposed in Campbell (i991b) Central Wisconsin ● Appleton Green Bay Rochester La Crosse Saginaw Buffalo Muskegon Milwaukee ●Grand Rapids Flint Madison 角Lansing Detroit Kalamazoo Rockford Des Moines Peoria ● Baltimore Bloomington /Normal Indianapolis Columbus Figure 2 Skyway Airlines Source:Columbus Dispatch (30 May 1991.p.A-2). linear programming.In general,however,relaxing metric (the latter metric limits travel to rectangular Protocol A restrictions greatly complicates the hub dimensions).Daganzo (1987)and Hall (1987)also network design problem.This added complexity has fix the locations and service areas of the hubs.This necessitated the use of additional restrictions in restriction is relaxed by Campbell (1990a,1990b). order to manage the design problem.Table 2 Partial interhub connections concentrate flows at provides some examples. particular hub facilities,which allows the exploitation One of the more common Protocol A relaxations of flow-processing economies of scale.Leung et al attempted is the assignment of nodes to more than (1990)allow partially interconnected hubs as well as one hub.Multiple-hub assignment can save trans- multiple hub assignment by separating the node-hub portation costs by tailoring the selection of hubs to assignment problem from the interhub routeing the eventual destinations of the flows being shipped problem.The routeing problem is solved by treating from an origin node thus reducing the distance it as a multicommodity flow problem,with each travelled.In addressing this routeing problem commodity distinguished by its origin-destination Daganzo (1987),and Hall (1987)are able to derive pair.Chou (1990)restricts topology to partially analytical solutions only by restricting the spatial interconnected hubs by requiring the network to be dimension of the problem to linear space or Li minimally connected,Since the network is a minimal 34 Journal of Trunsport Geography 1994 Volumne 2 Number I
The hub network design problem: M. E. O'Kelly and H.i. Miller Table 1 Traditional location problem analogues under Protocol A restrictions Number of hubs Spatial constraint Design objective Problem characteristics Source Single Planar Minisum Weber least-cost location problem O'Kelly (1986) Single Planar Minimax Round-trip location problem O'Kelly and Miller (1991) Single Discrete Minisum Trivial; complete enumeration Single Discrete Minimax Trivial; complete enumeration Multiple Planar Minisum Location-allocation problem Aykin and Brown (1992); O'Kelly (1992b) Multiple Planar Minimax Unsolved Multiple Discrete Minisum Quadratic assignment problem with Aykin (191\1\); p-median constraints Klinccwicz (1991); O'Kelly (191\7). O'Kelly (1992a) Multiple Discrete Minimax Integer programming formulation Proposed in Campbell (1991b) Central Wisconsin Peoria Green Bay Baltimore Indianapolis Figure 2 Skyway Airlines Source: Columbus Dispatch (30 May 1991, p. A-2). linear programming. In general, however, relaxing Protocol A restrictions greatly complicates the hub network design problem. This added complexity has necessitated the use of additional restrictions in order to manage the design problem. Table 2 provides some examples. One of the more common Protocol A relaxations attempted is the assignment of nodes to more than one hub. Multiple-hub assignment can save transportation costs by tailoring the selection of hubs to the eventual destinations of the flows being shipped from an origin node thus reducing the distance travelled. In addressing this routeing problem Daganzo (1987), and Hall (1987) are able to derive analytical solutions only by restricting the spatial dimension of the problem to linear space or L 1 34 metric (the latter metric limits travel to rectangular dimensions). Daganzo (1987) and Hall (1987) also fix the locations and service areas of the hubs. This restriction is relaxed by Campbell (1990a, 1990b). Partial interhub connections concentrate flows at particular hub facilities, which allows the exploitation of flow-processing economies of scale. Leung et al (1990) allow partially interconnected hubs as well as multiple hub assignment by separating the node-hub assignment problem from the interhub routeing problem. The routeing problem is solved by treating it as a multicommodity flow problem, with each commodity distinguished by its origin-destination pair. Chou (1990) restricts topology to partially interconnected hubs by requiring the network to be minimally connected. Since the network is a minimal Jot/mal of Transport Geography /994 Volt/me 2 Nt/mher I
The hub network design problem:M.E.O'Kelly and H.J.Miller b Figure 3 Yellow Freight:(a)hub and spoke,and (b)linchaul system spanning tree,routeing can be determined through Nevertheless,if a node is directly connected to a the connectivity matrix.Chou (1990)also relaxes large number of other nodes,there would seem to be this restriction somewhat by introducing a link- a strong case for developing full hub functionality at capacity constraint which can result in a more that location.In a slightly different vein,Flynn and connected topology. Ratick (1988)allow these linkages in the form of Internodal linkages can provide direct service stopover'air service in their air transport network between locations that have a high degree of model.However,the overall network is already interaction.The interesting aspect of this Protocol A established,and the design problem consists of relaxation is that,although the analyst may permit feeding additional service into the established hub certain routes to be served directly,the model network.One of the most general hub network determines whether or not such direct routes are design models was formulated by Powell and Sheffi economically viable (see for instance Aykin,1992). (1983).Their analysis includes both a statement of In practice,the use of direct node-to-node connec- the optimal design problem and a heuristic solution tions to 'bleed off'larger predictable flows from the procedure.The optimal version requires only one hubs is noted in air express.It should be emphasized directional link to enter and leave each node or hub that in terms of our definitions,these direct node-to- but this restriction is relaxed in the heuristic solution node pairs do not create a hub at the node,as the procedure.The solution procedure is a local im- usual hub trans-shipment functions are absent. provement strategy in which the user broadly directs Journal of Transport Geography 1994 Volume 2 NumberI 35
The hub network design problem: M. E. O'Kelly and H.i. Miller a b Figure 3 Yellow Freight: (a) hub and spoke, and (b) Iinehaul system spanning tree, routeing can be determined through the connectivity matrix. Chou (1990) also relaxes this restriction somewhat by introducing a linkcapacity constraint which can result in a more connected topology. Internodal linkages can provide direct service between locations that have a high degree of interaction. The interesting aspect of this Protocol A relaxation is that, although the analyst may permit certain routes to be served directly, the model determines whether or not such direct routes are economically viable (see for instance Aykin, 1992). In practice, the use of direct node-to-node connections to 'bleed off' larger predictable flows from the hubs is noted in air express. It should be emphasized that in terms of our definitions, these direct node-tonode pairs do not create a hub at the node, as the usual hub trans-shipment functions are absent. Journal of Transport Geography /994 Volume 2 Number / Nevertheless, if a node is directly connected to a large number of other nodes, there would seem to be a strong case for developing full hub functionality at that location. In a slightly different vein, Flynn and Ratick (1988) allow these linkages in the form of 'stopover' air service in their air transport network model. However, the overall network is already established, and the design problem consists of feeding additional service into the established hub network. One of the most general hub network design models was formulated by Powell and Sheffi (1983). Their analysis includes both a statement of the optimal design problem and a heuristic solution procedure. The optimal version requires only one directional link to enter and leave each node or hub, but this restriction is relaxed in the heuristic solution procedure. The solution procedure is a local improvement strategy in which the user broadly directs 35
The hub network design problem:M.E.O'Kelly and H.J.Miller Table 2 Examples of hub network modelling with Protocol A violations Source Protocol A violation allowed Additional restrictions Routeing mechanism Campbell (1990a) Assignment of nodes to multiple Lincar or Li spacc Analytical hubs Campbeil (1990b) Assignment of nodes to multiplc Linear space" Analytical hubs Chou (1990) Partial interconnection of hubs Network required to be minimally Connectivity matrix connected subject to possible link capacity constraint Daganzo (1987) Assignment of nodes to multiple Hub locations fixed Analytical hubs L space Hub service arcas fixed in size and shape Flynn and Ratick (1988)Internodal linkages Limited portion of network considered Multiobjective. hicrarchical weighted covering model Hal(1987) Assignment of nodes to multiple Hub locations fixed One-and two-hub hubs Limited number of hubs routeing heuristics Hubs not connected L space Hal(1989) Assignment of nodes to multiple Hub locations fixed Onc-and two-hub hubs Limited number of hubs routeing heuristics Hubs not connected Leung et al (1990) Assignment of nodes to multiple Hub locations fixed Multicommodity flow hubs Separates nodes assignment problem from problem Partial interconnection of hubs interhub routeing problem Powell and Sheffi (1983)Assignment of nodes to multiple Problem solved through user-directed local Not specified hubs improvement heuristic with prespecificd Hubs partially interconnected sequence of possible network changes Notes:"Euclidian space version uses Protocol A. the search for network changes.followed by inter- classification system.Finally,we discuss the implica- active modifications. tions of our system for the hub network design Table 2 illustrates the wide variety of restrictions problem. exploited in order to facilitate model solutions for Addressing the hub network design problem for a relatively complex configurations. Restrictions in- wide variety of possible configurations raises some clude:(i)limitations on the spatial dimension of the very basic definitional issues that have not been problem (eg Campbell.1990a,1990b;Daganzo, considered in the literature.However,these basic 1987;Hall,1987);(ii)fixing selected components of definitions are important in order to establish the the network or limiting their complexity (Chou, basic ground rules that characterize a hub network. 1990,1993;Daganzo,1987;Hall,1987:Leung et Without formal definitions of basic hub network al,1990);(iii)restricting the scope of the analysis components,the hub network design problem cannot (Flynn and Ratick,1988);and (iv)partitioning the be consistent across different applications. overall design problem into more manageable com- A hub network consists of three major components: ponents (Leung et al.1990;Powell and Sheffi service nodes,hubs and arcs.A 'service node'is a 1983).Thus,approaches to the hub network design point location from which flows can originate and problem beyond the Protocol A restrictions are into which only flows which are destined for that disparate.This creates difficulty in comparing (and location can enter.A 'hub'has the characteristics of even defining)the hub network design problem a service node (ie it can be a flow origin and across a wide range of applications. destination)but also allows the passage of through- flows or trans-shipment flows which are not destined A hub network classification system for that location.All throughflow that enters a hub must also exit that hub.Hubs are not differentiated In this section of the paper,we provide a common by class or hierarchy:we assume for now that a hub framework for the hub network design problem. can handle any amount of throughflow. This framework consists of formal definitions of hub The arcs that connect the service nodes and hubs network components and a classification system must have the following properties:(1)every service based on combinations of specific network design node must be connected to at least one hub;(2)a rules within the definitional parameters.We discuss valid path must exist between all hubs.These two the definitional issue first and then present the properties ensure that a feasible path will cxist 36 Journal of Transport Geography 1994 Volume 2 Number I
The hub network design problem: M. E. O'Kelly and H.J. Miller Table 2 Examples of hub network modelling with Protocol A violations Source Protocol A violation allowed Additional restrictions Routeing mechanism Analytical Analytical Not specified Multicommodity tlow problem One- and two-hub routeing heuristics Analytical Multiobjective. hierarchical weighted covering model One- and two-hub routeing heuristics Linear space" Hub locations fixed Separates nodes assignment problem from interhub routeing prohlem Problem solved through user-directed local improvement heuristic with prespeeified sequence of possible network changes Hub locations fixed Limited number of hubs L, space Hub locations fixed Limited number of hubs Network required to be minimally Connectivity matrix connected subject to possible link capacity constraint Hub locations fixed L, space Hub service areas fixed in size and shape Limited portion of network considered Assignment of nodes to multiple Linear or L, space hubs Assignment of nodes to multiple hubs Partial interconnection of hubs Internodal linkages Assignment of nodes to multiple hubs Hubs not connected Assignment of nodes to multiple hubs Hubs not connected Assignment of nodes to multiple hubs Partial interconnection of hubs Assignment of nodes to multiple hubs Hubs partially interconnected Assignment of nodes to multiple hubs Leung et al (llJlJO) Hall (llJ8lJ) Daganzo (llJ87) Hall (llJ87) Powell and Sheffi (llJ83) Flynn and Ratick (llJ88) Campbell (llJlJOa) Campbell (llJlJOb) Chou (llJlJO) Notes: "Euclidian space version uses Protocol A. the search for network changes, followed by interactive modifications. Table 2 illustrates the wide variety of restrictions exploited in order to facilitate model solutions for relatively complex configurations. Restrictions include: (i) limitations on the spatial dimension of the problem (eg Campbell, 1990a, 1990b; Daganzo, 1987; Hall, 1987); (ii) fixing selected components of the network or limiting their complexity (Chou, 1990, 1993; Daganzo, 1987; Hall, 1987; Leung et aI, 1990); (iii) restricting the scope of the analysis (Flynn and Ratick, 1988); and (iv) partitioning the overall design problem into more manageable components (Leung et aI, 1990; Powell and Sheffi, 1983). Thus, approaches to the hub network design problem beyond the Protocol A restrictions are disparate. This creates difficulty in comparing (and even defining) the hub network design problem across a wide range of applications. A hub network classification system In this section of the paper, we provide a common framework for the hub network design problem. This framework consists of formal definitions of hub network components and a classification system based on combinations of specific network design rules within the definitional parameters. We discuss the definitional issue first and then present the classification system. Finally, we discuss the implications of our system for the hub network design problem. Addressing the hub network design problem for a wide variety of possible configurations raises some very basic definitional issues that have not been considered in the literature. However, these basic definitions are important in order to establish the basic ground rules that characterize a hub network. Without formal definitions of basic hub network components, the hub network design problem cannot be consistent across different applications. A hub network consists ofthree major components: service nodes, hubs and arcs. A 'service node' is a point location from which flows can originate and into which only flows which are destined for that location can enter. A 'hub' has the characteristics of a service node (ie it can be a flow origin and destination) but also allows the passage of throughflows or trans-shipment flows which are not destined for that location. All throughflow that enters a hub must also exit that hub. Hubs are not differentiated by class or hierarchy: we assume for now that a hub can handle any amount of throughflow. The arcs that connect the service nodes and hubs must have the following properties: (1) every service node must be connected to at least one hub; (2) a valid path must exist between all hubs. These two properties ensure that a feasible path will exist 36 JOllY/wi of Trallsport Geograph\' 1'N4 Volume 2 NII/llh"r I
The hub network design problem:M.E.O'Kelly and H.J.Miller between all origins and destinations in the network. The three binary decision variables create 23=8 hub Also observe that a service node which is directly network classes,which are defined in Table 3 connected to all other service nodes does not Example networks can be seen in Figure 4. influence the hub network design problem.There- While it is difficult to find an exact match in the fore we disregard a service node as part of the hub real world to these prototypical networks,there are network if it essentially bypasses that network. several excellent representative examples.Protocol Note that property I does not allow the 'spider A is similar to the Rockwell International interplant leg'configuration unless the intermediate node (eg communications system illustrated in Fotheringham Bloomington/Normal in Figure 2)is defined as a and O'Kelly (1989,p.172).Protocol B can be seen hub,since that location receives throughflow.This in the satellite communications network design does not greatly reduce the generality of the hub proposed by Helme and Magnanti(1989).Note that network classification system since hubs can handle in their approach (see p.431,Figure 2),each node any amount of throughflow,even if this flow is from is connected to one of the available hubs,but these only one service node.In fact,intermediate nodes in hubs are not all connected directly to one another. a spider leg configuration do perform one of the Instead they have a link to a super hub (satellite). major services of a hub (ie the consolidation of Protocols C and D can be seen to a certain extent in flows),although other services (ie sorting)may not some financial networks which have single-hub be performed.Recently,Kuby and Gray (1993) assignment,but varying degrees of direct node-to- have developed an analysis of the hub network node connections and interhub connectivity design problem with stopovers and feeders.They (Weinstein,1982).Protocol E is seen in McShan and suggest that in the case of Federal Express,spider Windle (1989,p.213)where there are connected leg links to the hub at Memphis are common and hubs,but multiple-hub allocations.The Yellow require careful analysis. Freight system shown in Figure 3 is an excellent Since we are primarily concerned with the situation example of Protocol F.Many air passenger systems where hubs are selected from the existing set of illustrated in Shaw (1993)exemplify Protocols G origins and destinations (ie the discrete space and H problem,meaning that hubs are also flow origins A key feature of our classification system concerns and destinations),network configurations in which the complexity of the hub network design problem hubs have no interconnections (see,eg,Hall,1987. The basic design questions inherent in all protocols 1989)are not valid since this would make certain are the locations of hubs and the assignment of non- hubs (as flow destinations)inaccessible from hub nodes to hubs.Beyond this,each protocol portions of the network.From the perspective of our differs with regard to the freedom to configure arcs classification system,we would consider these in the network.For example,in Protocol A there are configurations as separate but intermeshed hub no 'free'arcs:hubs must be fully interconnected, networks. only one arc connects any node to any hub,and As noted earlier,the Protocol A network is the direct internodal connections are not allowed.in product of three assumptions:(i)all hubs are fully contrast,all arcs (existing and potential)in a interconnected;(ii)all non-hub nodes are connected Protocol H network are free for variable reconfigura- to only one hub;and (iii)there are no internodal tion within the constraints of that protocol.Table 4 (direct service node to service node)connections. indicates the decision variables that occur in each of Any or all of these rules can be relaxed as long as the the design problems. basic assumptions discussed in this section are not An important implication for hub network design violated.This provides three binary decision variables is that while the consideration of all possible with which to define hub network types.The three configurations for a hub network results in a very decisions are complex design problem.the use of the classification D1)Node assignment either one hub assign- system allows this complexity to be managed to a ment. or multihub assignment. Table 3 Hub network classification system (D2)Direct node-node either not allowed, allowed. Design variables (D3)Hub interconnection either full Internodal Interhub Design class Node-hub assignment or partial. connections connectivity Protocol A Single hub only Not allowed Full DI concerns whether a node can be assigned to only Protocol B Single hub only Not allowed Partial one hub or more than one hub and D2 refers to Protocol C Single hub only Allowed Full Protocol D whether direct internodal connections which bypass Single hub only Allowed Partial Protocol E Multiple hubs allowed Not allowed Full the hub structure can be allowed.D3 refers to the Protocol F Multiple hubs allowed Not allowed Partial subnetwork that connects the hubs alone;this can be Protocol G Multiple hubs allowed Allowed Full fully interconnected or only partially interconnected. Protocol H Multiple hubs allowed Allowed Partial Journal of Transport Geography 1994 Volume 2 Number I 37
The hub network design problem: M.E. O'Kelly and H.J. Miller The three binary decision variables create 23 = 8 hub network classes, which are defined in Table 3. Example networks can be seen in Figure 4. While it is difficult to find an exact match in the real world to these prototypical networks, there are several excellent representative examples. Protocol A is similar to the Rockwell International interplant communications system illustrated in Fotheringham and O'Kelly (1989, p. 172). Protocol B can be seen in the satellite communications network design proposed by Helme and Magnanti (1989). Note that in their approach (see p. 431, Figure 2), each node is connected to one of the available hubs, but these hubs are not all connected directly to one another. Instead they have a link to a super hub (satellite). Protocols C and 0 can be seen to a certain extent in some financial networks which have single-hub assignment, but varying degrees of direct node-tonode connections and interhub connectivity (Weinstein, 1982). Protocol E is seen in McShan and Windle (1989, p. 213) where there are connected hubs, but multiple-hub allocations. The Yellow Freight system shown in Figure 3 is an excellent example of Protocol F. Many air passenger systems illustrated in Shaw (1993) exemplify Protocols G and H. A key feature of our classification system concerns the complexity of the hub network design problem. The basic design questions inherent in all protocols are the locations of hubs and the assignment of nonhub nodes to hubs. Beyond this, each protocol differs with regard to the freedom to configure arcs in the network. For example, in Protocol A there are no 'free' arcs: hubs must be fully interconnected, only one arc connects any node to any hub, and direct internodal connections are not allowed. in contrast, all arcs (existing and potential) in a Protocol H network are free for variable reconfiguration within the constraints of that protocol. Table 4 indicates the decision variables that occur in each of the design problems. An important implication for hub network design is that while the consideration of all possible configurations for a hub network results in a very complex design problem, the use of the classification system allows this complexity to be managed to a between all origins and destinations in the network. Also observe that a service node which is directly connected to all other service nodes does not influence the hub network design problem. Therefore we disregard a service node as part of the hub network if it essentially bypasses that network. Note that property 1 does not allow the 'spider leg' configuration unless the intermediate node (eg Bloomington/Normal in Figure 2) is defined as a hub, since that location receives throughflow. This does not greatly reduce the generality of the hub network classification system since hubs can handle any amount of throughflow, even if this flow is from only one service node. In fact, intermediate nodes in a spider leg configuration do perform one of the major services of a hub (ie the consolidation of flows), although other services (ie sorting) may not be performed. Recently, Kuby and Gray (1993) have developed an analysis of the hub network design problem with stopovers and feeders. They suggest that in the case of Federal Express, spider leg links to the hub at Memphis are common and require careful analysis. Since we are primarily concerned with the situation where hubs are selected from the existing set of origins and destinations (ie the discrete space problem, meaning that hubs are also flow origins and destinations), network configurations in which hubs have no interconnections (see, eg, Hall, 1987, 1989) are not valid since this would make certain hubs (as flow destinations) inaccessible from portions of the network. From the perspective of our classification system, we would consider these configurations as separate but intermeshed hub networks. As noted earlier, the Protocol A network is the product of three assumptions: (i) all hubs are fully interconnected; (ii) all non-hub nodes are connected to only one hub; and (iii) there are no internodal (direct service node to service node) connections. Any or all of these rules can be relaxed as long as the basic assumptions discussed in this section are not violated. This provides three binary decision variables with which to define hub network types. The three decisions are: (Dl) Node assignment either one hub assignment, or multihub assignment. (02) Direct node-node either not allowed, or allowed, (03) Hub interconnection either full, or partial. Table 3 Hub network classification system Design variables Internodal Design class Node-hub assignment connections Interhub connectivity 01 concerns whether a node can be assigned to only one hub or more than one hub and 02 refers to whether direct internodal connections which bypass the hub structure can be allowed. 03 refers to the subnetwork that connects the hubs alone; this can be fully interconnected or only partially interconnected. Journal of Transport Geography /994 Volume 2 Number / Protocol A Protocol B Protocol C Protocol D Protocol E Protocol F Protocol G Protocol H Single hub only Single hub only Single hub only Single hub only Multiple hubs allowed Multiple hubs allowed Multiple hubs allowed Multiple hubs allowed Not allowed Not allowed Allowed Allowed Not allowed Not allowed Allowed Allowed Full Partial Full Partial Full Partial Full Partial 37
The hub network design problem:M.E.O'Kelly and H.J.Miller 5 8 A E 5 8 3 3 6 8 B 5 8 ● 3 6 5 8 C G 5 8 6 Q 5 8 D H 5 8 6 6 Figure 4 Example Protocol A-H networks Table 4 Hub network design issues under different protocols with examples Design class Design variables Empirical examples" Analysis examples Protocol A Hub location Rockwell 0 Kelly(1986,1987.1992a,1992b): Node-single hub assignment Interplant communications O'Kelly and Miller (1991):Aykin (1988); Aykin and Brown (1992);Klincewicz (1991) Protocol B Hub location Satellite communications Chou (1990):Helme and Magnanti (1989) Node-single hub assignment Hub-hub links Protocol C Hub location Financial networks Aykin(1992.1993: Node-single hub assignment Campbell (1991a,1991b) Node-node links Protocol D Hub location Financial networks Unknown at this time (4/93) Node-single hub assignment Hub-hub links Node-node links Protocol E Hub location Air passenger networks Campbell (1990a.1990b) Node-multiple hub assignment Protocol F Hub location Yellow Freight Leung er al (1990): Node-multiple hub assignment Powell and Sheffi (1983) Hub-hub links Protocol G Hub location Air passenger networks Aykin(1992,1993): Node-multiple hub assignment Campbell (1991a.1991b) Node-node links Protocol H Hub location Air passenger networks Unknown at this time (4/93) Node-multiple hub assignment Hub-hub links Node-node links Note:"The empirical examples and references are discussed in the text. 38 Journal of Transport Geogruphy 1994 Volume 2 Number I
The hub network design problem: M. E. O'Kelly and H.i. Miller 5 6 5 6 5 6 5 6 8 7 8 7 8 7 8 7 A B c o E F G H 5 6 5 6 5 6 5 6 8 7 8 7 8 7 8 7 Figure 4 Example Protocol A-H networks Table 4 Hub network design issues under different protocols with examples Design class Protocol A Protocol B Protocol C Protocol D Protocol E Protocol F Protocol G Protocol H Design variables Hub location Node-single hub assignment Hub location Node-single hub assignment Hub-hub links Hub location Node-single hub assignmcnt Node-node links Hub location Node-single hub assignment Hub-hub links Node-node links Hub location Node-multiple hub assignment Hub location Node-multiple hub assignment Hub-hub links Hub location Node-multiple hub assignment Node-nodc links Hub location Node-multiple hub assignment Hub-hub links Node-nodc links Empirical examples· Rockwell Interplant communications Satellite communications Financial networks Financial networks Air passenger networks YeHow Freight Air passenger networks Air passenger nctworks Analysis examples O'Kelly (1986,1987, 1992a, 1992b); O'Kelly and Miller (1991); Aykin (1988); Aykin and Brown (1992); Klincewicz (1991) Chou (1990); Helme and Magnanti (1989) Aykin (1992,1993); Campbell (1991a, 1991b) Unknown at this timc (4/93) Campbell (1990a, 1990b) Leung et al (1990); Powell and Sheffi (1983) Aykin (1992,1993); Campbcll (1991a, 1991b) Unknown at this time (4/93) Note: "The empirical examples and references are discussed in the text. 38 Journal of Transport Geography /994 Volume 2 Numher /
The hub network design problem:M.E.O'Kelly and H.J.Miller substantial degree.The design protocols allow the In other words,the analyst should be able to decision maker to trade off the complexity of the determine the properties of the best network plan, problem against the combination of design features including the level of interhub linkage,the provision inherent in each network archetype.A decision of direct routes,and so on.The contribution of this maker can assess these trade-offs and choose a paper has been to classify the types of hub network network type as a first approximation of the design structure that can emerge.It remains a major for the particular application.Then,a specific research problem to offer a prescription for the best configuration,determined according to the relatively type of network for the various transport applica- limited number of design changes within that pro- tions tocol,can be explored.For example,if a distribution problem has large amounts of interaction between some service node pairs,the decision maker may Acknowledgements wish to abandon the convenient but restrictive This work was supported by the National Science Protocol A design archetype in favour of the more Foundation (SES-8821227,and DMS-9200292).A complex Protocol C archetype which allows inter- previous version of this paper was presented at the nodal connections.In addition,if benefits can be 1990 Annual Meeting of the Association of American derived from concentrating flows at hubs,the Geographers,Toronto,Ontario.The authors thank decision maker can also allow partial interhub both Dr Turgut Aykin and Dr James Campbell for connectivity by using Protocol D.However,this providing preprints of their working papers.Thanks would make the design problem even more complex. also to Mace Bowen,DIGIT Laboratory.University If this complexity is undesirable,internodal connect- of Utah for drawing the figures. ivity could be sacrificed in favour of partial interhub connectivity by using Protocol B.Thus,the choice of a design protocol involves trade-offs between References problem complexity and desired network properties relative to the particular distribution problem the Abdinnour.S.and Venkataramanan.M.A.(1992)'Using simulated annealing to solve the p-hub location problem', decision maker is attempting to resolve. manuscript,Proceedings of the Decision Science Institute (Abstract forthcoming) Aykin.T.(1988)'On the location of hub facilities'.Transportation Conclusion Science.22.pp.155-157 Hub networks are used for solving a class of the Aykin.T.(1992)'The hub location and routing problem' manuscrint many-to-many distribution problem.Hubs allow the Aykin.T.(1993)'Lagrangian relaxation based approaches to construction of indirect linkages between origins and capacitated hub-and-spoke network design problem'.European destinations,which can benefit operating costs, Journal of Operational Research (forthcoming) service provision and market position.These net- Aykin.T.and Brown.G.F.(1992)'Interacting new facilities and works are used for air and ground transportation and location-allocation problems',Transportation Science.26(3), pp.212-222 communication and can have a variety of configura- Bodin,L.D..Golden,B.L..Schuster.A.D.and Romig.W tions.However,the design problem for all but the (1980)'A model for the blocking of trains'.Transportation simplest network topologies can be extremely com- Research B.14B.pp.115-120 plex.Due to the nature of this design problem, Campbell.J.F.(1990a)'Freight consolidation and routing with transportation economies of scale'.Transportation Research B. researchers have been forced to rely on restrictive 24B,pp.345-361 problem assumptions and have used a wide range of Campbell,J.F.(1990b)'Locating transportation terminals to non-standardized approaches to the problem.In this serve an expanding demand'.Transportation Research B. paper,we have synthesized existing approaches to Pp.173-192 the hub network design problem and presented a Campbell.J.F.(1991a)'Hub location problems and the p-hub median problem',Center for Business and Industrial Studies framework for standardizing the problem.By doing WP 91-06-21.University of Missouri-St Louis so,we have identified examples of prototypical Campbell.J.F.(1991b)'Integer programming formulations of networks,anticipated the occurrence of other hybrid discrete hub location problems' Center for Business and Industrial Studies.WP 91-06-22,University of Missouri-St network configurations and drawn attention to some Louis gaps in the analytical literature on these nets. Chan.Y.and Ponder,R.J.(1979)'The small package air freight This paper has introduced the reader to the industry in the United States:a review of the Federal Express complexity of the hub-and-spoke network design experience'.Transportation Research A.13A.pp.221-229 problem.There are many further complexities that Chestler.L.(1985)'Overnight air express:spatial pattern. could be introduced.The obvious directions are to competition and the future in small package delivery services' Transportation Quarterly.39.pp.59-71 include capacity constraints(as suggested by Aykin, Chou,Y-H.(1990)The hierarchical-hub model for airline 1993)and to determine a dynamic facility siting plan networks' Transportation Planning and Technology.14. (as suggested by Campbell,1990b).Apart from Pp.243-258 these extensions.however,is the idea that the hub Chou,Y-H.(1993)'Airline deregulation and nodal accessibility'. Journal of Transport Geography.1.pp.36-46 network ought to be chosen without any a priori Chung.S.-H..Myung.Y.-S.,and Tcha,D.-W.(1992)'Optimal restrictions on the types of connections permitted design of a distributed network with a two-level hierarchical Journal of Transport Geography 1994 Volume 2 Number I 39
The hub network design problem: M. E. O'Kelly and H.i. Miller substantial degree. The design protocols allow the decision maker to trade off the complexity of the problem against the combination of design features inherent in each network archetype. A decision maker can assess these trade-offs and choose a network type as a first approximation of the design for the particular application. Then, a specific configuration, determined according to the relatively limited number of design changes within that protocol, can be explored. For example, if a distribution problem has large amounts of interaction between some service node pairs, the decision maker may wish to abandon the convenient but restrictive Protocol A design archetype in favour of the more complex Protocol C archetype which allows internodal connections. In addition, if benefits can be derived from concentrating flows at hubs, the decision maker can also allow partial interhub connectivity by using Protocol D. However, this would make the design problem even more complex. If this complexity is undesirable, internodal connectivity could be sacrificed in favour of partial interhub connectivity by using Protocol B. Thus, the choice of a design protocol involves trade-offs between problem complexity and desired network properties relative to the particular distribution problem the decision maker is attempting to resolve. Conclusion Hub networks are used for solving a class of the many-to-many distribution problem. Hubs allow the construction of indirect linkages between origins and destinations, which can benefit operating costs, service provision and market position. These networks are used for air and ground transportation and communication and can have a variety of configurations. However, the design problem for all but the simplest network topologies can be extremely complex. Due to the nature of this design problem, researchers have been forced to rely on restrictive problem assumptions and have used a wide range of non-standardized approaches to the problem. In this paper, we have synthesized existing approaches to the hub network design problem and presented a framework for standardizing the problem. By doing so, we have identified examples of prototypical networks, anticipated the occurrence of other hybrid network configurations and drawn attention to some gaps in the analytical literature on these nets. This paper has introduced the reader to the complexity of the hub-and-spoke network design problem. There are many further complexities that could be introduced. The obvious directions are to include capacity constraints (as suggested by Aykin, 1993) and to determine a dynamic facility siting plan (as suggested by Campbell, 1990b). Apart from these extensions, however, is the idea that the hub network ought to be chosen without any a priori restrictions on the types of connections permitted. Journal of Transport Geography 1994 Volume 2 Number I In other words, the analyst should be able to determine the properties of the best network plan, including the level of interhub linkage, the provision of direct routes, and so on. The contribution of this paper has been to classify the types of hub network structure that can emerge. It remains a major research problem to offer a prescription for the best type of network for the various transport applications. Acknowledgements This work was supported by the National Science Foundation (SES-8821227, and DMS-9200292). A previous version of this paper was presented at the 1990 Annual Meeting of the Association of American Geographers, Toronto, Ontario. The authors thank both Dr Turgut Aykin and Dr James Campbell for providing preprints of their working papers. Thanks also to Mace Bowen, DIGIT Laboratory, University of Utah for drawing the figures. References Abdinnour, S. and Venkataramanan, M.A. (1992) 'Using simulated annealing to solve the p-hub location problem', manuscript, Proceedings of the Decision Science Institute (Abstract forthcoming) Aykin, T. (1988) 'On the location of hub facilities', Transportation Science. 22, pp. 155-157 Aykin, T. (1992) 'The hub location and routing problem'. manuscript Aykin, T. (1993) 'Lagrangian relaxation based approaches to capacitated hub-and-spoke network design problem', European Journal of Operational Research (forthcoming) Aykin, T. and Brown, G.F. (1992) 'Interacting new facilities and location-allocation problems'. Transportation Science, 20(3), pp. 212-222 Bodin, L.D .. Golden. B.L., Schuster, A.D. and Romig, W. (1980) 'A model for the blocking of trains', Transportation Research B, 14B, pp. 115-120 Campbell, J.F. (1990a) 'Freight consolidation and routing with transportation economies of scale', Transportation Research B, 24B, pp. 345-301 Campbell, J.F. (1990b) 'Locating transportation terminals to serve an expanding demand', Transportation Research B. pp. 173-192 Campbell, J.F. (1991a) 'Hub location problems and the p-hub median problem', Center for Business and Industrial Studies. WP 91-iJ0-21, University of Missouri-St Louis Campbell, J.F. (199Ib) 'Integer programming formulations of discrete hub location problems', Center for Business and Industrial Studies, WP 91-iJ0-22, University of Missouri-St Louis Chan, Y. and Ponder, R.J. (1979) 'The small package air freight industry in the United States: a review of the Federal Express experience', Transportation Research A, 13A, pp. 221-229 Chestler, L. (1985) 'Overnight air express: spatial pattern, competition and the future in small package delivery services', Transportation Quarterly, 39, pp. 59-71 Chou, V-H. (1990) 'The hierarchical-hub model for airline networks', Transportation Planning and Technology, 14, pp. 243-258 Chou, V-H. (1993) 'Airline deregulation and nodal accessibility', Journal of Transport Geography, I, pp. 30--40 Chung, S.-H., Myung, Y.-S., and Tcha, D.-W. (1992) 'Optimal design of a distributed network with a two-level hierarchical 39
The hub network design problem:M.E.O'Kelly and H.1.Miller structure'.European Journul of Operational Research,62.pp. programming approach to air cargo flcet planning'.Management 105-115 Science,26.Pp.1096-1107 Daganzo.C.F.(1987)'The break-bulk role of terminals in many- MeShan.S.and Windle,R.(1989)'The implications of hub-and- to-many logistic nctworks'.Operations Research.35. spoke routing for airlinc costs and competitiveness',Logistics pp.543-555 and Transportation Review,25(3).pp.209-230) Devany.A.S.and Garges.E.H.(1972)'A forecast of air travel Minas.J.S.and Mitten.L.G.(1958)"The hub operation and and airport and airway use in 1980',Transportation Research.6. scheduling problem',Operations Research.6.pp.329-345 pp.1-18 O'Kelly,M.E.(1986)The location of interacting hub facilitics' Dempscy.P.S.and Goctz.A.R.(1992)Airline deregulation and Transportation Science,20,pp.92-106 laissez-faire mythology,Westport,CT:Ouorum Books O'Kelly,M.E.(1987)A quadratic integer program for the Flynn.J.and Ratick.S.(1988)'A multiobjective hierarchical location of interacting hub facilities'.European Journal of covering model for the Essential Air Services program'. Operational Research,32.pp.393-404 Transportation Science.22.pp.139-147 O'Kelly,M.E.(1992a)'Hub facility location with fixed costs' Fotheringham.A.S.and O'Kelly,M.E.(1989)Spatial interaction Papers in Regional Science 71(3).pp.293-306 models:formulations and applications,Dordrecht:Kluwer O'Kelly.M.E.(1992b)'A clustcring approach to the planar hub Goldman.A.J.(1969)'Optimal location for centers in a network'. location problem'.Annals of Operations Research.40 Transportation Science.3.pp.352-360) pp.,339-353 Hall.R.W.(1987)'Comparison of strategics for routing ship- O'Kelly.M.E.and Lao.Y.(1991)'Mode choice in a hub-and- ments through transportation terminals' Transportation spoke network:a zcro-one linear programming approach', Research A.21A.pp.421-429 Geographical Analysis,23.pp.283-297 Hall.R.W.(1989)Configuration of an overnight package air O'Kelly.M.E.and Miller.H.J.(1991)Solution strategics for nctwork'.Transportation Research A.23A.pp.139-149 the single facility minimax hub location problem'.Papers in Helme.M.P.and Magnanti.T.L.(1989)'Designing satellite Regional Science,70.pp.367-380 communication networks by zero-one quadratic programming' O'Kelly,M.E..Skorin-Kapov,D.and Skorin-Kapov,J.(1993) Nerworks.19.pp.427-450 An improved lower bound estimate for the hub location Kanafani.A.and Ghobrial.A.A.(1985)'Airline hubbing: problem'.Management Science (forthcoming) Some implications for airport cconomics'.Transportation Powell,W.B.and Sheffi,Y.(1983)'The load planning problem Research A,19A,pp.15-27 of motor carriers:problem description and a proposed solution Klincewicz.J.G.(1991)'Heuristics for the p-median hub location strategy'.Transportation Research A.17A.pp.471-480 problem'.European Journal of Operational Research.53. Shaw.S.-L.(1993)'Hub structures of major US passenger pp.25-37 airlines',Journal of Transport Geography,1,pp.47-58 Klincewicz,J.G.(1992)'Avoiding local optima in the p-hub Skorin-Kapov,D.and Skorin-Kapov,J.(1992)'On tabu search location problem using tabu search and GRASP'.Annals of for the location of interacting hub facilities',European Journal Operation Research,40,283-302:presented at ISOLDE V. Operational Research (torthcoming),manuscript June 1990 W.A.Harriman School for Management and Policy.SUNY Kuby.M.J.and Gray.R.G.(1993)"The hub network design Stony Brook problem with stopovers and feeders:the case of Federal Toh.R.S.and Higgins.R.G.(1985)'The impact of hub and Express'.Transportation Research A.27A.pp.1-12 spoke network centralization and route monopoly on domestic Lcung.J.M.Y..Magnanti.T.L.and Sighal.V.(1990)Routing airline profitability'.Transportation Journal.24(4),pp.16-27 in point-to-point delivery systems:formulations and heuristics' Weinstein.S.B.(1982)'A perspective on financial industry Transportution Science.24.pp.245-260 networking',Journal of Telecommunication Networks.1(4). Marsten.R.E.and Mucller.M.R.(1980)'A mixed-integer pp.317-332 40 Journal of Transport Geography 1994 Volume 2 Number I
The hub network design problem: M. E. O'Kelly and H.J. Miller structure'. European Journal of Operational Research, 62, pp. 105-115 Daganzo, C.F. (1987) 'The break-bulk role of terminals in manyto-many logistic networks', Operations Research, 35, pp. 543-555 Devany, A.S. and Garges, E.H. (1972) 'A forecast of air travel and airport and airway use in 1980', Transportation Research, 6, pp. 1-18 Dempsey, P.S. and Goetz, A.R. (1992) Airline deregulation and laissez-faire mythology, Westport, CT: Ouorum Books Flynn, .I. and Ratick, S. (1988) 'A multiobjective hierarchical covering model for the Essential Air Services program', Transportation Science, 22, pp. 139-147 Fotheringham, A.S. and O'Kelly, M.E. (1989) Spatial interaction models: formulations and applications, Dordrecht: Kluwer Goldman, A ..I. (1969) 'Optimal location for centers in a network', Transportation Science, 3, pp. 352-360 Hall, R.W. (1987) 'Comparison of strategies for routing shipments through transportation terminals'. Transportation Research A, 21A, pp. 421-429 Hall, R.W. (1989) 'Configuration of an overnight package air network', Transportation Research A, 23A, pp. 139-149 Helme, M.P. and Magnanti, T.L. (1989) 'Designing satellite communication networks by zero-one quadratic programming', Networks, 19, pp. 427-450 Kanafani, A. and Ghobrial, A.A. (1985) 'Airline hubbing: Some implications for airport economics', Transportation Research A, 19A, pp. 15-27 Klineewiez, .I .G. (1991) 'Hcuristics for thc p-median hub location problem', European Journal of Operational Research, 53, pp. 25-37 Klincewiez, .I.G. (1992) 'Avoiding local optima in the p-hub location problem using tabu search and GRASP', Annals of Operation Research, 40, 283-302; presented at ISOLDE Y, June 1990 Kuby, M..I. and Gray, R.G. (1993) 'The hub network design problem with stopovers and feeders: the case of Federal Express', Transportation Research A, 27A, pp. 1-12 Leung, .I.M.Y., Magnanti, T.L. and Sighal, Y. (1990) 'Routing in point-to-point delivery systems: formulations and heuristics', Transportation Science, 24, pp. 245-260 Marsten, R.E. and Mueller, M.R. (1980) 'A mixed-integer 40 programming approach to air cargo fleet planning', Management Science, 26, pp. 1096--1107 McShan, S. and Windle, R. (1989) 'The implications of hub-andspoke routing for airline costs and competitiveness', Logistics and Transportation Review, 25(3), pp. 209-230 Minas, .I.S. and Mitten, L.G. (1958) The hub operation and scheduling problem', Operations Research, 6, pp. 329-345 O'Kelly, M.E. (1986) 'The location of interacting hub facilities', Transportation Science, 20, pp. 92-106 O'Kelly, M.E. (1987) 'A quadratic intcger program for the location of interacting hub facilities', European Journal of Operational Research, 32, pp. 393-404 O'Kclly, M.E. (1992a) 'Hub facility location with fixcd costs', Papers in Regional Science 71(3), pp. 293-306 O'Kelly, M.E. (1992b) 'A clustering approach to the planar hub location problem', Annals of Operations Research, 40, pp. 339-353 O'Kelly, M.E. and Lao, Y. (1991) 'Modc choice in a hub-andspokc network: a zer()-{me linear programming approach', Geographical Analysis, 23, pp. 283-297 O'Kelly, M.E. and Millcr, H..I. (1991) 'Solution strategies for the single facility minimax hub location problem'. Papers in Regional Science, 70, pp. 367-380 O'Kelly, M.E., Skorin-Kapov, D. and Skorin-Kapov, .I. (1993) 'An improved lower bound estimatc for the hub location problem', Management Science (fortheoming) Powcll, W.B. and Sheffi, Y. (1983) 'The load planning problem of motor carriers: problem description and a proposed solution strategy', Transportation Research A, 17A, pp. 471-480 Shaw, S.-L. (1993) 'Hub structures of major US passenger airlines', Journal of Transport Geography, I, pp. 47-58 Skorin-Kapov, D. and Skorin-Kapov,.I. (1992) 'On tabu search for the location of interacting hub facilities', European Journal of Operational Research (forthcoming), manuscript, W. A. Harriman School for Management and Policy, SUNY Stony Brook Toh, R.S. and Higgins, R.G. (1985) 'The impact of hub and spoke network centralization and route monopoly on domestic airline profitability', Transportation Journal, 24(4), pp. 16--27 Weinstein, S.B. (1982) 'A perspeetivc on financial industry networking', Journal of Telecommunication Networks, 1(4), pp.317-332 Journal of Transport Geography 1494 Volume 2 Numoer I