Placing a Supply Depot in Angola
A training command must locate a small logistics depot to serve three units. Unit X is at coordinates (0, 0), Unit Y at (8, 0), and Unit Z at (0, 6) on a map grid in kilometers. Roads run only along the grid lines, so travel distance is measured as |Δx| + |Δy| (Manhattan distance). The depot must minimize the total road distance to the three units, and it must sit on a grid intersection. A planner proposes placing the depot at the centroid (2.67, 2.00).
1. Compute the total Manhattan distance from the proposed centroid to each unit and evaluate the proposal.
Read the worked answer
The centroid is not on a grid intersection, so first round to (3, 2).
Distances from (3, 2):
- To X (0,0): |3−0| + |2−0| = 3 + 2 = 5 km.
- To Y (8,0): |3−8| + |2−0| = 5 + 2 = 7 km.
- To Z (0,6): |3−0| + |2−6| = 3 + 4 = 7 km.
Total: 5 + 7 + 7 = 19 km.
Evaluation: Feasible, but there is no reason to assume it is optimal - the centroid minimizes squared Euclidean distance, not Manhattan distance. We must test alternatives.
2. Find the grid point that minimizes total Manhattan distance and compare it with the proposal.
Read the worked answer
For Manhattan distance, the optimum separates into x and y: choose the median of the coordinates.
x-coordinates: 0, 8, 0 → sorted 0, 0, 8 → median = 0. y-coordinates: 0, 0, 6 → sorted 0, 0, 6 → median = 0.
So the optimal depot is at (0, 0) - coinciding with Unit X.
Check:
- To X: 0 km.
- To Y: 8 km.
- To Z: 6 km.
- Total: 14 km.
Comparison: 14 km < 19 km. The planner's centroid is 5 km worse. The median rule is the correct tool for Manhattan distance; the centroid is the wrong heuristic here.