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 IThe 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 conveni￾ence. 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, re￾searchers have had to relax some of its restrictions in order to remain relevant to real-world distribution problems. In general, these extensions greatly com￾plicate 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 applica￾tions. 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 real￾world 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 /