2.4 Transportation and Assignment Problems

Transportation Problems as Linear Programming

Special Cases of Linear Programming

Transportation and assignment problems are specific types of linear programming problems, but they have a structure that makes them much easier to solve than general LP problems.

Both problem types can be represented as bipartite networks, where decision variables correspond to arcs connecting two sets of nodes (like sources and destinations). Their constraint matrices have a property called total unimodularity, which guarantees that the optimal solution will always have integer values when you solve with LP methods. That's a big deal because it means you don't need to worry about rounding or using integer programming techniques.

You could solve these with the standard simplex method, but specialized algorithms are faster:

• Transportation simplex method for transportation problems
• Hungarian method for assignment problems

These algorithms exploit the special structure to reach optimal solutions with far less computation.

Transportation Problem Characteristics

Transportation problems involve distributing goods from multiple supply points (like warehouses or factories) to multiple demand points (like retail stores or distribution centers), while minimizing total shipping cost.

The key components are:

• Supply points with known capacities (how much each source can ship)
• Demand points with known requirements (how much each destination needs)
• Unit transportation costs between every supply-demand pair
• Decision variables representing the quantity shipped along each route

The objective function minimizes total cost across all routes. Constraints ensure no supply point ships more than it has, and every demand point receives at least what it needs.

Real-world applications include shipping products from factories to distribution centers, routing agricultural goods from farms to markets, and allocating inventory across a retail network.

Assignment Problem Characteristics

Assignment problems deal with matching a set of agents (employees, machines, etc.) to a set of tasks (jobs, projects, etc.) in a one-to-one pairing that minimizes total cost or maximizes total efficiency.

The problem is defined by a cost or efficiency matrix, where each entry represents the cost (or benefit) of assigning a specific agent to a specific task. Unlike transportation problems, the decision variables here are binary: each $x_{ij}$ is either 0 or 1, indicating whether agent $i$ is assigned to task $j$.

Constraints enforce the one-to-one matching: each agent gets exactly one task, and each task gets exactly one agent.

Common examples include assigning workers to jobs, matching students to dormitory rooms, and scheduling machines to production runs.

Formulating Transportation Problems

Key Components and Parameters

Before you can solve a transportation problem, you need to identify these elements:

• Supply points (sources of goods): factories, warehouses, farms, etc.
• Demand points (destinations): retail stores, distribution centers, dealerships, etc.
• Transportation cost $c_{ij}$: the cost per unit shipped from supply point $i$ to demand point $j$
• Supply capacity $s_i$: the maximum amount available at each supply point
• Demand requirement $d_j$: the minimum amount needed at each demand point
• Decision variables $x_{ij}$: the quantity shipped from supply point $i$ to demand point $j$

For example, if you have 3 automobile factories shipping to 4 dealerships, you'd have 12 decision variables (one for each factory-dealership pair), 3 supply constraints, and 4 demand constraints.

Objective Function and Constraints

The objective function minimizes total shipping cost across all routes:

$\min \sum_{i=1}^{m} \sum_{j=1}^{n} c_{ij}x_{ij}$

where $c_{ij}$ is the unit cost from supply point $i$ to demand point $j$.

Supply constraints prevent shipping more than what's available:

$\sum_{j=1}^{n} x_{ij} \leq s_i \quad \text{for all } i$

Demand constraints ensure each destination receives enough:

$\sum_{i=1}^{m} x_{ij} \geq d_j \quad \text{for all } j$

Non-negativity constraints keep shipments feasible:

$x_{ij} \geq 0 \quad \text{for all } i \text{ and } j$

Balanced vs. Unbalanced Problems

A balanced transportation problem has total supply exactly equal to total demand:

$\sum_{i=1}^{m} s_i = \sum_{j=1}^{n} d_j$

When balanced, supply constraints become equalities and demand constraints become equalities, which simplifies the solution process.

Unbalanced problems occur when supply and demand don't match. You fix this by adding dummy nodes:

• Excess supply: Add a dummy demand point with demand equal to the surplus. Set its transportation costs to zero (the excess just stays at the source).
• Excess demand: Add a dummy supply point with supply equal to the shortage. Set its transportation costs to a high value (representing unmet demand penalties), or to zero if you simply want to identify which demand goes unfilled.

Unbalanced situations arise from things like seasonal demand fluctuations, production delays, or capacity changes.

Solving Transportation Problems

Initial Basic Feasible Solutions

The transportation simplex method needs a starting solution. Three common methods generate one:

