Transportation & Assignment Problems: Models, Costs & Optimization

TAKEAWAYS:

• Transportation problems minimize costs of shipping goods from sources (factories, warehouses) to destinations (stores, markets) using supply-demand constraints.
• Assignment problems optimize task allocation to agents (e.g., workers, machines) with the lowest total cost, solved via the Hungarian Algorithm.
• Dummy variables balance supply and demand when unbalanced, ensuring feasible solutions.
• Vogel’s Approximation Method (VAM) is a step-by-step heuristic to find near-optimal solutions quickly.
• Northwest Corner Rule and Least Cost Method are initial allocation techniques, but VAM refines them for better efficiency.
• Real-world ties: Used in eSewa’s delivery routing, Ncell’s technician assignment, and Daraz’s warehouse logistics.

1. Introduction to Transportation Problems

Transportation problems arise when goods must be moved from sources (factories, warehouses) to destinations (stores, markets) at the minimum total cost. Key features:

• Supply constraints: Total output from sources cannot exceed availability.
• Demand constraints: Total deliveries to destinations must meet requirements.
• Cost matrix: Shows the cost of transporting one unit from each source to each destination.

Why Solve Transportation Problems?

• Cost efficiency: Reduces logistics expenses (e.g., fuel, labor, storage).
• Resource optimization: Balances supply and demand to avoid shortages or excess inventory.
• Service improvement: Faster deliveries (e.g., Pathao’s rider assignments, NTC’s fuel depot routing).

IMAGE: Supply chain logistics network | Sources, destinations, and transportation routes in a real-world supply chain

2. Mathematical Formulation

A transportation problem can be represented as:

• Decision variables: $x_{ij}$ = units shipped from source $i$ to destination $j$.
• Objective: Minimize total cost $Z={\sum }_{i=1}^m{\sum }_{j=1}^n{c}_{ij}{x}_{ij}$.
• Constraints:
  • Supply: ${\sum }_{j=1}^n{x}_{ij}\le S_i$ (for all sources $i$).
  • Demand: ${\sum }_{i=1}^m{x}_{ij}\ge D_j$ (for all destinations $j$).

Example: BIROI Electronics Case

BIROI manufactures smart home appliances in 3 factories (F1, F2, F3) and distributes to 4 stores (S1, S2, S3, S4). The cost matrix (in Rs.) and supply-demand data are:

Problem: Total supply (14 + 27 + 10 = 51) < total demand (15 + 19 + 11 + 10 = 55). Solution: Add a dummy source with zero cost to balance demand.

3. Solving Transportation Problems

Step 1: Balance Supply and Demand

If supply ≠ demand, introduce a dummy source/destination with zero cost.

• Example: BIROI’s case has a deficit of 4 units. Add a dummy factory $F4$ with supply = 4 and cost = 0.

Step 2: Initial Feasible Solution (Northwest Corner Rule)

Start at the top-left cell (F1-S1) and allocate as much as possible, moving right or down.

• BIROI’s allocation:
  • F1 → S1: min(14, 15) = 14 (S1 demand met).
  • F1 → S2: 0 (F1 supply exhausted).
  • F2 → S2: min(27, 19) = 19 (S2 demand met).
  • F2 → S3: min(8, 11) = 8 (F2 supply left = 9).
  • F2 → S4: min(9, 10) = 9 (S4 demand met, F2 exhausted).
  • F3 → S3: min(10, 3) = 3 (S3 demand met).
  • Dummy $F4$ → S3: 2 (to meet remaining demand).
  • Dummy $F4$ → S4: 2 (to meet remaining demand).

Total cost: $(14\times 9)+(19\times 7)+(8\times 9)+(9\times 12)+(3\times 12)+(2\times 0)+(2\times 0)=126+133+72+108+36=475$ Rs.

Step 3: Optimality Check (Stepping-Stone Method)

Check if the current solution is optimal by testing closed loops (alternating + and – signs).

• If all opportunity costs ≥ 0, the solution is optimal.
• If any opportunity cost < 0, adjust allocations to reduce total cost.

Step 4: Vogel’s Approximation Method (VAM)

A better heuristic than Northwest Corner Rule:

1. Calculate penalties for each row/column:
   • Penalty = difference between the 2nd smallest and smallest cost.
2. Select the row/column with the highest penalty and allocate to the lowest cost cell.
3. Repeat until all demands/supplies are met.

BIROI’s VAM Solution:

1. Row penalties:
   • F1: min(7,9) = 7, next = 8 → penalty = 1.
   • F2: min(8,9) = 8, next = 11 → penalty = 3.
   • F3: min(10,12) = 10, next = 13 → penalty = 3.
   • Dummy: all costs = 0 → penalty = 0. Highest penalty: F2 or F3 (penalty = 3). Choose F2 (lower cost cell F2-S1 = 8).
2. Allocate 14 to F2-S1 (F1’s supply is exhausted, so F2 takes over).
   • Update supplies/demands.
3. Next highest penalty: Column S2 (penalty = 2).
   • Allocate 19 to F2-S2 (F2 exhausted).
4. Continue until all demands are met.

Final VAM allocation (optimal):

• F1 → S2: 14
• F2 → S1: 14, S3: 13
• F3 → S2: 5, S4: 10
• Total cost: 389 Rs. (better than Northwest’s 475 Rs.).

4. Assignment Problems

Assignment problems allocate tasks to agents (e.g., workers, machines) with the minimum total cost. Key differences from transportation problems:

