Assignment & Transportation Problems: Models, Solving & Real-World Apps

TAKEAWAYS:

• Assignment problems minimize cost by matching n tasks to n agents using a cost matrix and solved via the Hungarian algorithm (O(n³)).
• Transportation problems distribute goods from m sources to n destinations with supply/demand constraints, solved via northwest corner rule, least-cost method, or MODI.
• Both problems use linear programming under constraints, with duality theory linking primal and dual solutions.
• Real-world uses: Pathao’s driver-task assignment, NTC’s fuel depot routing, and bank loan officer allocation.
• The stepping-stone method and MODI iteratively improve solutions until optimality (no negative cost loops).
• Duality simplifies complex problems: the dual of an assignment problem is a transportation problem, and vice versa.

1. Assignment Problem: Definition and Mathematical Formulation

The assignment problem is a classic optimization problem where we assign n distinct tasks to n distinct agents (e.g., workers, machines, or contractors) such that the total cost is minimized (or profit maximized). This is a special case of the linear programming (LP) problem with constraints ensuring each task is assigned to exactly one agent and vice versa.

Key Components

• Cost Matrix (C): A square matrix where $C_{ij}$ represents the cost of assigning agent j to task i. Example: Assigning 4 contractors to 4 maintenance tasks in Kathmandu City Corporation.

• Decision Variables (x): Binary variables $x_{ij}$ where: $x_{ij}=1$ if agent j is assigned to task i, $x_{ij}=0$ otherwise.

• Objective Function: Minimize total cost: $$\text{Minimize }Z=\sum _{i=1}^n\sum _{j=1}^n{C}_{ij}{x}_{ij}$$

• Constraints:

  1. Each task is assigned to exactly one agent: $$\sum _{j=1}^n{x}_{ij}=1\forall i$$
  2. Each agent is assigned to exactly one task: $$\sum _{i=1}^n{x}_{ij}=1\forall j$$
  3. Binary constraint: $$x_{ij}\in \{0,1\}$$

Visual: Cost Matrix for Kathmandu City Corporation

Assumption: There are 5 contractors but only 4 tasks, so one contractor will be unused.

2. Solving the Assignment Problem: Hungarian Algorithm

The Hungarian algorithm (or Munkres algorithm) is an efficient method to solve assignment problems in O(n³) time. It works by:

1. Subtracting row minima to create at least one zero in each row.
2. Subtracting column minima to create at least one zero in each column.
3. Covering all zeros with the minimum number of lines (rows/columns).
4. Adjusting the matrix if the number of lines < n (using the modification step).
5. Selecting optimal assignments from the zeros.

Worked Example: Kathmandu City Corporation

Given:

• 4 tasks (T1-T4) and 5 contractors (A-E).
• Cost matrix as above (but we ignore contractor E since there are only 4 tasks).

Step 1: Subtract row minima

Step 2: Subtract column minima

Step 3: Cover zeros with minimum lines

• Zeros at (T1,B), (T1,D), (T2,A), (T2,C), (T3,D), (T4,A), (T4,D).
• Minimum lines needed: 2 (e.g., cover rows T1 and T4).
• Since lines < n (4), we proceed to modification step.

Modification Step:

1. Find the smallest uncovered element: 1 (at (T2,B)).
2. Subtract this from all uncovered elements; add to elements covered by two lines.
3. Repeat until optimal assignment is found.

Optimal Assignment:

• T1 → B (cost = 8)
• T2 → A (cost = 7)
• T3 → D (cost = 7)
• T4 → A or D? (Conflict resolved by selecting the lowest cost path.)
• Final assignment:
  • T1 → B (8)
  • T2 → C (5)
  • T3 → D (7)
  • T4 → A (6)
• Total cost = 8 + 5 + 7 + 6 = 26

3. Transportation Problem: Definition and Formulation

The transportation problem involves distributing goods from m sources (factories, warehouses) to n destinations (stores, cities) at minimum cost, subject to supply and demand constraints.

Key Components

• Cost Matrix (C): $C_{ij}$ = cost of transporting 1 unit from source i to destination j.

• Supply (S): $S_i$ = supply capacity of source i.

• Demand (D): $D_j$ = demand requirement of destination j.

