Introduction

Picture a handful of warehouses, each holding a stack of identical crates, and a handful of stores, each needing a certain number of those crates. Every warehouse-to-store route has a shipping cost per crate. Your job is to decide how many crates travel along each route so that every store gets exactly what it ordered, no warehouse ships more than it has, and the total bill is as small as possible.

This is the transportation problem, first studied by Frank Hitchcock in 1941 and Tjalling Koopmans during World War II — work that helped earn Koopmans a share of the 1975 Nobel Prize in Economics. It sounds like the kind of puzzle that might force you to try every combination. It doesn't.

The transportation problem is one of the great success stories of optimization: it has a clean structure, it is solved exactly in polynomial time, and it taught a generation of researchers what an easy hard-looking problem feels like.

Balance Supply and Demand

Below are two warehouses and three stores. Each warehouse has a supply; each store has a demand; each cell holds the cost to ship one crate along that route. Edit any number, then press Solve to see the cheapest plan that satisfies every store.

<p class="hint">Two warehouses (rows) supply three stores (columns). Each cell is the cost to ship one crate along that route. Edit any number, then press <b>Solve</b> — the minimum-cost shipping plan appears instantly. Supply and demand are balanced for you.</p>
<div class="grid" id="grid"></div>
<div class="status" id="status">Edit the numbers, then Solve.</div>
<div class="btns">
  <button id="solve" type="button">Solve</button>
  <button id="rand" type="button" class="ghost">Randomize costs</button>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .7rem; line-height: 1.45; }
