Van Routing on a Single Arterial Road: Heuristic, Exact, or Structurally Solvable
A courier company serves 2,000 delivery points in a single shift. Every point lies on one straight arterial road running north–south; the depot sits at kilometre 0, and the sorted stop coordinates run from −18.0 km to +34.0 km, roughly evenly spread. A van averages 50 km/h, loading at the depot takes 20 minutes, and the legal shift allows 150 minutes of work. The routing module uses a nearest-neighbour heuristic, which on last Tuesday's list produced a 168 km tour and a 201-minute completion time, breaching the shift. Operations blames congestion on the road network; the developer blames the heuristic; the planner wants to replace it with an exact solver that stores, for every subset of the 2,000 stops, the cheapest way to have visited that subset and be parked at each possible last stop. The dispatch manager wants the argument settled before the new season, when the list will grow to about 2,600 points and the shift limit will stay unchanged.
1. Compute the minimum feasible tour length and completion time for the 2,000-stop list, and decide whether the shift can be completed.
Read the worked answer
Lower bound. Because the depot at 0 lies inside the served interval [−18, +34], every point of the interval must be reached and then left again: each road segment is traversed at least twice, once outbound and once inbound. Hence any tour starting and ending at the depot costs at least 2 × (34 − (−18)) = 104 km.
Achievability. Drive 0 → −18 (18 km), then the full span −18 → +34 (52 km), then 34 → 0 (34 km). Total 18 + 52 + 34 = 104 km, so the bound is attained.
Time. 104 / 50 h = 2.08 h = 124.8 min, plus 20 min loading = 144.8 min, inside the 150-minute limit with only about 5 minutes of slack.
Judgement. Tuesday's 2,000-stop list is feasible - but marginally. A 5% drop in average speed, a single stop beyond +34 km, or a longer load time breaks the shift. The report to the dispatch manager should state feasibility and the slack, because a plan that only works at 50 km/h has no buffer for the congestion that operations is worried about.
2. The nearest-neighbour heuristic returned 168 km. Diagnose the cause and judge which party is right about responsibility.
Read the worked answer
Diagnosis. On a line metric, nearest-neighbour repeatedly picks the closest unvisited stop, which forces it to alternate sides of the depot: each pick is locally cheap but the tour zig-zags across the interval, so some segments are traversed many times instead of twice. The result, 168 km against an optimum of 104 km, is 62% excess - a structural failure of the heuristic on this geometry, not a network effect.
Responsibility. The developer is right about the cause and operations is wrong to blame the road network: with a fixed speed and a line metric, the route length entirely explains the 201-minute result. But 'the heuristic is bad' understates the issue: the problem here is not hard at all. Once stops are sorted, the optimum is available by inspection.
What to tell each party. Operations: Tuesday's route was 64 km longer than needed and that, not congestion, caused the breach. Developer: nearest-neighbour has no performance guarantee on line metrics and should never be the fallback for this data; replace it, but with a sorted-order construction, not with a heavier general solver. Neither should be asked to accept a heuristic whose worst case is this far from optimal without a lower bound to detect the gap.
3. Evaluate the planner's proposed exact solver (a state for every subset of the 2,000 stops), and propose a correct approach if the stops later cease to lie on a line.
Read the worked answer
The proposed solver is not merely slow, it is astronomically infeasible. A subset-based Held–Karp formulation needs on the order of n·2ⁿ states: 2,000 × 2²⁰⁰⁰, which exceeds any conceivable memory or time budget. Doubling the machine or the budget does not help; the growth is exponential in n.
But this instance has structure that removes the need for it. In an optimal tour on a line, the set of visited stops is always a contiguous block in sorted order - you never skip a nearer stop to serve a farther one and come back. So the state is (i, j, side) where [i, j] is the served interval and the van is at the left or right end. That is O(n²) states ≈ 4 × 10⁶ for n = 2,000, each with O(1) transitions: milliseconds, and it stays trivial at 2,600 points.
If stops leave the line (2-D coordinates, city streets), no such shortcut exists: the problem contains the travelling salesman problem, which is NP-hard. The defensible design is then a constructive heuristic (nearest neighbour, then 2-opt/Or-opt improvement) plus a lower bound - a minimum spanning tree or 1-tree relaxation - so the gap to optimality is measured rather than assumed, and the planner can say 'within 6% of a valid lower bound' instead of 'looks fine'.