The Transportation Problem

Ship goods from factories to warehouses minimizing total transport cost — while satisfying every factory's capacity and every warehouse's demand.

The problem

You have:

Factories (sources) with given supply capacities
Warehouses (sinks) with given demand
A cost matrix: cost per unit shipped from factory i to warehouse j

Decide how many units to ship from each factory to each warehouse to minimize total cost, subject to all supply and demand being satisfied.

The example used in the course

3 factories (capacities 20, 15, 10) and 3 warehouses (demands 5, 20, 20). Total supply = total demand = 45. Costs:

	W1 (5)	W2 (20)	W3 (20)	Capacity
F1	0.9	1.0	1.0	20
F2	1.0	1.4	0.8	15
F3	1.3	1.0	0.8	10

Initial solution: Northwest Corner method

Start at the top-left cell. Assign as much as possible (limited by row capacity and column demand). Cross out whichever (row or column) gets satisfied. Move right or down. Repeat.

Step 1: Cell [1][1] = min(20, 5) = 5
        Column 1 satisfied → remove it.
        Row 1 remaining = 15.
Step 2: Cell [1][2] = min(15, 20) = 15
        Row 1 satisfied → remove it.
        Column 2 remaining = 5.
Step 3: Cell [2][2] = min(15, 5) = 5
        Column 2 satisfied → remove it.
        Row 2 remaining = 10.
Step 4: Cell [2][3] = min(10, 20) = 10
        Row 2 satisfied → remove it.
        Column 3 remaining = 10.
Step 5: Cell [3][3] = min(10, 10) = 10
        Both satisfied → done.

	W1	W2	W3
F1	5 × 0.9	15 × 1.0	—
F2	—	5 × 1.4	10 × 0.8
F3	—	—	10 × 0.8

Cost = 0.9·5 + 1.0·15 + 1.4·5 + 0.8·10 + 0.8·10 = 42.5 $

NW Corner is feasible but ignores costs — usually far from optimal.

Initial solution: Least Cost method

Among all uncovered cells, pick the one with the smallest unit cost. Allocate the max to it. Eliminate the satisfied row or column. Repeat.

Step 1: cheapest cell is [2][3]=0.8 (or [3][3]=0.8 — break ties arbitrarily)
        Allocate min(15, 20) = 15. Row 2 done. W3 remaining = 5.
Step 2: cheapest remaining is [3][3] = 0.8
        Allocate min(10, 5) = 5. Column 3 done. Row 3 remaining = 5.
Step 3: cheapest remaining is [1][1] = 0.9
        Allocate min(20, 5) = 5. Column 1 done. Row 1 remaining = 15.
Step 4: cheapest remaining is [1][2] = 1.0
        Allocate min(15, 20) = 15. Row 1 done. W2 remaining = 5.
Step 5: only [3][2] left.
        Allocate 5. Done.

Cost = 0.9·5 + 1.0·15 + 0.8·15 + 1.0·5 + 0.8·5 = 40.5 $ (better than NW Corner's 42.5)

Improvement: Stepping Stone algorithm

The big idea

You have a feasible allocation. For each empty cell, ask: "if I shipped one unit through here, what closed loop of compensating ± changes would I need to keep the row/column totals correct, and does that loop have a negative net cost?" If yes, route as much through that empty cell as possible.

For each empty cell, you construct a closed path that alternates +1 / −1 around occupied cells. The "stepping stones" are the corners of that path.

Worked example — try cell [1][3]

Starting from NW Corner solution (cost 42.5). Trial: ship 1 unit via [1][3].

Add +1 to [1][3].
Row 1 unbalanced → subtract 1 from [1][2]. Now [1][2] = 14.
Column 2 unbalanced → add 1 to [2][2]. Now [2][2] = 6.
Row 2 unbalanced → subtract 1 from [2][3]. Now [2][3] = 9.

Net cost change = +1.0 +1.4 −1.0 −0.8 = +0.6 $ per unit
This is BAD (adds to cost). Skip this empty cell.

Try cell [3][2]:

+[3][2]  −[3][3]  +[2][3]  −[2][2]
Net = +1.0 −0.8 +0.8 −1.4 = −0.4 $ per unit
NEGATIVE → improving! Route max units through this loop.
The max is limited by the smallest "−" cell in the loop: min(10, 5) = 5.
Allocate 5 units to [3][2]; subtract 5 from [3][3], add 5 to [2][3], subtract 5 from [2][2].

After this move, total cost drops by 0.4 × 5 = 2.0 $. New cost ≈ 40.5 $.

Repeat: check each remaining empty cell. When every empty cell has non-negative change → optimal.

Exam tips

Frequently asked

"Apply NW Corner" — top-left, allocate max, satisfy row or column, move.
"Apply Least Cost" — pick cheapest cell, allocate max, satisfy row or column, repeat.
"Apply Stepping Stone to improve" — for each empty cell, construct the closed loop, compute the net cost change. Negative → reroute. Largest absolute improvement first.
"Is this solution optimal?" — yes if every empty cell has non-negative stepping-stone evaluation.
Watch out for ties — break them either way (just be consistent).