Optimizing Photoshoot Timelines: North-West Corner vs. Vogel's Approximation

Framing the Photoshoot as a Transportation Problem

At its core, a transportation problem aims to minimize the cost of shipping goods from a set of sources (e.g., factories) to a set of destinations (e.g., warehouses). Given your background in Operations Research, you'll recognize the standard linear programming formulation.

To apply this to our photoshoot scenario, we must define our terms:

• Sources: These are the blocks of time available for the shoot. Let's say we have a Morning session (120 minutes) and an Afternoon session (180 minutes). These are our supply points.
• Destinations: These are the specific outfit-pose combinations we want to shoot. Each requires a certain amount of time. Let's define four combinations:
  • Combo A (Lingerie 1, Pose 1): Requires 80 minutes.
  • Combo B (Lingerie 1, Pose 2): Requires 100 minutes.
  • Combo C (Lingerie 2, Pose 1): Requires 50 minutes.
  • Combo D (Lingerie 2, Pose 2): Requires 70 minutes.
• Cost/Objective: Our goal is to maximize total "sexiness." However, standard transportation algorithms are designed to minimize cost. Therefore, we must convert our maximization problem into a minimization one. We do this by creating a "regret" or "opportunity loss" matrix.

Let's assume we have the following "sexiness" scores (on a 1-10 scale) for each combo in each time block, perhaps due to lighting or energy levels:

The highest possible score is 10. We convert this into a cost matrix by subtracting each score from the maximum score. The cell with the highest sexiness (Afternoon, Combo B) now has a cost of 0, representing the ideal allocation.

Applying this conversion, our problem becomes a minimization problem with the following cost matrix. Notice that the total supply (120 + 180 = 300) equals the total demand (80 + 100 + 50 + 70 = 300), so we have a balanced transportation problem.

Photoshoot Time Allocation Problem (Minimization)

Our task now is to find an initial basic feasible solution (IBFS)—a starting allocation that satisfies all supply and demand constraints. We will explore two methods to do this.

Method 1: The North-West Corner (NWC) Rule

The North-West Corner rule is a simple, mechanical heuristic that pays no attention to costs. It simply starts at the top-left ("north-west") cell of the matrix and allocates as much as possible.

The algorithm is as follows:

1. Start at the top-left cell (Morning, Combo A).
2. Allocate the minimum of the available supply for that row and the demand for that column.
3. Subtract the allocated amount from the supply and demand.
4. If a row's supply is exhausted, cross it out and move down. If a column's demand is met, cross it out and move right.
5. Repeat for the new top-left cell in the un-crossed-out matrix until all allocations are made.

Let's apply this to our photoshoot problem:

1. Cell (Morning, A): min(Supply=120, Demand=80) = 80. Allocate 80.

   • New Morning Supply = 120 - 80 = 40.
   • New Combo A Demand = 80 - 80 = 0.
   • Combo A demand is met, so we cross out Column A and move right.

2. Cell (Morning, B): min(Supply=40, Demand=100) = 40. Allocate 40.

   • New Morning Supply = 40 - 40 = 0.
   • New Combo B Demand = 100 - 40 = 60.
   • Morning supply is exhausted, so we cross out Row 1 and move down.

3. Cell (Afternoon, B): min(Supply=180, Demand=60) = 60. Allocate 60.

   • New Afternoon Supply = 180 - 60 = 120.
   • New Combo B Demand = 60 - 60 = 0.
   • Combo B demand is met, cross out Column B and move right.

4. Cell (Afternoon, C): min(Supply=120, Demand=50) = 50. Allocate 50.

   • New Afternoon Supply = 120 - 50 = 70.
   • New Combo C Demand = 50 - 50 = 0.
   • Combo C demand is met, cross out Column C and move right.

5. Cell (Afternoon, D): min(Supply=70, Demand=70) = 70. Allocate 70. All supplies and demands are now met.

NWC Initial Solution:

Total "Regret" Cost = $(80\times 1)+(40\times 3)+(60\times 0)+(50\times 5)+(70\times 2)$ = $80+120+0+250+140=590$.

The video below gives a full walkthrough of the NWC method on a different example, which will help solidify your understanding of the mechanics.

Method 2: Vogel's Approximation Method (VAM)

VAM is a more intelligent heuristic. It considers the "penalty" or "opportunity cost" of not using the best available route. This should resonate with the Minimax Regret criterion you've studied previously. The goal is to make the least "bad" decision at each step.

The VAM algorithm is iterative:

