The Transportation Problem

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.

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">{{hint}}</p>
<div class="grid" id="grid"></div>
<div class="status" id="status">{{status_initial}}</div>
<div class="btns">
  <button id="solve" type="button">{{btn_solve}}</button>
  <button id="rand" type="button" class="ghost">{{btn_randomize}}</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; }

// Code not found

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

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.

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

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.