Transportation Problem

Work in progress. This note is still being written and incomplete.

Minimizes the cost of shipping a single commodity from mm supply points to nn demand points, given a per-unit shipping cost cijc_{ij} for every supply-demand pair.

minimize z=i=1mj=1ncijxij\text{minimize } z = \sum_{i=1}^{m} \sum_{j=1}^{n} c_{ij} x_{ij}

Subject to:

  • j=1nxijai\sum_{j=1}^{n} x_{ij} \le a_i for every supply point ii (supply capacity)
  • i=1mxijbj\sum_{i=1}^{m} x_{ij} \ge b_j for every demand point jj (demand requirement)
  • xij0x_{ij} \ge 0

Variations

Balanced

Total supply equals total demand: iai=jbj\sum_i a_i = \sum_j b_j. Every constraint becomes an equality.

A feasible solution exists iff the problem is balanced.

A balanced transportation problem with mm supply and nn demand points has m+n1m + n - 1 basic variables in any basic feasible solution (BFS).

Unbalanced

Total supply and demand differ. Add a dummy supply point (if demand exceeds supply) or a dummy demand point (if supply exceeds demand) with 0 shipping cost, absorbing the excess, to rebalance it.

Maximization

Convert to an equivalent minimization problem by negating every cost cijc_{ij} (or subtracting each from the largest cost in the matrix), then solve as usual.

Restricted

A route is prohibited (e.g. no road between a supply and demand point). Assign it a very large cost MM, which drives xijx_{ij} to 0 in any optimal solution.

Transportation Table

A transportation table lays out a transportation problem as a grid: one row per supply point, one column per demand point.

Conventions:

  • Cell (i,j)(i,j) carries the shipping cost cijc_{ij} and the allocation xijx_{ij}.
  • The rightmost column holds each row’s supply aia_i.
  • The bottom row holds each column’s demand bjb_j.
  • A cell is occupied when xij>0x_{ij} > 0, unoccupied otherwise.

Example, unsolved (only the costs, supply, and demand are known):

D1D_1D2D_2D3D_3 Supply
O1O_1 4 6 8 20
O2O_2 3 5 2 70
O3O_3 3 9 6 25
Demand 30 25 20

Total supply is 115115, total demand is 7575: unbalanced.

Loop

A closed path of occupied cells (plus a chosen unoccupied cell) that alternates horizontal and vertical moves, turning only at occupied cells, and returns to the unoccupied cell. Exactly one such loop exists for a given unoccupied cell in a non-degenerate BFS.

Degenerate BFS

A BFS is non-degenerate when it has exactly m+n1m+n-1 positive allocations. Every unoccupied cell then has exactly 1 loop, and the stepping stone method computes every improvement index directly.

A BFS is degenerate when an allocation exhausts a row and a column simultaneously before all supply/demand is used, leaving fewer than m+n1m+n-1 positive allocations. Add a 0 allocation to an unoccupied cell (chosen so the solution stays a basic feasible solution) to restore the count. From then on the 0-allocated cell counts as occupied for tracing loops, even though it ships nothing.

Degeneracy can also appear mid-solution: if a stepping stone pivot ties 2 or more - cells at the same minimum allocation, only 1 leaves the basis, but every tied cell drops to 0, again leaving fewer than m+n1m+n-1 positive allocations.

An allocation to a dummy row or column represents unmet demand or unused supply rather than an actual shipment, since its cost is 0. It is still an ordinary basic variable: it counts toward m+n1m+n-1, and it participates in loops like any other occupied cell.

Solving Transportation Method

To construct an initial BFS, there are 2 methods. Only 1 is needed to proceed to the stepping stone method.

Least Cost Method

Step:

  • Allocate as much as possible to the cell with the lowest cost in the matrix.
    A tie in the lowest cost is broken by choosing the cell allowing the larger allocation.
  • Cross out the exhausted row or column.
  • Repeat on the remaining cells until fully allocated.

Vogel’s Approximation Method

Penalty is the difference between the lowest and second-lowest cost in it.

