Hub & Spoke Network Design
p-Hub Median Problem · NP-Hard
A freight carrier must choose which of 8 cities to designate as hubs, routing all shipments through at most two hubs with a consolidation discount α. Hub network design determines 60–70% of a carrier's long-run cost structure.
Where This Decision Fits
Freight operations chain — the highlighted step is what this page optimizes
The Problem
From freight networks to combinatorial optimization
A freight network connects 8 cities (nodes) that exchange shipments. The carrier must select p hubs from these cities, routing every origin–destination pair through at most two hubs. Shipments between hubs travel on high-capacity trunk routes with a consolidation discount α (0 < α ≤ 1), reflecting economies of scale from bundling freight.
This is the p-Hub Median problem (O'Kelly, 1987)—an NP-hard combinatorial optimization problem. The objective is to minimize total weighted transportation cost across all O–D pairs, where the cost of routing from origin i to destination j via hubs k and m includes collection, transfer (discounted), and distribution legs.
| Freight Domain | p-Hub Median Model | |
|---|---|---|
| City / depot | Node i ∈ N | |
| Hub terminal | Hub k ∈ H ⊆ N | |
| Shipment volume | Flow wij | |
| Transport distance | Cost dij | |
| Consolidation savings | Discount factor α | |
| Number of hubs | Parameter p |
Mathematical Formulation
The single-allocation p-Hub Median model
Subject To assignment: Σk xik = 1 ∀ i ∈ N // each node assigned to exactly one hub
hub count: Σk yk = p // exactly p hubs selected
hub link: xik ≤ yk ∀ i,k ∈ N // assign only to open hubs
binary: xik, yk ∈ {0,1} ∀ i,k ∈ N
Interactive Solver
Choose a scenario, tune parameters, and watch the network form
Hub Network Solver
Dual-hub freight network with strong consolidation discount (α=0.6). Classic FedEx/UPS topology.
| Algorithm | Hubs Selected | Total Cost | vs Direct | Savings % | Time |
|---|---|---|---|---|---|
| Press Solve to run all algorithms | |||||
Solution Algorithms
Three approaches to hub location
Greedy (Most Central)
The greedy heuristic iteratively selects the node that yields the greatest cost reduction as a hub. At each step, the node with the highest total weighted flow (most central by traffic) is chosen, approximating the medoid selection used in clustering. While fast, it can get trapped in suboptimal configurations.
In the freight context, this mirrors the intuition of placing hubs at the busiest traffic intersections—cities with the highest total tonnage flowing through them.
Exhaustive Enumeration
For small instances (p ≤ 2 with 8 nodes gives C(8,2) = 28 subsets), exhaustive enumeration evaluates every possible hub combination and returns the globally optimal solution. Each candidate set requires computing the full O–D cost matrix through the selected hubs.
This guarantees optimality but scales as C(n,p), which becomes intractable for larger networks. For our 8-city demo, it remains practical up to p = 3 (56 subsets).
Swap Local Search
Starting from the greedy solution, the swap heuristic iteratively tries replacing each current hub with every non-hub node. If any swap reduces total cost, the best improving swap is accepted. The process repeats until no improving swap exists (local optimum).
This is the Teitz & Bart (1968) vertex substitution method adapted for hub networks. It often finds the global optimum on small instances and provides good solutions on larger ones within a bounded number of iterations.
Complexity & Hardness
- Greedy: O(n²p) — fast but no optimality guarantee, typically within 5–15% of optimal
- Exhaustive: O(C(n,p) × n²) — optimal but exponential in p; practical only for small n
- Swap: converges to local optimum in O(n²p) per iteration, typically 2–5 iterations
- NP-Hardness: the p-Hub Median problem is NP-hard (Kara & Tansel, 2000); exact methods use branch-and-bound or Benders decomposition for large instances
- Practical note: real hub network designs from carriers like FedEx, UPS, and DHL use meta-heuristics (GA, SA) combined with simulation for robustness under demand uncertainty
References
Key literature on hub location problems