1. Northwest Corner Rule

   • Start at the top-left cell of the transportation tableau.
   • Allocate as much as possible to that cell (the minimum of remaining supply and demand).
   • Move right if the supply point is exhausted, or down if the demand point is satisfied.
   • Repeat until all supply and demand are allocated.
   • This method is simple but ignores costs, so the starting solution is usually far from optimal.

2. Least Cost Method

   • Find the cell with the lowest unit transportation cost in the entire tableau.
   • Allocate as much as possible to that cell.
   • Eliminate the satisfied row or column, then find the next lowest cost cell.
   • Repeat until all allocations are made.
   • This typically gives a better starting solution than the Northwest Corner Rule.

3. Vogel's Approximation Method (VAM)

   • For each row and column, calculate a penalty: the difference between the two lowest costs in that row or column.
   • Select the row or column with the highest penalty.
   • Allocate as much as possible to the lowest-cost cell in that row or column.
   • Recalculate penalties and repeat.
   • VAM usually produces the best initial solution of the three methods and often comes close to the optimal.

Transportation Simplex Method

This is a streamlined version of the simplex method designed specifically for transportation problems.

1. Start with an initial basic feasible solution (from one of the methods above).

2. Calculate opportunity costs for all non-basic (empty) cells using dual variables $u_i$ and $v_j$, where $u_i + v_j = c_{ij}$ for each basic cell.

3. Evaluate non-basic cells: compute $c_{ij} - u_i - v_j$ for each empty cell. A negative value means shipping along that route would reduce total cost.

4. Select the entering variable: choose the non-basic cell with the most negative opportunity cost.

5. Trace a stepping stone path: find a closed loop starting and ending at the entering cell, turning only at basic cells, alternating between adding and subtracting shipments.

6. Determine the leaving variable: the basic cell in the loop where you subtract, with the smallest current allocation, leaves the basis.

7. Update allocations along the loop and repeat from step 2.

8. Stop when all opportunity costs for non-basic cells are non-negative. The current solution is optimal.

Degeneracy and Special Cases

Degeneracy occurs when the number of basic (positive) allocations is less than $m + n - 1$ (where $m$ = supply points, $n$ = demand points). A basic feasible solution must have exactly $m + n - 1$ basic variables for the transportation simplex to work.

For example, with 3 supply points and 3 demand points, you need $3 + 3 - 1 = 5$ basic variables. If you only have 4 positive allocations, the solution is degenerate.

To resolve degeneracy:

• Perturbation (epsilon method): Assign a tiny value $\varepsilon$ to one or more empty cells to bring the count of basic variables up to $m + n - 1$. This allows the algorithm to proceed without cycling.
• Place $\varepsilon$ in a cell that doesn't create a closed loop with existing basic cells.

Other special cases:

• Prohibited routes: If certain supply-demand routes can't be used, assign a very large cost ($M$) to those cells. The algorithm will avoid them.
• Fixed shipments: If a specific quantity must ship along a certain route, pre-assign it and adjust the remaining supply and demand before solving.

Formulating Assignment Problems

Cost or Efficiency Matrices

The assignment problem is defined by a square matrix. For a cost matrix $C = [c_{ij}]$, each entry $c_{ij}$ represents the cost of assigning agent $i$ to task $j$. For an efficiency matrix $E = [e_{ij}]$, each entry represents the benefit of that pairing.

The matrix is $n \times n$ for balanced problems (equal numbers of agents and tasks).

Example cost matrix for assigning 3 workers to 3 jobs:

$\begin{bmatrix} 10 & 12 & 19 \\ 5 & 10 & 7 \\ 12 & 14 & 13 \end{bmatrix}$

Here, assigning Worker 1 to Job 1 costs 10, Worker 1 to Job 2 costs 12, and so on. The goal is to find the one-to-one assignment that minimizes total cost.

Objective Function and Constraints

For minimization:

$\min \sum_{i=1}^{n} \sum_{j=1}^{n} c_{ij}x_{ij}$

For maximization:

$\max \sum_{i=1}^{n} \sum_{j=1}^{n} e_{ij}x_{ij}$

The constraints enforce one-to-one matching:

• Each agent is assigned to exactly one task: $\sum_{j=1}^{n} x_{ij} = 1$ for all $i$
• Each task is assigned to exactly one agent: $\sum_{i=1}^{n} x_{ij} = 1$ for all $j$

Decision variables are binary: $x_{ij} \in \{0, 1\}$, where $x_{ij} = 1$ means agent $i$ is assigned to task $j$.

Because of total unimodularity, you can relax the binary constraint to $x_{ij} \geq 0$ and still get integer solutions from LP methods.

