Transshipment Problem

309. Transshipment Problem

Generalization of the transportation problem allowing intermediate transshipment nodes — locations that neither produce nor consume, but pass flow through.

309.1. Formulation

Three node types:

Supply nodes ( $𝑏_{𝑖} > 0$ ): produce $𝑏_{𝑖}$ units
Demand nodes ( $𝑏_{𝑖} < 0$ ): consume $| 𝑏_{𝑖} |$ units
Transshipment nodes ( $𝑏_{𝑖} = 0$ ): inflow = outflow

For each arc $(𝑖, 𝑗) \in 𝐸$ , decision $𝑥_{𝑖 𝑗} \geq 0$ = flow on arc, with cost $𝑐_{𝑖 𝑗}$ per unit.

min \sum_{(𝑖, 𝑗) \in 𝐸} 𝑐_{𝑖 𝑗} 𝑥_{𝑖 𝑗}

s.t. flow conservation at each node:

\sum_{𝑗 : (𝑗, 𝑖) \in 𝐸} 𝑥_{𝑗 𝑖} - \sum_{𝑗 : (𝑖, 𝑗) \in 𝐸} 𝑥_{𝑖 𝑗} = - 𝑏_{𝑖}, \forall 𝑖 \in 𝑉

(Inflow minus outflow = $- 𝑏_{𝑖}$ : positive for sinks, negative for sources, zero for transshipment.)

309.2. Capacitated variant

Now cap each arc: flow can’t exceed an edge’s capacity $𝑢_{𝑖 𝑗}$ . Same objective and conservation, plus a per-arc upper bound:

min \sum_{(𝑖, 𝑗) \in 𝐸} 𝑐_{𝑖 𝑗} 𝑥_{𝑖 𝑗}

\sum_{𝑗 : (𝑗, 𝑖) \in 𝐸} 𝑥_{𝑗 𝑖} - \sum_{𝑗 : (𝑖, 𝑗) \in 𝐸} 𝑥_{𝑖 𝑗} = - 𝑏_{𝑖}, \forall 𝑖 \in 𝑉

0 \leq 𝑥_{𝑖 𝑗} \leq 𝑢_{𝑖 𝑗}, \forall (𝑖, 𝑗) \in 𝐸

lower bound $0$ : no reverse flow on the arc
upper bound $𝑢_{𝑖 𝑗}$ : the arc can’t carry more than its capacity

309.3. Reduction to transportation problem

Any transshipment problem with $𝑛$ nodes can be converted into a transportation problem on a complete bipartite graph (every source potentially connects to every demand via possible transshipment paths) — at the cost of larger problem size.

In practice solve directly as an LP, or use network simplex.

309.4. Why it matters

The transshipment formulation is the canonical model for:

Multi-echelon distribution: factory → DC → store
Hub-and-spoke networks: airlines, parcel logistics
Inter-regional sourcing: route through cheapest intermediate even when not on the direct path
Min-cost flow generalization — see MCNF

309.5. See also

Transportation Problem — special case (no intermediates)
Multi-Commodity Network Flow
Network Simplex