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 33The 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 conceptual￾ization 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 proper￾ties. 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 charac￾teristics 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 least￾cost 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, con￾venient 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; Skorin￾Kapov 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 single￾facility problems in discrete space: under both minisum and minimax objectives, this problem can be solved through simple enumeration. More com￾plex, 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, Kalamazoo￾Lansing). 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 alloca￾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￾and a master-hub can be solved optimally using Journal of Transport Geography 1994 Volume 2 Numher I 33