306. Transshipment Problem

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

306.1. Formulation

Three node types:

• Supply nodes (): produce units
• Demand nodes (): consume units
• Transshipment nodes (): inflow = outflow

For each arc , decision = flow on arc, with cost per unit.

s.t. flow conservation at each node:

(Inflow minus outflow = : positive for sinks, negative for sources, zero for transshipment.)

306.2. 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.

306.3. 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

306.4. See also

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