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 39The 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 pro￾tocol, 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 inter￾nodal 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 connect￾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 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 net￾works are used for air and ground transportation and communication and can have a variety of configura￾tions. However, the design problem for all but the simplest network topologies can be extremely com￾plex. 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 applica￾tions. 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