.grid { display: grid; grid-template-columns: 90px repeat(3, 1fr) 70px; gap: 6px; align-items: stretch; }
.h { font: 700 13px system-ui; display: flex; align-items: center; justify-content: center;
     color: #1d3557; text-align: center; }
.lab { font: 700 13px system-ui; display: flex; align-items: center; color: #1d3557; }
.cell { position: relative; background: #eef3f7; border: 1px solid #cdd9e3; border-radius: 8px;
        min-height: 54px; display: flex; flex-direction: column; align-items: center; justify-content: center; }
.cell input { width: 48px; text-align: center; font: 700 15px ui-monospace, monospace; border: none;
              background: transparent; color: #1d3557; }
.cell input:focus { outline: 2px solid #457b9d; border-radius: 4px; }
.ship { font: 700 12px system-ui; margin-top: 2px; color: #0a7d33; min-height: 14px; }
.ship.empty { color: #9aa6b1; }
.sd { background: #1d3557; color: #fff; border-radius: 8px; display: flex; align-items: center;
      justify-content: center; font: 700 14px ui-monospace, monospace; }
.sd input { width: 40px; text-align: center; font: 700 14px ui-monospace, monospace; border: none;
            background: transparent; color: #fff; }
.status { font-size: 1rem; font-weight: 600; margin: .8rem 0 .5rem; min-height: 1.4em; color: #0a7d33; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; }
button { font: 600 14px system-ui; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Transportation problem: ship from sources (supplies) to sinks (demands) at minimum total cost. It is a linear program with network structure, solved in polynomial time by the network simplex. Here m=2, n=3 is tiny, so we compute the true optimum by enumerating basic feasible solutions — the cost function is linear, so the minimum is always attained at such a vertex.
const M = 2, N = 3;
let cost = [[4, 6, 8], [9, 5, 3]];
let supply = [12, 8];           // total 20
let demand = [7, 6, 7];         // total 20

// Enumerate every integer shipment matrix consistent with supply/demand and return the cheapest. Feasible region is small; this is an exact LP solve.
function solve() {
  const total = supply.reduce((a, b) => a + b, 0);
  let best = null, bestCost = Infinity;
  // Choose x[0][0], x[0][1] freely (0..supply[0]); the rest is forced by the balance equations because m=2, n=3 leaves m*n - (m+n-1) = 2 free cells.
  for (let a = 0; a <= supply[0]; a++) {
    for (let b = 0; b <= supply[0] - a; b++) {
      const x = [[a, b, supply[0] - a - b], [0, 0, 0]];
      x[1][0] = demand[0] - x[0][0];
      x[1][1] = demand[1] - x[0][1];
      x[1][2] = demand[2] - x[0][2];
      if (x[1][0] < 0 || x[1][1] < 0 || x[1][2] < 0) continue;
      // (row-1 sum already equals supply[1] by balance: total - supply[0])
      let c = 0;
      for (let i = 0; i < M; i++) for (let j = 0; j < N; j++) c += x[i][j] * cost[i][j];
      if (c < bestCost) { bestCost = c; best = x.map(r => r.slice()); }
    }
  }
  return { plan: best, cost: bestCost };
}

function buildGrid() {
  const g = document.getElementById('grid'); g.innerHTML = '';
  const mk = (cls, html) => { const d = document.createElement('div'); d.className = cls; d.innerHTML = html; return d; };
  g.appendChild(mk('h', ''));
  for (let j = 0; j < N; j++) g.appendChild(mk('h', fmt('Store %j%%v%', { j: j, v: 1 })));
  g.appendChild(mk('h', 'Supply'));
  for (let i = 0; i < M; i++) {
    g.appendChild(mk('lab', fmt('Warehouse %i%%v%', { i: i, v: 1 })));
    for (let j = 0; j < N; j++) {
      const cell = document.createElement('div'); cell.className = 'cell';
      const inp = document.createElement('input');
      inp.type = 'number'; inp.min = '0'; inp.value = cost[i][j];
      inp.addEventListener('change', () => { cost[i][j] = Math.max(0, parseInt(inp.value) || 0); inp.value = cost[i][j]; clear(); });
      const ship = document.createElement('div'); ship.className = 'ship empty'; ship.id = 's' + i + j;
      cell.appendChild(inp); cell.appendChild(ship); g.appendChild(cell);
    }
    const sd = document.createElement('div'); sd.className = 'sd';
    const si = document.createElement('input'); si.type = 'number'; si.min = '0'; si.value = supply[i];
    si.addEventListener('change', () => { supply[i] = Math.max(0, parseInt(si.value) || 0); rebalance(); });
    sd.appendChild(si); g.appendChild(sd);
  }
  g.appendChild(mk('lab', 'Demand'));
  for (let j = 0; j < N; j++) {
    const sd = document.createElement('div'); sd.className = 'sd';
    const di = document.createElement('input'); di.type = 'number'; di.min = '0'; di.value = demand[j];
    di.addEventListener('change', () => { demand[j] = Math.max(0, parseInt(di.value) || 0); rebalance(); });
    sd.appendChild(di); g.appendChild(sd);
  }
  g.appendChild(mk('h', ''));
}

// Keep total supply == total demand by nudging the last demand cell.
function rebalance() {
  const ts = supply.reduce((a, b) => a + b, 0);
  let td = demand.reduce((a, b) => a + b, 0);
  const diff = ts - td;
  demand[N - 1] = Math.max(0, demand[N - 1] + diff);
  buildGrid(); clear();
}
function clear() {
  for (let i = 0; i < M; i++) for (let j = 0; j < N; j++) {
    const s = document.getElementById('s' + i + j); s.textContent = ''; s.className = 'ship empty';
  }
  const st = document.getElementById('status');
  st.textContent = 'Edit the numbers, then Solve.';
}
function run() {
  const { plan, cost: c } = solve();
  if (!plan) { document.getElementById('status').textContent = 'Supply and demand do not match.'; return; }
  for (let i = 0; i < M; i++) for (let j = 0; j < N; j++) {
    const s = document.getElementById('s' + i + j);
    s.textContent = plan[i][j] > 0 ? (fmt('ship %v%', { v: plan[i][j] })) : '·';
    s.className = plan[i][j] > 0 ? 'ship' : 'ship empty';
  }
  document.getElementById('status').textContent = fmt('Minimum total cost: %c%', { c: c });
  console.log('Optimal plan:', JSON.stringify(plan), '| cost', c);
}
function randomize() {
  for (let i = 0; i < M; i++) for (let j = 0; j < N; j++) cost[i][j] = 1 + Math.floor(Math.random() * 9);
  buildGrid(); clear();
}
document.getElementById('solve').addEventListener('click', run);
document.getElementById('rand').addEventListener('click', randomize);
buildGrid();
Result
Console

Notice what happens. The space of possible plans is enormous, yet the optimal one snaps into place instantly. That is because the transportation problem is a linear program with a special network structure — and structure like this is exactly what makes a problem tractable instead of a brute-force nightmare. (Total supply must equal total demand; the demo balances it for you.)

The Real Complexity

How hard is the transportation problem, really?

  • Status: solved, efficiently. It is a special case of linear programming, which George Dantzig made practical with the simplex method in 1947 and which Leonid Khachiyan proved solvable in polynomial time in 1979.
  • The network simplex. Because the problem lives on a bipartite network of sources and sinks, a tailored version called the network simplex runs far faster than general LP and is the standard engine in practice.
  • Integers for free. The constraint matrix of a transportation problem is totally unimodular. A consequence: whenever supplies and demands are whole numbers, an optimal solution with whole-number shipments is guaranteed — no rounding, no separate integer-programming search.
  • A sibling of flow. The transportation problem is exactly a minimum-cost flow problem on a two-layer network, so the same polynomial-time machinery applies.

That is the punchline: a problem with astronomically many candidate plans is genuinely easy. It belongs to P — there is no combinatorial explosion to fear, which is the opposite of the situation in P vs NP for problems like the traveling salesman.

Where It Matters

"Move stuff from where it is to where it's needed, cheaply" is one of the most universal problems in industry — and the transportation problem is its mathematical heart:

  • Logistics and supply chains: routing freight from plants to distribution centers to retailers is the textbook application.
  • Power and water networks: matching generation to demand across a grid is the same balancing act.
  • The assignment problem: matching workers to jobs is a transportation problem where every supply and demand equals one — see the assignment problem.
  • Machine learning: the earth mover's distance (optimal transport) compares two distributions by solving a transportation problem, and now underpins everything from image retrieval to generative models.

Understand the transportation problem and you've met optimal transport and minimum-cost flow — a family of efficiently solvable problems that quietly moves the physical and digital world.

Conclusion

The transportation problem looks like it should be hard. There are exponentially many ways to route crates from warehouses to stores, and intuition screams "try them all." But its network structure and total unimodularity make it a tame linear program: the network simplex finds the provably cheapest plan in polynomial time, and the answer comes out in whole crates with no extra work.

So the next time a delivery arrives, remember that somewhere a tiny linear program decided its journey — and that not every problem with a giant search space is doomed to be slow. Some of them, like this one, sit comfortably in P, far from the cliff edge of P vs NP.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/transportation-problem/Content licensed under CC BY-NC 4.0.