The hub network design problem:M.E.O'Kelly and H.J.Miller Table 1 Traditional location problem analogues under Protocol A restrictions Number of hubs Spatial constraint Design objective Problem characteristics Source Single Planar Minisum Weber least-cost location problem O'Kelly (1986) Single Planar Minimax Round-trip location problem O'Kelly and Miller (1991) Single Discrete Minisum Trivial;complete enumeration Single Discrete Minimax Trivial:complete enumeration Multiple Planar Minisum Location-allocation problem Aykin and Brown (1992):O'Kelly (1992b) Multiple Planar Minimax Unsolved Multiple Discrete Minisum Quadratic assignment problem with Avkin (1988): p-median constraints Klincewicz (1991): O'Kelly (1987). O'Kelly (1992a) Multiple Discrete Minimax Integer programming formulation Proposed in Campbell (i991b) Central Wisconsin ● Appleton Green Bay Rochester La Crosse Saginaw Buffalo Muskegon Milwaukee ●Grand Rapids Flint Madison 角Lansing Detroit Kalamazoo Rockford Des Moines Peoria ● Baltimore Bloomington /Normal Indianapolis Columbus Figure 2 Skyway Airlines Source:Columbus Dispatch (30 May 1991.p.A-2). linear programming.In general,however,relaxing metric (the latter metric limits travel to rectangular Protocol A restrictions greatly complicates the hub dimensions).Daganzo (1987)and Hall (1987)also network design problem.This added complexity has fix the locations and service areas of the hubs.This necessitated the use of additional restrictions in restriction is relaxed by Campbell (1990a,1990b). order to manage the design problem.Table 2 Partial interhub connections concentrate flows at provides some examples. particular hub facilities,which allows the exploitation One of the more common Protocol A relaxations of flow-processing economies of scale.Leung et al attempted is the assignment of nodes to more than (1990)allow partially interconnected hubs as well as one hub.Multiple-hub assignment can save trans- multiple hub assignment by separating the node-hub portation costs by tailoring the selection of hubs to assignment problem from the interhub routeing the eventual destinations of the flows being shipped problem.The routeing problem is solved by treating from an origin node thus reducing the distance it as a multicommodity flow problem,with each travelled.In addressing this routeing problem commodity distinguished by its origin-destination Daganzo (1987),and Hall (1987)are able to derive pair.Chou (1990)restricts topology to partially analytical solutions only by restricting the spatial interconnected hubs by requiring the network to be dimension of the problem to linear space or Li minimally connected,Since the network is a minimal 34 Journal of Trunsport Geography 1994 Volumne 2 Number IThe hub network design problem: M. E. O'Kelly and H.i. Miller Table 1 Traditional location problem analogues under Protocol A restrictions Number of hubs Spatial constraint Design objective Problem characteristics Source Single Planar Minisum Weber least-cost location problem O'Kelly (1986) Single Planar Minimax Round-trip location problem O'Kelly and Miller (1991) Single Discrete Minisum Trivial; complete enumeration Single Discrete Minimax Trivial; complete enumeration Multiple Planar Minisum Location-allocation problem Aykin and Brown (1992); O'Kelly (1992b) Multiple Planar Minimax Unsolved Multiple Discrete Minisum Quadratic assignment problem with Aykin (191\1\); p-median constraints Klinccwicz (1991); O'Kelly (191\7). O'Kelly (1992a) Multiple Discrete Minimax Integer programming formulation Proposed in Campbell (1991b) Central Wisconsin Peoria Green Bay Baltimore Indianapolis Figure 2 Skyway Airlines Source: Columbus Dispatch (30 May 1991, p. A-2). linear programming. In general, however, relaxing Protocol A restrictions greatly complicates the hub network design problem. This added complexity has necessitated the use of additional restrictions in order to manage the design problem. Table 2 provides some examples. One of the more common Protocol A relaxations attempted is the assignment of nodes to more than one hub. Multiple-hub assignment can save trans￾portation costs by tailoring the selection of hubs to the eventual destinations of the flows being shipped from an origin node thus reducing the distance travelled. In addressing this routeing problem Daganzo (1987), and Hall (1987) are able to derive analytical solutions only by restricting the spatial dimension of the problem to linear space or L 1 34 metric (the latter metric limits travel to rectangular dimensions). Daganzo (1987) and Hall (1987) also fix the locations and service areas of the hubs. This restriction is relaxed by Campbell (1990a, 1990b). Partial interhub connections concentrate flows at particular hub facilities, which allows the exploitation of flow-processing economies of scale. Leung et al (1990) allow partially interconnected hubs as well as multiple hub assignment by separating the node-hub assignment problem from the interhub routeing problem. The routeing problem is solved by treating it as a multicommodity flow problem, with each commodity distinguished by its origin-destination pair. Chou (1990) restricts topology to partially interconnected hubs by requiring the network to be minimally connected. Since the network is a minimal Jot/mal of Transport Geography /994 Volt/me 2 Nt/mher I