Your exact subset-DP route planner tops out near 20 stops, but dispatch now needs 35 — how do you decide what replaces it?

## Why this is a judgment call and not a debugging task A planner that handles 20 stops and is asked for 35 is not slow; it is in the wrong complexity class for the requirement. The state count of a subset route DP is 2^n·n: about 2 × 10^7 at n = 20 and about 1.2 × 10^12 at n = 35. That is a factor of roughly 60,000 in memory alone. Every optimisation available inside the method — two-byte cost entries, keeping only two layers of the table live, pruning masks forbidden by time windows, fixing the start to kill rotational symmetry — buys constant factors that together are worth two or three extra stops. Saying this out loud early is most of the answer, because it stops the team from spending a quarter on a rewrite that cannot succeed. ## The three real options **Decompose the instance.** Cluster the stops so that each cluster is small enough for the exact method, solve each exactly, and stitch the clusters together with a cheaper ordering pass. This preserves the code you already trust, keeps a meaningful optimality guarantee *within* each cluster, and fails gracefully — a bad clustering costs route quality, not correctness. It is usually the lowest-risk move when geography is naturally clumpy, which for delivery work it generally is. **Change exact method.** Branch-and-bound with good lower bounds, or a mature solver driven by cutting planes, solves routing instances far beyond what a subset DP can hold, because it never materialises the whole state space. The catch is runtime variance: the same solver that finishes in 40 ms on Tuesday's stops may take minutes on Thursday's. If dispatch has a hard latency budget, you need an anytime formulation — best solution so far, returned when the clock expires — and the operational discipline to monitor that. **Accept an optimality gap.** A constructive pass plus local improvement gets within a small percentage of optimal on realistic instances, in predictable milliseconds, in code a normal engineer can read. For most delivery businesses this is the right answer, and the argument for it is economic rather than algorithmic. ## The inputs that actually decide it - **Latency budget.** If a dispatcher waits for the route, a method with unbounded tail latency is disqualified regardless of solution quality. Predictability often outranks optimality. - **The value of a percent.** Compute it: percent of route cost × routes per day × fleet size. If three percent of driving time is worth a meaningful sum annually, an exact-ish method earns its complexity. If it is worth less than an engineer's salary, it does not. - **Maintenance and staffing.** A hand-tuned solver is one person's expertise. A heuristic with a clear structure is the whole team's. Ask who debugs a bad route at 3am on a public holiday, and whether that person can explain why the planner chose it — explainability matters to dispatchers who override the machine. - **Input shape stability.** If 35 is really "usually 12, occasionally 35", a hybrid is legitimate: run the exact DP when the instance is small and fall back above a threshold. That threshold becomes a tuned, monitored parameter, not a constant someone guessed. ## What to do with the code you already have Do not delete the exact DP. It becomes the **oracle**: on randomly generated instances of 10–16 stops it produces the true optimum, and a test can assert that the heuristic stays within an agreed percentage of it. That converts "the new planner seems fine" into a measured, regression-tested bound, and it is by far the cheapest quality guarantee available once you have accepted an approximate method. It is also the argument that makes the switch defensible to a sceptical stakeholder: you can quote the gap rather than promise it. ## How to present the decision Write the options with their costs, not their elegance: expected route-cost delta, worst-case latency, engineer-weeks to build, and who can maintain each. Recommend one. Name the reversal condition — for instance, "if measured gap exceeds four percent, or instances shrink below 20 stops after the new depot opens, we revisit." A principal-level answer is not the cleverest algorithm; it is a decision someone else can inherit, with the evidence attached and the exit criteria written down. ## The failure modes to avoid Rewriting the same DP in a faster style and hoping; treating an exponential wall as a hardware purchase; adopting a heuristic without ever measuring its gap; and building a bespoke exact solver whose only maintainer then changes teams. Each of those is a decision that looked technical and was actually organisational.