Unbalanced Problems and Special Cases

When the number of agents and tasks differ, you need to balance the matrix:

• More tasks than agents (e.g., 3 workers, 4 jobs): Add a dummy agent (row) with high costs for all tasks. Any task assigned to the dummy worker goes unassigned in practice.
• More agents than tasks (e.g., 5 machines, 3 tasks): Add dummy tasks (columns) with zero costs. Agents assigned to dummy tasks simply have no work.

Other special cases:

• Forbidden assignments: Set $c_{ij} = M$ (a very large number) for any agent-task pair that's not allowed. The algorithm will avoid these.
• Forced assignments: Pre-assign the required pair, remove that agent and task from the matrix, and solve the reduced problem.

Solving Assignment Problems with the Hungarian Method

Algorithm Overview and Steps

The Hungarian method (also called the Kuhn-Munkres algorithm) solves assignment problems in $O(n^3)$ time. Here's the full procedure:

1. Row reduction: Subtract the smallest value in each row from every element in that row. This creates at least one zero per row.
2. Column reduction: Subtract the smallest value in each column from every element in that column. This creates at least one zero per column.
3. Cover all zeros using the minimum number of horizontal and vertical lines.
4. Test for optimality: If the number of covering lines equals $n$ (the matrix dimension), an optimal assignment exists among the zeros. Stop here.
5. Create additional zeros: If fewer than $n$ lines are needed, find the smallest uncovered element, subtract it from all uncovered elements, and add it to elements at the intersection of two covering lines. Leave singly-covered elements unchanged.
6. Repeat steps 3-5 until the number of lines equals $n$.
7. Read the optimal assignment from the zero positions.

Matrix Reduction and Augmentation

Here's a worked example with a $3 \times 3$ cost matrix:

Initial matrix:

$\begin{bmatrix} 3 & 2 & 3 \\ 4 & 3 & 1 \\ 1 & 1 & 2 \end{bmatrix}$

Step 1 - Row reduction (subtract row minimums: 2, 1, 1):

$\begin{bmatrix} 1 & 0 & 1 \\ 3 & 2 & 0 \\ 0 & 0 & 1 \end{bmatrix}$

Step 2 - Column reduction (column minimums are 0, 0, 0, so no change):

$\begin{bmatrix} 1 & 0 & 1 \\ 3 & 2 & 0 \\ 0 & 0 & 1 \end{bmatrix}$

Step 3 - Cover zeros with minimum lines. You can cover all zeros with 2 lines (row 3 and column 2). Since 2 < 3, the solution isn't optimal yet.

Step 5 - Create additional zeros. The smallest uncovered element is 1. Subtract 1 from uncovered elements, add 1 to doubly-covered elements:

$\begin{bmatrix} 1 & 0 & 1 \\ 2 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix}$

Wait: let's recheck. With lines on row 3 and column 2, the uncovered elements are: (1,1)=1, (1,3)=1, (2,1)=3, (2,3)=0. The smallest uncovered value is 0, which means we need different covering lines. Actually, covering with row 3 and column 2 leaves (2,3)=0 uncovered, so that's not a valid minimum cover. The correct minimum cover uses 3 lines (for instance, row 1, row 3, and column 3), meaning all zeros are covered with $n = 3$ lines. The assignment is already optimal.

The optimal assignment from the zeros: Agent 1 → Task 2 (cost 2), Agent 2 → Task 3 (cost 1), Agent 3 → Task 1 (cost 1). Total cost = 4.

Optimality and Special Cases

Optimality is confirmed when the minimum number of lines covering all zeros equals $n$.

Maximization problems: Convert to minimization by subtracting every element from the largest element in the matrix. For example, with efficiency matrix:

$\begin{bmatrix} 7 & 5 & 9 \\ 4 & 3 & 8 \\ 3 & 8 & 6 \end{bmatrix}$

The largest element is 9. Subtract each element from 9 to get the equivalent cost matrix:

$\begin{bmatrix} 2 & 4 & 0 \\ 5 & 6 & 1 \\ 6 & 1 & 3 \end{bmatrix}$

Then apply the Hungarian method as usual.

Other special cases:

• Rectangular problems (unequal agents and tasks): Add dummy rows or columns with appropriate costs to make the matrix square, then solve normally.
• Forbidden assignments: Set those cells to a very large value $M$ so they're never selected.
• Sensitivity analysis: After finding the optimal solution, you can examine how much a cost coefficient would need to change before the optimal assignment shifts. This helps assess how robust your solution is to cost uncertainty.