I want to frame this as the classic logistics question I’d face running a supply chain: I have several factories (supply points), each producing a fixed quantity of goods, and several warehouses or retailers (demand points), each requiring a fixed quantity. Shipping a unit from any given factory to any given warehouse has a known cost. How do I decide how much to ship from each factory to each warehouse so that all supply is used, all demand is met, and total shipping cost is minimized? This is the classical Transportation Problem, a foundational special case of linear programming that I find elegant because its structure allows for algorithms far simpler than general-purpose LP solvers.
History and Background
The problem was first formulated by the French mathematician Gaspard Monge in 1781, in the context of earth-moving (minimizing the cost of transporting soil), which is why the more general modern version of this idea is sometimes called the “Monge–Kantorovich transportation problem.” The modern operations-research treatment came from Frank L. Hitchcock, who formalized the problem mathematically in 1941, and independently from Tjalling Koopmans in 1947, whose work on the topic contributed to his later Nobel Memorial Prize in Economic Sciences (1975). George Dantzig then showed in the late 1940s and 1950s how the simplex method could be specialized into efficient transportation-specific algorithms, such as the Stepping Stone Method and the Modified Distribution (MODI) Method, which avoid needing a full general-purpose LP solver.
Problem Statement
I define it as: given $m$ supply sources with available quantities $a_1, \dots, a_m$, $n$ demand destinations with required quantities $b_1, \dots, b_n$ (with total supply equal to total demand, i.e., $\sum a_i = \sum b_j$, the “balanced” case), and a cost matrix $c_{ij}$ representing the cost of shipping one unit from source $i$ to destination $j$, determine the shipment quantities $x_{ij}$ that minimize total cost while fully satisfying every source’s supply and every destination’s demand.
Core Concepts
- Supply and demand: the fixed quantities available at each source and required at each destination.
- Balanced transportation problem: the case where total supply exactly equals total demand — if not, a dummy source or destination with zero cost is added to balance it.
- Basic feasible solution: an initial valid shipment plan satisfying all supply/demand constraints, typically found via methods like the Northwest Corner Rule, Least Cost Method, or Vogel’s Approximation Method.
- Degeneracy: a situation where the number of non-zero (basic) shipment routes is less than $m+n-1$, requiring special handling to keep the optimization algorithm running correctly.
- Optimality test (MODI/u-v method): a way of checking whether a current feasible solution can still be improved, using dual variables associated with each source and destination.
How It Works
- I confirm the problem is balanced (total supply = total demand); if not, I add a dummy row or column with zero shipping costs.
- I find an initial basic feasible solution using a construction heuristic — Vogel’s Approximation Method (VAM) tends to give a good starting point, though the simpler Northwest Corner Rule also works.
- I compute dual variables $u_i$ (for each source) and $v_j$ (for each destination) such that $u_i + v_j = c_{ij}$ for every basic (currently used) route, fixing one variable (commonly $u_1 = 0$) to anchor the system.
- For every non-basic (unused) route, I compute the opportunity cost $\Delta_{ij} = c_{ij} – (u_i + v_j)$.
- If all $\Delta_{ij} \geq 0$, the current solution is optimal, and I stop.
- Otherwise, I select the route with the most negative $\Delta_{ij}$, trace a closed loop through currently basic routes to determine how much flow can be shifted onto it, and update the solution accordingly.
- I repeat steps 3–6 until no negative $\Delta_{ij}$ remains.
Working Principle
The mechanism is a specialized form of the simplex method, exploiting the transportation problem’s particular structure: its constraint matrix is always totally unimodular, which guarantees that basic feasible solutions are automatically integer-valued whenever supplies and demands are integers — I never need to worry about fractional shipments appearing in an otherwise integer problem. The MODI method’s dual-variable trick lets me evaluate whether any unused route could improve the total cost without having to explicitly recompute the entire solution from scratch, which is what makes it so much faster than applying generic simplex machinery directly.
Mathematical Foundation
I formalize the problem as the linear program:
$$ \min \sum_{i=1}^{m} \sum_{j=1}^{n} c_{ij} x_{ij} $$
subject to
$$ \sum_{j=1}^{n} x_{ij} = a_i \quad \forall i, \qquad \sum_{i=1}^{m} x_{ij} = b_j \quad \forall j, \qquad x_{ij} \geq 0 $$
The dual variables satisfy, for every basic variable $x_{ij} > 0$:
$$ u_i + v_j = c_{ij} $$
and the optimality condition for every non-basic route is:
$$ \Delta_{ij} = c_{ij} – u_i – v_j \geq 0 $$
If some $\Delta_{ij} < 0$, I know the solution can still be improved by rerouting flow along a loop that includes that route.
Diagrams
flowchart TD
Start([Start: supply, demand, cost matrix]) --> Balance{Supply = Demand?}
Balance -- No --> Dummy[Add dummy source/destination]
Balance -- Yes --> Initial
Dummy --> Initial[Build initial feasible solution: VAM/Northwest Corner]
Initial --> Dual[Compute dual variables u_i, v_j]
Dual --> Opp[Compute opportunity costs for non-basic routes]
Opp --> OptCheck{All opportunity costs >= 0?}
OptCheck -- Yes --> End([Optimal solution found])
OptCheck -- No --> Loop[Trace closed loop, shift flow, update solution]
Loop --> Dual
Pseudocode
function TransportationProblem(supply[1..m], demand[1..n], cost[1..m][1..n]):
if sum(supply) != sum(demand):
add dummy source or destination with zero cost to balance
x = InitialFeasibleSolution(supply, demand, cost) // e.g., Vogel's Approximation
loop:
(u, v) = ComputeDualVariables(x, cost) // u_i + v_j = cost[i][j] for basic cells
bestDelta = 0
bestCell = none
for each non-basic cell (i, j):
delta = cost[i][j] - (u[i] + v[j])
if delta < bestDelta:
bestDelta = delta
bestCell = (i, j)
if bestCell == none:
return x // optimal
loop_path = FindClosedLoop(x, bestCell)
theta = min shipment among the "minus" corners of loop_path
update x by adding theta along "plus" corners and subtracting along "minus" corners
return x
Step-by-Step Example
Using the diagram above: Source 1 supplies 20, Source 2 supplies 30 (total 50). Destination 1 needs 15, Destination 2 needs 25, Destination 3 needs 10 (total 50) — balanced.
Costs: S1-D1=4, S1-D2=6, S1-D3=9, S2-D1=8, S2-D2=5, S2-D3=3.
Using the Least Cost Method for an initial solution:
- Cheapest cell is S2-D3 (cost 3): ship min(30,10)=10. Remaining: S2=20, D3=0.
- Next cheapest available is S1-D1 (cost 4): ship min(20,15)=15. Remaining: S1=5, D1=0.
- Next cheapest available is S2-D2 (cost 5): ship min(20,25)=20. Remaining: S2=0, D2=5.
- Remaining: S1=5, D2=5, so ship S1-D2: 5.
Initial solution: S1-D1=15, S1-D2=5, S2-D2=20, S2-D3=10. Cost = 15(4) + 5(6) + 20(5) + 10(3) = 60 + 30 + 100 + 30 = 220.
Checking optimality with MODI: setting $u_1=0$, from S1-D1: $v_1 = 4$. From S1-D2: $v_2 = 6$. From S2-D2: $u_2 + 6 = 5 \Rightarrow u_2 = -1$. From S2-D3: $-1 + v_3 = 3 \Rightarrow v_3 = 4$.
Checking non-basic cell S1-D3: $\Delta = 9 – (0+4) = 5 \geq 0$. Checking S2-D1: $\Delta = 8 – (-1+4) = 5 \geq 0$. All opportunity costs are non-negative, so this initial solution is already optimal.
Final optimal cost: 220.
Time Complexity
Finding an initial feasible solution via Vogel’s Approximation Method takes roughly $O(m \cdot n \cdot \min(m,n))$ in a straightforward implementation. Each iteration of the MODI optimality-improvement loop takes $O(mn)$ to compute dual variables and opportunity costs, and $O(m+n)$ to trace a closed loop; the number of iterations needed is typically small in practice but can be bounded by $O(mn)$ in the worst case, giving an overall worst-case complexity around $O(m^2n^2)$, though in practice it converges much faster, similar to how simplex behaves in practice despite worse theoretical worst-case bounds.
Space Complexity
I need $O(mn)$ space to store the cost matrix and the current shipment solution matrix, plus $O(m+n)$ for the dual variable arrays — overall space is $O(mn)$, dominated by the cost and allocation matrices.
Correctness Analysis
Correctness follows from linear programming duality theory: the MODI method is a specialization of the simplex method applied to the transportation problem’s particular constraint structure. The optimality condition — all opportunity costs $\Delta_{ij} \geq 0$ — is exactly the complementary slackness / dual feasibility condition from LP duality theory, which guarantees that once satisfied, the current solution is provably optimal, not merely locally good. The total unimodularity of the transportation constraint matrix additionally guarantees that every basic feasible solution found along the way is integer-valued whenever supplies and demands are integers, so the method never needs separate integer-programming machinery to get whole-unit shipments.
Advantages
- Exploits the special structure of the transportation problem to run much faster than a general-purpose simplex solver.
- Automatically yields integer solutions when supply and demand are integers, thanks to total unimodularity — no rounding needed.
- Well-suited to hand computation for moderately sized problems, making it useful both pedagogically and operationally.
- Extends naturally to related problems like the assignment problem and transshipment problem.
Disadvantages
- Requires the problem to be balanced (or artificially balanced with a dummy row/column), which can obscure the interpretation of “unmet demand” or “unused supply” if not handled carefully.
- Degenerate solutions (fewer than $m+n-1$ basic variables) require special handling to avoid the algorithm stalling or cycling.
- Doesn’t natively handle additional real-world constraints like maximum route capacities or minimum shipment requirements without extension.
- As problem size grows very large, even this specialized method becomes slower than modern general LP solvers using more advanced numerical techniques (interior-point methods).
Applications
- Distribution and logistics network planning, deciding shipment volumes between plants and warehouses.
- Supply chain and inventory positioning across multiple production and consumption sites.
- Public transportation and school-bus routing resource allocation.
- Energy distribution planning, matching power generation sites to demand centers.
- Assignment-style problems (as a special case with all supplies/demands equal to 1), such as task-to-worker matching.
Implementation in C
#include <stdio.h>
#define M 2 // number of sources
#define N 3 // number of destinations
int main() {
int supply[M] = {20, 30};
int demand[N] = {15, 25, 10};
int cost[M][N] = {
{4, 6, 9},
{8, 5, 3}
};
int allocation[M][N] = {0};
int s[M], d[N];
for (int i = 0; i < M; i++) s[i] = supply[i];
for (int j = 0; j < N; j++) d[j] = demand[j];
// Least Cost Method for initial feasible solution
int visited[M][N] = {0};
int totalCost = 0;
for (int step = 0; step < M + N - 1; step++) {
int minCost = 1000000, mi = -1, mj = -1;
for (int i = 0; i < M; i++) {
for (int j = 0; j < N; j++) {
if (!visited[i][j] && s[i] > 0 && d[j] > 0 && cost[i][j] < minCost) {
minCost = cost[i][j];
mi = i;
mj = j;
}
}
}
if (mi == -1) break;
int qty = (s[mi] < d[mj]) ? s[mi] : d[mj];
allocation[mi][mj] = qty;
totalCost += qty * cost[mi][mj];
s[mi] -= qty;
d[mj] -= qty;
if (s[mi] == 0) {
for (int j = 0; j < N; j++) visited[mi][j] = 1;
}
if (d[mj] == 0) {
for (int i = 0; i < M; i++) visited[i][mj] = 1;
}
}
printf("Allocation matrix:\n");
for (int i = 0; i < M; i++) {
for (int j = 0; j < N; j++)
printf("%d\t", allocation[i][j]);
printf("\n");
}
printf("Total transportation cost: %d\n", totalCost);
return 0;
}
Sample Input and Output
Input: the supply, demand, and cost matrix defined above.
Output:
Allocation matrix:
15 5 0
0 20 10
Total transportation cost: 220
This matches my manual walkthrough — the Least Cost Method already produces the optimal solution here, with total cost 220.
Optimization Techniques
- Use Vogel’s Approximation Method instead of the Northwest Corner Rule for the initial solution — it typically starts much closer to optimal, reducing the number of MODI iterations needed.
- Handle degeneracy proactively by adding an infinitesimally small allocation (epsilon) to a cell when the number of basic variables falls short of $m+n-1$, to keep the loop-tracing step well-defined.
- For very large transportation networks, use network simplex implementations that exploit graph-based data structures for faster loop-finding and pivoting.
- Decompose very large problems geographically or by product category when direct dependencies allow, solving smaller sub-problems independently.
Common Mistakes
- Forgetting to balance the problem (adding a dummy source/destination) before applying the algorithm, leading to an infeasible or incorrect setup.
- Miscounting basic variables and not detecting degeneracy, which can cause the loop-tracing step in MODI to fail or behave incorrectly.
- Confusing the transportation problem with the general assignment problem — while related, the assignment problem is a special case with unit supplies/demands and is often solved with the more specialized Hungarian algorithm instead.
- Not verifying total supply equals total demand numerically before running the algorithm, silently producing a nonsensical allocation.
Further Reading
- Hitchcock, F. L. (1941). “The Distribution of a Product from Several Sources to Numerous Localities.” Journal of Mathematics and Physics, 20(1-4), 224–230.
- Koopmans, T. C. (1949). “Optimum Utilization of the Transportation System.” Econometrica, 17, 136–146.
- Dantzig, G. B. (1963). Linear Programming and Extensions, Princeton University Press.
- Taha, H. A. Operations Research: An Introduction, Pearson.
- GeeksforGeeks, Transportation Problem: https://www.geeksforgeeks.org/dsa/transportation-problem-set-1-introduction/
