What a CVRP solver actually solves (and why it's NP-hard)

The capacitated vehicle routing problem, CVRP, asks a simple question with an expensive answer: given a depot, a set of stops with known demand, and a fleet of trucks with fixed capacity, what assignment of stops to trucks and what sequence per truck minimizes total distance without any truck going over capacity? For a handful of stops you could work it out on paper. Past a few dozen, the number of valid combinations grows faster than any computer could ever check them all one by one, which is what "NP-hard" means in practice: there's no known shortcut that guarantees the perfect answer in a reasonable amount of time.

This is why route optimization software doesn't claim to find the mathematically optimal route. It runs heuristics: clustering algorithms that group stops by capacity and geography, local search that swaps stops between routes looking for improvements, and multi-pass refinement that keeps tightening a plan that was already good. None of these guarantee perfection. All of them reliably beat a human planner working from a spreadsheet, because they check far more of the possibility space than a person has time for.

The practical upshot for anyone evaluating AI route planning tools: ask what the solver actually optimizes for, not just whether it says "AI" on the label. A solver that treats capacity and time windows as hard constraints from the first pass will consistently outperform one that builds a route first and patches violations after, because by the time you're patching, the cheap solutions are already gone.