The hub network design problem:M.E.O'Kelly and H.J.Miller between all origins and destinations in the network. The three binary decision variables create 23=8 hub Also observe that a service node which is directly network classes,which are defined in Table 3 connected to all other service nodes does not Example networks can be seen in Figure 4. influence the hub network design problem.There- While it is difficult to find an exact match in the fore we disregard a service node as part of the hub real world to these prototypical networks,there are network if it essentially bypasses that network. several excellent representative examples.Protocol Note that property I does not allow the 'spider A is similar to the Rockwell International interplant leg'configuration unless the intermediate node (eg communications system illustrated in Fotheringham Bloomington/Normal in Figure 2)is defined as a and O'Kelly (1989,p.172).Protocol B can be seen hub,since that location receives throughflow.This in the satellite communications network design does not greatly reduce the generality of the hub proposed by Helme and Magnanti(1989).Note that network classification system since hubs can handle in their approach (see p.431,Figure 2),each node any amount of throughflow,even if this flow is from is connected to one of the available hubs,but these only one service node.In fact,intermediate nodes in hubs are not all connected directly to one another. a spider leg configuration do perform one of the Instead they have a link to a super hub (satellite). major services of a hub (ie the consolidation of Protocols C and D can be seen to a certain extent in flows),although other services (ie sorting)may not some financial networks which have single-hub be performed.Recently,Kuby and Gray (1993) assignment,but varying degrees of direct node-to- have developed an analysis of the hub network node connections and interhub connectivity design problem with stopovers and feeders.They (Weinstein,1982).Protocol E is seen in McShan and suggest that in the case of Federal Express,spider Windle (1989,p.213)where there are connected leg links to the hub at Memphis are common and hubs,but multiple-hub allocations.The Yellow require careful analysis. Freight system shown in Figure 3 is an excellent Since we are primarily concerned with the situation example of Protocol F.Many air passenger systems where hubs are selected from the existing set of illustrated in Shaw (1993)exemplify Protocols G origins and destinations (ie the discrete space and H problem,meaning that hubs are also flow origins A key feature of our classification system concerns and destinations),network configurations in which the complexity of the hub network design problem hubs have no interconnections (see,eg,Hall,1987. The basic design questions inherent in all protocols 1989)are not valid since this would make certain are the locations of hubs and the assignment of non- hubs (as flow destinations)inaccessible from hub nodes to hubs.Beyond this,each protocol portions of the network.From the perspective of our differs with regard to the freedom to configure arcs classification system,we would consider these in the network.For example,in Protocol A there are configurations as separate but intermeshed hub no 'free'arcs:hubs must be fully interconnected, networks. only one arc connects any node to any hub,and As noted earlier,the Protocol A network is the direct internodal connections are not allowed.in product of three assumptions:(i)all hubs are fully contrast,all arcs (existing and potential)in a interconnected;(ii)all non-hub nodes are connected Protocol H network are free for variable reconfigura- to only one hub;and (iii)there are no internodal tion within the constraints of that protocol.Table 4 (direct service node to service node)connections. indicates the decision variables that occur in each of Any or all of these rules can be relaxed as long as the the design problems. basic assumptions discussed in this section are not An important implication for hub network design violated.This provides three binary decision variables is that while the consideration of all possible with which to define hub network types.The three configurations for a hub network results in a very decisions are complex design problem.the use of the classification D1)Node assignment either one hub assign- system allows this complexity to be managed to a ment. or multihub assignment. Table 3 Hub network classification system (D2)Direct node-node either not allowed, allowed. Design variables (D3)Hub interconnection either full Internodal Interhub Design class Node-hub assignment or partial. connections connectivity Protocol A Single hub only Not allowed Full DI concerns whether a node can be assigned to only Protocol B Single hub only Not allowed Partial one hub or more than one hub and D2 refers to Protocol C Single hub only Allowed Full Protocol D whether direct internodal connections which bypass Single hub only Allowed Partial Protocol E Multiple hubs allowed Not allowed Full the hub structure can be allowed.D3 refers to the Protocol F Multiple hubs allowed Not allowed Partial subnetwork that connects the hubs alone;this can be Protocol G Multiple hubs allowed Allowed Full fully interconnected or only partially interconnected. Protocol H Multiple hubs allowed Allowed Partial Journal of Transport Geography 1994 Volume 2 Number I 37The hub network design problem: M.E. O'Kelly and H.J. Miller The three binary decision variables create 23 = 8 hub network classes, which are defined in Table 3. Example networks can be seen in Figure 4. While it is difficult to find an exact match in the real world to these prototypical networks, there are several excellent representative examples. Protocol A is similar to the Rockwell International interplant communications system illustrated in Fotheringham and O'Kelly (1989, p. 172). Protocol B can be seen in the satellite communications network design proposed by Helme and Magnanti (1989). Note that in their approach (see p. 431, Figure 2), each node is connected to one of the available hubs, but these hubs are not all connected directly to one another. Instead they have a link to a super hub (satellite). Protocols C and 0 can be seen to a certain extent in some financial networks which have single-hub assignment, but varying degrees of direct node-to￾node connections and interhub connectivity (Weinstein, 1982). Protocol E is seen in McShan and Windle (1989, p. 213) where there are connected hubs, but multiple-hub allocations. The Yellow Freight system shown in Figure 3 is an excellent example of Protocol F. Many air passenger systems illustrated in Shaw (1993) exemplify Protocols G and H. A key feature of our classification system concerns the complexity of the hub network design problem. The basic design questions inherent in all protocols are the locations of hubs and the assignment of non￾hub nodes to hubs. Beyond this, each protocol differs with regard to the freedom to configure arcs in the network. For example, in Protocol A there are no 'free' arcs: hubs must be fully interconnected, only one arc connects any node to any hub, and direct internodal connections are not allowed. in contrast, all arcs (existing and potential) in a Protocol H network are free for variable reconfigura￾tion within the constraints of that protocol. Table 4 indicates the decision variables that occur in each of the design problems. An important implication for hub network design is that while the consideration of all possible configurations for a hub network results in a very complex design problem, the use of the classification system allows this complexity to be managed to a between all origins and destinations in the network. Also observe that a service node which is directly connected to all other service nodes does not influence the hub network design problem. There￾fore we disregard a service node as part of the hub network if it essentially bypasses that network. Note that property 1 does not allow the 'spider leg' configuration unless the intermediate node (eg Bloomington/Normal in Figure 2) is defined as a hub, since that location receives throughflow. This does not greatly reduce the generality of the hub network classification system since hubs can handle any amount of throughflow, even if this flow is from only one service node. In fact, intermediate nodes in a spider leg configuration do perform one of the major services of a hub (ie the consolidation of flows), although other services (ie sorting) may not be performed. Recently, Kuby and Gray (1993) have developed an analysis of the hub network design problem with stopovers and feeders. They suggest that in the case of Federal Express, spider leg links to the hub at Memphis are common and require careful analysis. Since we are primarily concerned with the situation where hubs are selected from the existing set of origins and destinations (ie the discrete space problem, meaning that hubs are also flow origins and destinations), network configurations in which hubs have no interconnections (see, eg, Hall, 1987, 1989) are not valid since this would make certain hubs (as flow destinations) inaccessible from portions of the network. From the perspective of our classification system, we would consider these configurations as separate but intermeshed hub networks. As noted earlier, the Protocol A network is the product of three assumptions: (i) all hubs are fully interconnected; (ii) all non-hub nodes are connected to only one hub; and (iii) there are no internodal (direct service node to service node) connections. Any or all of these rules can be relaxed as long as the basic assumptions discussed in this section are not violated. This provides three binary decision variables with which to define hub network types. The three decisions are: (Dl) Node assignment either one hub assign￾ment, or multihub assignment. (02) Direct node-node either not allowed, or allowed, (03) Hub interconnection either full, or partial. Table 3 Hub network classification system Design variables Internodal Design class Node-hub assignment connections Interhub connectivity 01 concerns whether a node can be assigned to only one hub or more than one hub and 02 refers to whether direct internodal connections which bypass the hub structure can be allowed. 03 refers to the subnetwork that connects the hubs alone; this can be fully interconnected or only partially interconnected. Journal of Transport Geography /994 Volume 2 Number / Protocol A Protocol B Protocol C Protocol D Protocol E Protocol F Protocol G Protocol H Single hub only Single hub only Single hub only Single hub only Multiple hubs allowed Multiple hubs allowed Multiple hubs allowed Multiple hubs allowed Not allowed Not allowed Allowed Allowed Not allowed Not allowed Allowed Allowed Full Partial Full Partial Full Partial Full Partial 37