Hungarian Algorithm (Steps)

1. Subtract row minima from each row.
2. Subtract column minima from each column.
3. Cover all zeros with the fewest lines. If lines = number of rows/columns, optimal solution found.
4. Adjust the matrix by finding the smallest uncovered value, subtracting it from uncovered cells, and adding it to cells covered by two lines.
5. Repeat until optimal assignment is found.

Example: ABC Motors (Past Exam Question)

ABC Motors has 4 machines (M1-M4) and 4 jobs (J1-J4). Cost matrix (in Rs.):

Solution:

1. Subtract row minima:
   • M1: 10,8,12,9 → [0, -2, 2, -1]
   • M2: 7,11,10,13 → [0, 4, 3, 6]
   • M3: 9,12,8,11 → [1, 3, 0, 2]
   • M4: 11,9,10,7 → [4, 2, 3, 0]
2. Subtract column minima:
   • J1: [0,0,1,4] → [0,0,0,3]
   • J2: [-2,4,3,2] → [-2,4,3,2]
   • J3: [2,3,0,3] → [2,3,0,3]
   • J4: [-1,6,2,0] → [-1,6,2,0]
3. Cover zeros with 3 lines (optimal). Assign:
   • M1 → J2 (cost = 8)
   • M2 → J1 (cost = 7)
   • M3 → J3 (cost = 8)
   • M4 → J4 (cost = 7) Total cost: 8 + 7 + 8 + 7 = 30 Rs.

5. Real-World Applications

In the Real World

1. eSewa’s Delivery Routing

   • Problem: Assign delivery agents to customer orders with varying distances and costs.
   • Solution: Transportation model minimizes fuel costs and delivery time.
   • Example: eSewa uses VAM to route agents from depots (Kathmandu, Pokhara) to customers, reducing idle time.

2. Ncell’s Technician Assignment

   • Problem: Assign repair technicians to fault locations with minimal travel cost.
   • Solution: Assignment problem solved via Hungarian Algorithm.
   • Example: Ncell’s dispatch system matches technicians to nearby faults, cutting response time by 30%.

3. Daraz’s Warehouse Logistics

   • Problem: Ship products from warehouses to fulfillment centers at lowest cost.
   • Solution: Transportation model with dummy variables for unbalanced supply/demand.
   • Example: Daraz’s Nepal warehouse in Lalitpur supplies stores in Kathmandu, Pokhara, and Biratnagar using optimized routes.

IMAGE: eSewa delivery route optimization | Map showing optimal paths from depots to customers using transportation models

6. Case Study: Nabil Bank’s Loan Processing

Problem: Nabil Bank has 3 branches (Lalitpur, Thapathali, Bhaktapur) processing loan applications from 4 districts (Kathmandu, Lalitpur, Bhaktapur, Kavrepalanchok). The cost (in Rs.) of processing and dispatching loans is:

Solution:

1. Balance supply/demand: Add dummy district with demand = 0 (since supply = demand).
2. Apply VAM:
   • Highest penalty: Thapathali branch (penalty = 150).
   • Allocate 600 to Thapathali-Kavrepalanchok (lowest cost in row).
   • Repeat until optimal.
3. Optimal cost: 1,920,000 Rs. (vs. 2,100,000 Rs. using Northwest Rule).

Impact: Saves 180,000 Rs. and reduces processing time by 20%.

7. Advantages and Limitations

8. Exam Tip

1. Understand the difference between transportation and assignment problems (supply/demand vs. one-to-one mapping).
2. Practice VAM and Hungarian Algorithm on past exam questions (e.g., BIROI, ABC Motors cases).
3. Dummy variables are critical for unbalanced problems—always check supply vs. demand first.
4. Stepping-stone method is often tested for optimality checks—know how to draw loops and calculate opportunity costs.
5. Real-world tie: Relate answers to Nepali companies (e.g., Daraz’s warehouse routes, Ncell’s technician assignments).
6. Shortcuts: Memorize that VAM often gives better initial solutions than Northwest Corner Rule.

flowchart TD
    A["Transportation Problem"] --> B["Balance Supply/Demand\n(Dummy Variables)"]
    B --> C["Initial Solution\n(Northwest or VAM)"]
    C --> D["Optimality Check\n(Stepping-Stone)"]
    D -->|"Optimal?"| E["Yes: Stop"]
    D -->|"Not Optimal"| F["Adjust Allocations\n(Loop Method)"]
    F --> D
    G["Assignment Problem"] --> H["Hungarian Algorithm\n(Row/Column Reduction)"]
    H --> I["Cover Zeros\n(Min Lines)"]
    I -->|"Lines = n?"| J["Optimal Assignment"]
    I -->|"Lines < n?"| K["Adjust Matrix\n(Subtract Min)"]
    K --> H

mindmap
  root((Transportation & Assignment Problems))
    Transportation
      Definition: Minimize shipping cost
      Steps: Balance -> Initial Solution -> Optimality Check
      Methods: Northwest, VAM, Stepping-Stone
      Example: BIROI Electronics
    Assignment
      Definition: One-to-one task allocation
      Steps: Hungarian Algorithm (Row/Col Reduction)
      Example: ABC Motors
    Real-World
      eSewa: Delivery routing
      Ncell: Technician assignment
      Daraz: Warehouse logistics
    Exam Tips
      Differentiate problems
      Practice VAM/Hungarian
      Use dummy variables