• Decision Variables (x): $x_{ij}$ = quantity transported from source i to destination j.

• Objective Function: Minimize total transportation cost: $$\text{Minimize }Z=\sum _{i=1}^m\sum _{j=1}^n{C}_{ij}{x}_{ij}$$

• Constraints:

  1. Supply constraints: $$\sum _{j=1}^n{x}_{ij}\le S_i\forall i$$
  2. Demand constraints: $$\sum _{i=1}^m{x}_{ij}\ge D_j\forall j$$
  3. Non-negativity: $$x_{ij}\ge 0$$

Visual: Transportation Network for NTC Fuel Depots

graph LR
    A["Depot X<br/>Supply: 60"] -->|"12 units"| B["City A<br/>Demand: 65"]
    A -->|"11 units"| C["City B<br/>Demand: 35"]
    A -->|"60 units"| D["City C<br/>Demand: 35"]
    E["Depot Y<br/>Supply: 60"] -->|"7 units"| B
    E -->|"11 units"| C
    E -->|"42 units"| D
    F["Depot Z<br/>Supply: 35"] -->|"2 units"| B
    F -->|"16 units"| C
    F -->|"17 units"| D

4. Solving the Transportation Problem

Three methods are commonly used:

1. Northwest Corner Rule (NWCR): A greedy heuristic (not always optimal).
2. Least-Cost Method (LCM): Prioritizes the cheapest routes first.
3. Modified Distribution (MODI) Method: An iterative LP-based method for optimality.

Worked Example: NTC Fuel Depot Routing

Given:

Step 1: Apply Northwest Corner Rule (Initial Feasible Solution)

1. Start at (X,A): Allocate min(60, 65) = 60.
   • X’s supply exhausted; A’s demand = 65 - 60 = 5.
2. Move to (Y,A): Allocate min(60, 5) = 5.
   • A’s demand exhausted; Y’s supply = 60 - 5 = 55.
3. Move to (Y,B): Allocate min(55, 35) = 35.
   • B’s demand exhausted; Y’s supply = 55 - 35 = 20.
4. Move to (Y,C): Allocate min(20, 35) = 20.
   • Y’s supply exhausted; C’s demand = 35 - 20 = 15.
5. Move to (Z,C): Allocate min(35, 15) = 15.
   • C’s demand exhausted; Z’s supply = 35 - 15 = 20.

Initial Solution:

Step 2: Check Optimality Using MODI Calculate u_i (row potentials) and v_j (column potentials):

1. Set $u_1=0$ (arbitrary).
2. For occupied cells, $u_i+v_j=C_{ij}$:
   • $u_1+v_1=12$ → $v_1=12$
   • $u_2+v_1=7$ → $u_2=-5$
   • $u_2+v_2=11$ → $v_2=16$
   • $u_2+v_3=4$ → $v_3=9$
   • $u_3+v_3=3$ → $u_3=-6$
3. Check unoccupied cells for negative $C_{ij}-(u_i+v_j)$:
   • (X,B): $11-(0+16)=-5$ → Not optimal!

Step 3: Apply Stepping-Stone Method Find a closed loop for (X,B):

• (X,B) → (X,A) → (Y,A) → (Y,B) → (X,B).
• Adjust allocations:
  • $\theta =\min (60,5,35)=5$.
  • New allocations:
    • X,A: 60 - 5 = 55
    • Y,A: 5 + 5 = 10
    • Y,B: 35 - 5 = 30
    • X,B: 0 + 5 = 5

Updated Solution:

Final Cost Calculation: $$Z=(55\times 12)+(5\times 11)+(10\times 7)+(30\times 11)+(20\times 4)+(15\times 3)=660+55+70+330+80+45=1240$$

## In the Real World

1. Pathao’s Driver-Task Assignment:

   • Problem: Assign drivers to ride requests in Kathmandu’s chaotic traffic.
   • Solution: Uses a real-time assignment algorithm (similar to the Hungarian method) to match drivers to passengers based on distance, wait time, and driver availability, minimizing total travel time.
   • Example: If a driver near Thapathali is requested for a ride to Koteshwor, the system calculates the cost matrix (time + fuel) and assigns the cheapest route dynamically.

