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