1. For each row and column, calculate a penalty cost: the absolute difference between the two smallest costs in that row/column.
2. Identify the row or column with the largest penalty. This is where a poor choice is most costly.
3. In that selected row or column, find the cell with the lowest cost.
4. Allocate the maximum possible amount to this cell (the minimum of its row supply and column demand).
5. Update supplies and demands, cross out the satisfied row/column, and repeat from step 1 until all allocations are made.

Let's apply VAM to our photoshoot problem.

Iteration 1:

• Penalties:
  • Row 1 (Morning): 3 - 1 = 2
  • Row 2 (Afternoon): 2 - 0 = 2
  • Col A: 2 - 1 = 1
  • Col B: 3 - 0 = 3
  • Col C: 5 - 4 = 1
  • Col D: 6 - 2 = 4
• Action: The highest penalty is 4, in Column D. The lowest cost in Column D is 2 (Afternoon, D).
• Allocate: min(Supply=180, Demand=70) = 70 to cell (Afternoon, D).
  • New Afternoon Supply = 110. New Combo D Demand = 0. Cross out Column D.

Iteration 2:

• Penalties (recalculated):
  • Row 1: 3 - 1 = 2
  • Row 2: 2 - 0 = 2
  • Col A: 2 - 1 = 1
  • Col B: 3 - 0 = 3
  • Col C: 5 - 4 = 1
• Action: The highest penalty is 3, in Column B. The lowest cost in Column B is 0 (Afternoon, B).
• Allocate: min(Supply=110, Demand=100) = 100 to cell (Afternoon, B).
  • New Afternoon Supply = 10. New Combo B Demand = 0. Cross out Column B.

Iteration 3:

• Penalties (recalculated):
  • Row 1: 4 - 1 = 3
  • Row 2: 5 - 2 = 3
  • Col A: 2 - 1 = 1
  • Col C: 5 - 4 = 1
• Action: We have a tie in penalties (3 for Row 1 and Row 2). We can break ties arbitrarily. Let's choose Row 1. The lowest cost in Row 1 is 1 (Morning, A).
• Allocate: min(Supply=120, Demand=80) = 80 to cell (Morning, A).
  • New Morning Supply = 40. New Combo A Demand = 0. Cross out Column A.

Final Allocations:
Only two cells remain.

• Allocate 40 to (Morning, C) to use up Morning's supply.
• Allocate 10 to (Afternoon, C) to use up Afternoon's remaining supply and meet Combo C's demand (40+10=50).

VAM Initial Solution:

Total "Regret" Cost = $(80\times 1)+(40\times 4)+(100\times 0)+(10\times 5)+(70\times 2)$ = $80+160+0+50+140=430$.

The following video provides another detailed walkthrough of VAM.

Comparison of NWC and VAM

Let's compare the results of our initial solutions for the photoshoot allocation:

• NWC Solution Cost: 590
• VAM Solution Cost: 430

As expected, VAM produced a significantly better initial solution. While both are valid feasible solutions, the VAM allocation starts us much closer to the optimal plan.

• North-West Corner: A "naive" method. It is very fast and simple to execute, but because it completely ignores the underlying costs, the resulting solution is often far from optimal.
• Vogel's Approximation Method: A "smart" heuristic. It requires more computation at each step (calculating penalties) but produces a high-quality initial solution by prioritizing allocations where the penalty for making a mistake is highest.

In practice, the extra effort of VAM is almost always worthwhile, as it can dramatically reduce the number of steps required in subsequent optimization procedures.

Conclusion

In this lesson, we successfully modeled a photoshoot scheduling task as a transportation problem and generated two distinct initial allocation plans.

Key Takeaways:

• Problem Framing: Maximization problems (like maximizing "sexiness") can be converted into standard minimization transportation problems by creating a "regret" or "opportunity loss" matrix.
• North-West Corner Rule: This is a simple, cost-ignorant heuristic that provides a fast but often poor-quality initial feasible solution.
• Vogel's Approximation Method (VAM): This is a more sophisticated heuristic that uses penalty costs to guide allocations, generally resulting in a much better initial solution that is closer to optimal.
• Initial vs. Optimal: Both NWC and VAM provide an Initial Basic Feasible Solution (IBFS). Neither guarantees optimality.

We now have a good starting point from VAM. But is it the best possible allocation? In our next lesson, we will learn the Modified Distribution (MODI) Method, a powerful algorithm used to test an initial solution for optimality and, if it's not optimal, to systematically improve it until the true minimum-cost (or maximum-sexiness) allocation is found.