Data Pattern Pro

Mathematical programming / Networks and location

Transportation Problem

Ship goods from a set of supply points to a set of demand points at minimum cost, respecting supply and demand limits.

Note Beginner

Short note. A compact reference, correct as far as it goes. It will be expanded into a full guide with a worked example and an interactive demonstration.

Problem

Given fixed supply at several origins and fixed demand at several destinations, and a per-unit shipping cost for every origin-destination pair, decide how much to ship along each route to satisfy demand at minimum total cost.

When to use it

Distribution planning between existing (already-built) warehouses and customers or stores — this is the assignment problem’s bigger sibling, used when quantities matter, not just one-to-one matches, and you’re not deciding whether to open a facility (that’s Facility Location).

Formulation

Continuous x_ij = units shipped from origin i to destination j:

minimize   sum(c_ij * x_ij)
subject to:
  sum_j(x_ij) <= supply_i     for all i
  sum_i(x_ij) >= demand_j     for all j
  x_ij >= 0

Like the assignment problem, this is a pure network-flow structure — the constraint matrix is totally unimodular, so an integral optimal solution exists even without declaring x_ij as integer, whenever supply and demand are integers.

Code sketch

import pulp

prob = pulp.LpProblem("transportation", pulp.LpMinimize)
x = {(i, j): pulp.LpVariable(f"ship_{i}_{j}", lowBound=0)
     for i in origins for j in destinations}

prob += pulp.lpSum(cost[i, j] * x[i, j] for i in origins for j in destinations)

for i in origins:
    prob += pulp.lpSum(x[i, j] for j in destinations) <= supply[i]
for j in destinations:
    prob += pulp.lpSum(x[i, j] for i in origins) >= demand[j]

Pitfalls

  • Check feasibility first: if total supply is less than total demand, the model is infeasible before you even get to costs — validate the balance before debugging the solver output.
  • This scales to thousands of origin-destination pairs without trouble since it’s a pure LP — if you find yourself adding binaries “just in case,” you’ve probably drifted into a different pattern (facility location, or a routing problem).
  • Real transportation networks often have per-route capacity limits — add x_ij <= capacity_ij per pair; it doesn’t change the structure, just adds bounds.