Hub Location Problem

HLP · O'KELLY 1987

Logistics · Network & Facility · Strategic

The Hub Location Problem is location theory applied to hub-and-spoke networks: traffic between pairs of nodes does not travel directly but is consolidated through an intermediate layer of hubs, often with a discount $\alpha \in (0, 1)$ on inter-hub flow to capture economies of scale. The originating formulation is O'Kelly (1987); Campbell (1994) distinguished single-allocation (each spoke assigned to exactly one hub) from multiple-allocation (spokes may be assigned to more than one hub for different destinations). Today's best survey is Alumur & Kara (2008), "Network hub location problems: The state of the art".

Formulation sketch

Single-allocation p-Hub Median · O'Kelly 1987

SymbolMeaning
$N$set of nodes (candidate hubs and spokes)
$p$required number of hubs
$w_{ij}$traffic (flow) from $i$ to $j$
$d_{kl}$distance from hub $k$ to hub $l$
$\alpha \in (0,1)$inter-hub consolidation discount
$z_{ik} \in \{0,1\}$1 if node $i$ is assigned to hub $k$ (with $z_{kk} = 1$ when $k$ itself is open)
Objective: total weighted transport cost
$$\min \; \sum_{i \in N} \sum_{j \in N} w_{ij} \sum_{k \in N} \sum_{l \in N} z_{ik} \, z_{jl} \, \left( d_{ik} + \alpha \, d_{kl} + d_{lj} \right)$$
(1) Each node assigned to exactly one hub
$$\sum_{k \in N} z_{ik} = 1 \quad \forall i \in N$$
(2) Assignment only to opened hubs
$$z_{ik} \le z_{kk} \quad \forall i, k \in N$$
(3) Exactly $p$ hubs opened
$$\sum_{k \in N} z_{kk} = p$$
(4) Binary
$$z_{ik} \in \{0,1\}$$

Four canonical variants. p-hub median (shown above: fix $p$, minimise total cost). Uncapacitated hub-location problem (UHLP): replace cardinality with fixed opening costs. Capacitated variants add throughput bounds at each hub. p-hub center: minimise max origin-destination cost (minimax objective).

Linearisation. The objective above is quadratic in the $z$'s. Linearisations range from Campbell (1994) flow-based reformulations to the tight Ernst-Krishnamoorthy (1996) mixed-integer LP that uses $O(n^3)$ flow variables per commodity. Modern commercial MIP handles moderate instances; Benders decomposition and Lagrangian relaxation are standard for larger cases.

Applications. Air freight (FedEx, UPS), passenger airlines, postal networks, less-than-truckload (LTL) freight, and increasingly telecommunications and data-centre design. The inter-hub discount $\alpha$ captures real economies in vehicle fill rate and equipment utilisation.

Key references

O'Kelly, M. E. (1987).
“A quadratic integer program for the location of interacting hub facilities.”
European Journal of Operational Research, 32(3), 393–404. doi:10.1016/S0377-2217(87)80007-3
Campbell, J. F. (1994).
“Integer programming formulations of discrete hub location problems.”
European Journal of Operational Research, 72(2), 387–405. doi:10.1016/0377-2217(94)90318-2
Ernst, A. T., & Krishnamoorthy, M. (1996).
“Efficient algorithms for the uncapacitated single allocation p-hub median problem.”
Location Science, 4(3), 139–154. doi:10.1016/S0966-8349(96)00011-3
Alumur, S., & Kara, B. Y. (2008).
“Network hub location problems: The state of the art.”
European Journal of Operational Research, 190(1), 1–21. doi:10.1016/j.ejor.2007.06.008
Farahani, R. Z., Hekmatfar, M., Arabani, A. B., & Nikbakhsh, E. (2013).
“Hub location problems: A review of models, classification, solution techniques, and applications.”
Computers & Industrial Engineering, 64(4), 1096–1109. doi:10.1016/j.cie.2013.01.012
Contreras, I., Cordeau, J.-F., & Laporte, G. (2011).
“Benders decomposition for large-scale uncapacitated hub location.”
Operations Research, 59(6), 1477–1490. doi:10.1287/opre.1110.0965

Designing a hub network?
The discount α captures most of the economics — let's get it right.

Get in Touch
Data and numerical examples are illustrative. Pages on this site are educational tools, not production software.