Steps:

  • For every remaining row and column, compute the penalty.
  • Select the row or column with the largest penalty.
    A tie is broken by choosing the row or column whose lowest-cost cell allows the larger allocation. If still tied, choose the one with the lower cost in that cell. If that also ties, choose the lowest-indexed row or column.
  • Allocate as much as possible to its lowest-cost cell in the chosen row or column.
  • Cross out the exhausted row or column and recompute penalties.
  • Repeat until fully allocated.

Generally gives a BFS closer to optimal than the least cost method.

Stepping Stone Method

Improves an initial BFS to optimality.

  • For every unoccupied cell, trace its loop.
  • Alternate ++ and - signs around the loop, starting with ++ at the unoccupied cell.
  • Sum the costs around the loop with their signs. This is the cell’s improvement index.
  • If every improvement index is 0\ge 0, the solution is optimal. Stop.
  • Otherwise, the cell with the most negative improvement index enters the basis.
  • Shift the minimum allocation among - cells in its loop, adding it at ++ cells and subtracting it at - cells.
  • The - cell with the minimum allocation leaves the basis (becomes 0/unoccupied).

Repeat until every improvement index is 0\ge 0.

Worked Example

Solving the table from Transportation Table. Total supply is 115115, total demand is 7575: unbalanced. Add a dummy demand point D4D_4 with demand 4040 and cost 00 to balance it.

D1D_1D2D_2D3D_3D4D_4 Supply
O1O_1 4 6 8 0 20
O2O_2 3 5 2 0 70
O3O_3 3 9 6 0 25
Demand 30 25 20 40

Least cost method proceeds as follows:

1 /

occupied cell 0 allocation this step loop path + cell − cell

Lowest cost is 0, tied across the whole dummy column D4D_4. O2D4O_2 D_4 allows the largest allocation (min(70,40)=40\min(70,40)=40, against O1O_1‘s 20 and O3O_3‘s 25). Allocate 40. D4D_4 exhausted.

Lowest remaining cost is 2 at O2D3O_2 D_3. Allocate min(30,20)=20\min(30,20) = 20. D3D_3 exhausted.

Lowest remaining cost is 3, tied between O2D1O_2 D_1 and O3D1O_3 D_1. O3D1O_3 D_1 allows the larger allocation (min(25,30)=25\min(25,30)=25 against min(10,30)=10\min(10,30)=10). Allocate 25. O3O_3 exhausted.

Lowest remaining cost is 3 at O2D1O_2 D_1. Allocate min(10,5)=5\min(10,5) = 5. D1D_1 exhausted.

Lowest remaining cost is 5 at O2D2O_2 D_2. Allocate min(5,25)=5\min(5,25) = 5. O2O_2 exhausted.

z=275z = 275

Only O1D2O_1 D_2 remains. Allocate the remaining 20. 6 basic variables equals m+n1m+n-1, non-degenerate.

Vogel’s approximation method proceeds as follows:

1 /

occupied cell 0 allocation this step loop path + cell − cell

Row penalties are O1=4O_1 = 4, O2=2O_2 = 2, O3=3O_3 = 3. Column penalties are D1=0D_1 = 0, D2=1D_2 = 1, D3=4D_3 = 4, D4=0D_4 = 0. O1O_1 and D3D_3 tie at 4. O1O_1‘s lowest-cost cell (O1D4O_1 D_4, cost 0) allows min(20,40)=20\min(20,40)=20; D3D_3‘s (O2D3O_2 D_3, cost 2) also allows min(70,20)=20\min(70,20)=20, so the lower cost wins: O1O_1.

Allocate 20 to O1D4O_1 D_4. O1O_1 exhausted.

Row penalties are O2=2O_2 = 2, O3=3O_3 = 3. Column penalties are D1=0D_1 = 0, D2=4D_2 = 4, D3=4D_3 = 4, D4=0D_4 = 0. D2D_2 and D3D_3 tie at 4. D2D_2‘s lowest-cost cell (O2D2O_2 D_2) allows min(70,25)=25\min(70,25)=25, more than D3D_3‘s min(70,20)=20\min(70,20)=20.

Allocate 25 to O2D2O_2 D_2. D2D_2 exhausted.

Row penalties are O2=2O_2 = 2, O3=3O_3 = 3. Column penalties are D1=0D_1 = 0, D3=4D_3 = 4, D4=0D_4 = 0. Largest is D3D_3 (4), whose lowest cost is O2D3O_2 D_3 (2).

