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 IThe 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 inter￾active modifications. Table 2 illustrates the wide variety of restrictions exploited in order to facilitate model solutions for relatively complex configurations. Restrictions in￾clude: (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 com￾ponents (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 implica￾tions 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 through￾flows 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