Transportation Problem

Minimizes the cost of shipping a single commodity from $m$ supply points to $n$ demand points, given a per-unit shipping cost $c_{ij}$ for every supply-demand pair.

Subject to:

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

Variations

Balanced

Total supply equals total demand: $\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 $m$ supply and $n$ demand points has $m + 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 $c_{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 $M$, which drives $x_{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)$ carries the shipping cost $c_{ij}$ and the allocation $x_{ij}$.
• The rightmost column holds each row’s supply $a_i$.
• The bottom row holds each column’s demand $b_j$.
• A cell is occupied when $x_{ij} > 0$, unoccupied otherwise.

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

Total supply is $115$, total demand is $75$: 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+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+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+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+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 $\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 $\ge 0$.

Worked Example

Solving the table from Transportation Table. Total supply is $115$, total demand is $75$: unbalanced. Add a dummy demand point $D_4$ with demand $40$ and cost $0$ to balance it.

Least cost method proceeds as follows:

Vogel’s approximation method proceeds as follows:

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

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.