Allocate 20 to O2D3O_2 D_3. D3D_3 exhausted.

Row penalties are O2=3O_2 = 3, O3=3O_3 = 3. Column penalties are D1=0D_1 = 0, D4=0D_4 = 0. O2O_2 and O3O_3 tie at 3, and both offer min(25,20)=20\min(25,20)=20 at cost 0 in D4D_4: tied on every rule, so the lowest-indexed row wins, O2O_2.

Allocate 20 to O2D4O_2 D_4. D4D_4 exhausted.

Only D1D_1 remains, so no penalty is needed. Allocate O2D1=5O_2 D_1 = 5. O2O_2 exhausted.

z=255z = 255

Allocate O3D1=25O_3 D_1 = 25. 6 basic variables equals m+n1m+n-1, non-degenerate.

Applying the stepping stone method to the least cost method’s BFS above (occupied cells O1D2O_1 D_2, O2D1O_2 D_1, O2D2O_2 D_2, O2D3O_2 D_3, O2D4O_2 D_4, O3D1O_3 D_1). Each step below traces the loop for one unoccupied cell, with ++ and - marking the alternating signs around it.

1 /

occupied cell 0 allocation this step loop path + cell − cell

z=275z = 275

Starting from the least cost method’s BFS. Trace the loop of every unoccupied cell to find its improvement index.

z=275z = 275

Loop O1D1(+),O2D1(),O2D2(+),O1D2()O_1 D_1(+), O_2 D_1(-), O_2 D_2(+), O_1 D_2(-). Improvement index 43+56=04 - 3 + 5 - 6 = 0.

z=275z = 275

Loop O1D3(+),O1D2(),O2D2(+),O2D3()O_1 D_3(+), O_1 D_2(-), O_2 D_2(+), O_2 D_3(-). Improvement index 86+52=58 - 6 + 5 - 2 = 5.

z=275z = 275

Loop O1D4(+),O1D2(),O2D2(+),O2D4()O_1 D_4(+), O_1 D_2(-), O_2 D_2(+), O_2 D_4(-). Improvement index 06+50=10 - 6 + 5 - 0 = -1: the most negative so far.

z=275z = 275

Loop O3D2(+),O3D1(),O2D1(+),O2D2()O_3 D_2(+), O_3 D_1(-), O_2 D_1(+), O_2 D_2(-). Improvement index 93+35=49 - 3 + 3 - 5 = 4.

z=275z = 275

Loop O3D3(+),O3D1(),O2D1(+),O2D3()O_3 D_3(+), O_3 D_1(-), O_2 D_1(+), O_2 D_3(-). Improvement index 63+32=46 - 3 + 3 - 2 = 4.

z=275z = 275

Loop O3D4(+),O3D1(),O2D1(+),O2D4()O_3 D_4(+), O_3 D_1(-), O_2 D_1(+), O_2 D_4(-). Improvement index 03+30=00 - 3 + 3 - 0 = 0. Every unoccupied cell is checked: O1D4O_1 D_4‘s 1-1 is the most negative, so it enters the basis.

z=275z = 275

The minimum allocation among the loop’s - cells is 20, at O1D2O_1 D_2. Shift 20 around the loop: add 20 at the ++ cells, subtract 20 at the - cells.

z=255z = 255

O1D2O_1 D_2 leaves the basis (0/unoccupied), O1D4O_1 D_4 enters at 20. New cost z=27520=255z = 275 - 20 = 255.

z=255z = 255

Recomputing: O1D1=1O_1 D_1 = 1, O1D2=1O_1 D_2 = 1, O1D3=6O_1 D_3 = 6, O3D2=4O_3 D_2 = 4, O3D3=4O_3 D_3 = 4, O3D4=0O_3 D_4 = 0. Every improvement index is 0\ge 0: optimal at z=255z = 255. O3D4=0O_3 D_4 = 0 gives an alternate optimal solution.

This matches Vogel’s approximation method’s result exactly, both in allocations and cost: VAM reached the optimum directly, while the least cost method needed 1 stepping stone iteration to get there.

Written by September 13, 2026 8 min read
Was this helpful?