2. NTC’s Fuel Depot Routing:

   • Problem: Distribute fuel from depots (X, Y, Z) to petrol pumps (A, B, C) with varying demands.
   • Solution: Solves a transportation problem to minimize fuel costs while meeting demand. For example, if Depot X has excess fuel and Pump A is nearby, the algorithm prioritizes routing fuel from X→A at the lowest cost.

3. Bank Loan Officer Allocation (NMB, Global IME):

   • Problem: Assign loan officers to customers based on risk level, processing time, and expertise.
   • Solution: Models this as an assignment problem where the cost matrix represents time + risk penalty. For example, a high-risk loan (longer processing) might be assigned to an experienced officer, reducing default risk.

4. Daraz’s Warehouse-to-Customer Delivery:

   • Problem: Route deliveries from warehouses to customers in Pokhara/Lalitpur efficiently.
   • Solution: Uses transportation problem variants to balance delivery cost, vehicle capacity, and time windows. For example, if Warehouse 1 has 100 units and Customer Zone A needs 80, the system calculates the cheapest truck routes.

5. Duality in Assignment and Transportation Problems

Duality is a fundamental concept in LP where every primal problem has a dual problem. For assignment and transportation problems:

Dual of an Assignment Problem

• Objective: Maximize $W={\sum }_{i=1}^n{\sum }_{j=1}^n{C}_{ij}{y}_{ij}$
• Constraints:
  • ${\sum }_{i=1}^n{y}_{ij}\le 1$ (each agent assigned to at most one task)
  • ${\sum }_{j=1}^n{y}_{ij}\le 1$ (each task assigned to at most one agent)
  • $y_{ij}\ge 0$

Advantages of Duality

1. Simplification: Converting a complex primal problem into a simpler dual.
2. Sensitivity Analysis: Helps understand how changes in costs affect optimal solutions.
3. Computational Efficiency: Some dual problems are easier to solve numerically.

6. Comparison: Assignment vs. Transportation Problems

7. Big M Method for Transportation Problems

When supply ≠ demand, we use the Big M method (a penalty cost approach) to balance the problem:

1. Add a dummy source or dummy destination to balance supply and demand.
2. Assign a large penalty cost (M) to routes involving the dummy.
3. Solve using standard methods (e.g., MODI).

Example: If total supply > total demand, add a dummy destination with demand = supply - total demand, and assign $C_{ij}=M$ (e.g., M = 1000).

8. Kendall’s Notation for Transportation Problems

Kendall’s notation describes transportation problems as: $$m\times n:\sum S_i=\sum D_j\text{or}\sum S_i\ne \sum D_j$$

• Balanced: $m\times n:\sum S_i=\sum D_j$ (e.g., 3×4 balanced).
• Unbalanced: $m\times n:\sum S_i\ne \sum D_j$ (requires dummy rows/columns).

## Exam Tip

1. Memorize the Hungarian Algorithm Steps:

   • Always subtract row minima first, then column minima.
   • Cover zeros with minimum lines; if lines < n, modify the matrix.
   • Optimal assignment is found when the number of lines = n.

2. Transportation Problem Shortcuts:

   • For NWCR/LCM, always start from the northwest corner or least-cost cell.
   • MODI is the most reliable for optimality checks—always verify with u_i and v_j.
   • Stepping-stone method is preferred over Vogel’s approximation in exams (more precise).

3. Duality Tricks:

   • If asked about duality, convert the primal problem to its dual form.
   • For assignment problems, the dual is a transportation problem (and vice versa).

4. Real-World Applications:

   • Pathao/Daraz: Use assignment problems for driver-passenger matching.
   • NTC/Nepal Oil: Use transportation problems for fuel logistics.
   • Banks: Use assignment for loan officer allocation.

5. Common Pitfalls:

   • Ignoring dummy rows/columns in unbalanced problems → incorrect solution.
   • Forgetting to check optimality after initial solution → partial marks lost.
   • Misapplying MODI (e.g., wrong signs for u_i and v_j) → wrong cost calculation.

6. Worked Example Patterns:

   • Assignment: Always show the cost matrix → row/column reduction → optimal assignment.
   • Transportation: Show initial solution (NWCR/LCM) → MODI check → stepping-stone adjustments.