Transportation and Assignment: Method

Transportation Simplex, Transshipment and the Hungarian Algorithm

The transportation problem

m sources hold supplies s_i, n destinations need demands d_j, and shipping one unit from i to j costs c_ij. The problem (Hitchcock 1941) is to choose the shipments x_ij ≥ 0 that meet every demand from the supplies at the least total cost Σ c_ij x_ij. Each row of the table sums to its supply and each column to its demand; because total supply equals total demand, one of these m + n equations is implied by the others, so a basic feasible solution has m + n − 1 basic cells. It is a linear program, and because the constraint matrix is totally unimodular the vertices are integer whenever the supplies and demands are: integer shipments come free. The same table solves many problems that have nothing to do with shipping, such as the production scheduling of Hillier and Lieberman's Northern Airplane example, where the rows are production months, the columns installation months, the costs are production plus storage, and a route backwards in time is forbidden.

Balancing, forbidden routes and maximization

When supply exceeds demand a dummy destination takes the surplus; when demand exceeds supply a dummy source covers the shortfall. Its costs are zero in the textbook treatment, or a penalty per unit unmet (or a storage cost per unit unshipped) when that cost is known; what the plan sends to or from the dummy is simply not shipped. A route that cannot be used gets a cost M so large that no optimal plan uses it while any feasible plan exists; the tool uses M = 1,000 × (largest cost) × (m + n) and shows the cell as M. To maximize a profit the methods are applied to the regret matrix, largest profit minus each entry: the plan of least total regret is the plan of largest total profit, because the two totals differ by the constant (largest profit) × (total shipped).

Starting solutions

The transportation simplex needs a basic feasible solution to start from, and three rules supply one:

• Northwest-corner rule: allocate at the top-left cell as much as its row and column allow, cross out the exhausted line, move right or down, repeat. It never looks at a cost and is usually far from the optimum (165,595 against 152,535 for the P&T Company table), but it is quick and always produces a basis.
• Least-cost method: allocate as much as possible to the cheapest open cell, cross out the exhausted line, repeat.
• Vogel's approximation method (Reinfeld and Vogel 1958): for each open row and column the penalty is the difference between its two cheapest open costs, what every unit not sent by the cheapest cell will cost extra. The line with the largest penalty is served first, at its cheapest cell. The method often lands on the optimum itself (it does for the P&T, Powerco and SunRay examples) and is the usual choice in practice.

When an allocation exhausts a row and a column together, only one of them is crossed out; the other keeps a zero and the next cell allocated to it enters the basis with a zero allocation. That keeps the basis at m + n − 1 cells and is what the textbooks call the ε allocation; the solution is then degenerate.

The transportation simplex (MODI, the u–v method)

The simplex method specialized to this structure (Dantzig 1951) never needs a tableau of the full linear program. With multipliers u_i for the rows and v_j for the columns, the dual constraints read u_i + v_j ≤ c_ij, with equality on the basic cells. Setting u₁ = 0 (the redundant equation leaves one multiplier free) and solving u_i + v_j = c_ij over the basic cells, which form a spanning tree of the rows and columns, gives every multiplier by substitution. The reduced cost of a nonbasic cell is c̄_ij = c_ij − u_i − v_j: the change in total cost per unit shipped through that cell with the basis adjusting around it. If no reduced cost is negative the solution is optimal; otherwise the most negative cell enters.

The stepping-stone loop (Charnes and Cooper 1954) is the unique closed path that starts at the entering cell and moves alternately along a row and a column through basic cells back to the start. Adding θ at the entering cell forces −θ at the next cell of its row, +θ at the next cell of that column, and so on; the signs alternate and every row and column of the loop keeps its total. θ is the smallest allocation among the − cells; that cell drops to zero and leaves the basis, and the cost falls by θ |c̄_ij|. When two − cells tie, one leaves and the other stays in the basis at zero: a degenerate pivot, which changes the basis but not the plan, and may give a zero θ on a later iteration. Winston's Powerco table needs three such pivots from the northwest-corner start (1,180 → 1,120 → 1,070 → 1,020); the P&T table needs two.

Reading the final tableau

• Alternative optima: a nonbasic cell with a reduced cost of exactly zero can enter without changing the cost, so the optimal plan is not unique (Northern Airplane has such a tie).
• Shadow prices: u_i and v_j are the dual values of the row and column constraints. Because the constraints are linearly dependent, they are determined only up to an additive constant; what is meaningful is u_i + v_j, the marginal cost of routing one more unit from i to j through the present basis, and the differences between them. In a balanced problem a single supply or demand cannot change alone (the table would unbalance), so the right-hand-side ranging of ordinary linear programming has no direct meaning here and is not printed.
• Cost ranging: for a nonbasic cell the plan stays optimal while its cost falls by at most its reduced cost; it may rise without limit. For a basic cell, removing it splits the spanning tree in two; a change δ of its cost shifts the multipliers of one part by δ, so the reduced cost of each nonbasic cell that spans the two parts moves by +δ or −δ, and the range is set by the first of them to reach zero. The ranges hold one coefficient at a time.

