Transportation and Assignment Problems

Motivation

Bananas are stored at warehouses and shipped to grocery stores. Each warehouse has a supply, each store has a demand, and each warehouse–store pair has a per-unit shipping cost.

The transportation problem asks for shipment amounts that meet all store demands, do not ship more than the available supply at any warehouse, and minimize total shipping cost.

Note on the chapter example. The TeX source contains an early table with demand d₃=8, but the subsequent feasible shipment, total-demand calculation, and algorithm use d=(3,5,7). This webpage uses d=(3,5,7), the internally consistent value in the rest of the chapter.

Chapter example

	Supply	Store 1 d=3	Store 2 d=5	Store 3 d=7
Warehouse 1	7	8	3	2
Warehouse 2	8	1	4	5
Warehouse 3	3	8	6	7

The entries inside the store columns are the costs c_ij.

Mathematical model

Transportation problem

Input. Warehouses i=1,…,m, stores j=1,…,n, supplies s_i≥0, demands d_j≥0, and costs c_ij≥0.

Output. Shipment amounts x_ij≥0 satisfying

∑_j=1ⁿ x_ij ≤ s_i for each warehouse i, ∑_i=1^m x_ij ≥ d_j for each store j.

Goal. Minimize total shipping cost

∑_i=1^m∑_j=1ⁿ c_ijx_ij.

Why demands can be met exactly

When all shipping costs are nonnegative, an optimal solution never needs to ship extra goods to a real store. If a store receives more than its demand, reducing some positive shipment into that store preserves feasibility and weakly decreases cost.

So for the cost-shift argument below, it is enough to focus on feasible solutions where each real store receives exactly its demand.

A feasible but nonoptimal shipment

	Store 1	Store 2	Store 3
Warehouse 1	0	6	0
Warehouse 2	0	0	7
Warehouse 3	3	0	0

This shipment has cost 3·6 + 5·7 + 8·3 = 77. Lowering x₁₂ from 6 to 5 still meets demand at store 2 and lowers the cost by 3.

Cost shifts that preserve optimal solutions

If every cost in one store column j is changed by the same amount Δ, then every potentially optimal feasible solution changes by the same total amount d_jΔ. The ranking of feasible solutions is unchanged.

To also change whole warehouse rows safely, the input is made balanced. If total supply is larger than total real demand, add a dummy store with demand equal to the excess supply and cost 0 from every warehouse. Shipping to this dummy store means “not shipped to a real store.”

d_dummy = ∑_is_i − ∑_jd_j.

After balancing, every feasible solution ships all supply somewhere, so changing every cost in warehouse row i by Δ changes every feasible solution by the same total amount s_iΔ.

Column reductions in the example

Subtract the minimum in each real store column: 1 from column 1, 3 from column 2, and 2 from column 3.

	Store 1	Store 2	Store 3
Warehouse 1	7	0	0
Warehouse 2	0	1	3
Warehouse 3	7	3	5

The dummy demand is 3 because total supply is 18 and total real demand is 15.

Testing for a zero-cost shipment with max flow

Given a balanced reduced-cost matrix, create a max-flow instance:

Add a source, a node for each warehouse, a node for each store, and a sink.
Add an arc from the source to warehouse i with capacity s_i.
Add an arc from store j to the sink with capacity d_j.
Add an infinite-capacity arc from warehouse i to store j only when the current reduced cost c_ij is 0.

Transportation algorithm

Balance the input by adding a dummy store if necessary.
Solve the zero-cost max-flow instance.
If the flow value equals total demand, the positive warehouse-to-store flows give an optimal transportation solution.
If not, use the residual reachable set S as a minimum cut. Let S_W be warehouses in S and S_D be stores in S. Set Δ = min{c_ij : i∈S_W, j∉S_D}.
Decrease every row in S_W by Δ, increase every column in S_D by Δ, and repeat.

Interactive transportation workbench

Edit the instance, initialize the balanced reduced-cost matrix, then step through the repeated max-flow and cost-update phases. The default data is the chapter example.

Input data

Warehouses

Stores

Do the chapter-style initial column reductions before the max-flow loop.

Reduced costs and zero-cost flow network

Algorithm state

Shipment / certificate

Step log

Special case: the assignment problem

When there are n workers and n jobs, with s_i=1 and d_j=1 for all i,j, the transportation problem becomes the assignment problem. A shipment of one unit from worker i to job j means assigning that worker to that job.

The max-flow subproblem is now a bipartite matching problem on the zero entries of the cost matrix. A minimum cut becomes a collection of rows and columns that covers every zero. The hand algorithm is the Hungarian method.

Chapter assignment example

8	10	7
10	11	8
5	6	7

Rows are workers, columns are jobs. The optimal assignment has cost 22.

Assignment algorithm

Subtract the minimum entry in each row from every entry in that row.
Subtract the minimum entry in each column from every entry in that column.
Look for a zero-cost assignment. Equivalently, find a matching using only zero entries.
If no perfect zero matching exists, cover all zeros with as few rows and columns as possible.
Let Δ be the smallest uncovered entry. Subtract Δ from uncovered entries and add Δ to entries covered twice. Repeat.

Interactive assignment workbench

Edit the worker-job cost matrix and step through row reduction, column reduction, zero matching, zero cover, and matrix update.

Input matrix

Size

Current reduced matrix

Assignment state

Assignment

Step log

What the interactives certify

Feasibility

Shipments satisfy warehouse supplies and store demands. After balancing, every unit of supply is shipped either to a real store or to the dummy store.

Lower bound

The algorithm keeps all reduced costs nonnegative. A zero-cost solution in the reduced matrix therefore has the smallest possible reduced cost.

Original optimality

Every row or column cost shift changes all feasible balanced solutions by the same constant. So an optimum for the final reduced costs is also an optimum for the original costs.