Transshipment

When goods may pass through intermediate nodes (warehouses, hubs) the problem is a transshipment problem (Orden 1956). It becomes a transportation table by letting every node that can ship be a row and every node that can receive be a column, with a buffer B, the total supply, added to both the supply and the demand of each transshipment node and a zero-cost cell from the node to itself. Units the node does not pass on stay in that cell; B minus that cell is the node's throughput, which can never exceed B. Node pairs without an arc are forbidden cells. The optimal table is read back as arc flows, and a path such as Memphis → New York → Los Angeles appears as a flow into New York and an equal flow out of it. Winston's Widgetco network solves to $6,370 this way, with the direct Denver → Boston route beating the route through Chicago.

The assignment problem and the Hungarian algorithm

Assigning n people to n jobs at the least total cost is the transportation problem with every supply and demand equal to one. Its basic solutions are hugely degenerate (only n of the 2n − 1 basic cells carry a unit), so the transportation simplex is awkward and the Hungarian algorithm (Kuhn 1955, Munkres 1957) is used instead. It rests on two facts: subtracting a constant from an entire row or column adds that constant to every assignment's total and so does not change which assignment is best; and the smallest number of lines (rows and columns) needed to cover all zeros of a matrix equals the largest number of zeros no two of which share a row or column (König's theorem). The steps:

1. Subtract each row's minimum from the row, then each column's minimum from the column; every line now has a zero and no entry is negative.
2. Find the largest set of independent zeros (a maximum matching in the graph of zeros). If it has n cells it is an optimal assignment: its total in the reduced matrix is zero, which is the least any assignment can score when every entry is non-negative, and the original total is the sum of every amount subtracted along the way.
3. Otherwise cover the zeros with that number of lines (the cover of König's theorem: rows not reached from the unmatched rows by alternating paths, plus the columns reached). Let δ be the smallest uncovered entry; subtract δ from every uncovered entry and add δ to every entry covered twice. This is a subtraction of δ from every uncovered row followed by an addition to every covered column, so the optimum is unchanged, and at least one new zero appears. Return to step 2.

A rectangular matrix is squared with dummy rows or columns of zero cost (a row matched to a dummy column receives nothing); a forbidden pairing gets the big cost M; a profit is maximized through the regret matrix. The page prints the matrix after each step with the covering lines, the value of δ, and the chosen zeros of the final matrix in brackets, and says whether a second complete set of zeros exists (alternative optimum). Winston's Machineco times (4 × 4) need one adjustment with δ = 1 and give a total of 15; Hillier and Lieberman's Job Shop table (3 machines, 4 locations, one forbidden cell) gives 29 with a dummy row.

Input formats

• Transportation table: first line the destinations as "Name demand" (also Name = 80 or Name: 80), separated by commas, semicolons, tabs or pipes, with an optional corner label first; each following line a source name, its supply, then one unit cost per destination. M or − marks a forbidden route. A table whose first line is numbers only is read as a plain cost matrix with the supplies and demands typed in the two fields.
• Transshipment network: nodes as "name, type, amount" with type source, transshipment or sink (a transshipment node with its own supply or demand takes "supply 50" or "demand 50"); arcs as "from, to, cost". Unlisted pairs cannot ship directly.
• Assignment matrix: an optional first line of column names, then a row name and its costs; rectangular matrices and M entries are allowed.

Worked examples on the page

The problem select loads the published cases: the P&T Company canneries and warehouses of Hillier and Lieberman (northwest corner 165,595, Vogel 152,535, optimum 152,535), Winston's Powerco plants (optimum $1,020 in three iterations from 1,180), Taha's SunRay Transport silos and mills (520, 475, 475 and the optimum 435 with a degenerate pivot), Hillier and Lieberman's Northern Airplane schedule (a dummy column, forbidden cells, alternative optima at $77.3 million), Winston's Widgetco transshipment ($6,370), and the assignments Machineco (15), Job Shop (29), Joe Klyne's children (27) and Taha's Example 5.4-2 (21). The test script checks the library against these printed values and against an independent simplex solution of each transportation problem and a scipy solution of each assignment.

Limits of the tool

• Up to 15 sources and 15 destinations (after balancing), and 15 × 15 assignment matrices; every tableau is printed, which is the point of the tool, not its speed.
• Supplies, demands and costs are plain numbers in one currency and one unit; no capacities on individual routes (a capacitated problem is a minimum-cost flow problem, which is linear programming territory: see the Linear Programming tool).
• The M of a forbidden cell is a number, so a reduced cost or a multiplier involving it is of that size; they are printed as M where they are meaningless.
• Ties in the entering and leaving cells are broken by position (first in reading order), which is one of the choices the textbooks make; a different tie rule can give a different sequence of tableaus with the same optimum.