Vehicle routing is NP-hard. How do you produce a plan the depot will run tomorrow morning?

What the problem is, and why the complexity result is the least useful fact about it

The vehicle routing problem asks for a set of routes from one or more depots that serves every stop exactly once, respects vehicle capacities, and minimises some cost. It generalises the travelling salesman problem, which it contains as the single-uncapacitated-vehicle case, and is therefore NP-hard. Realistic instances add time windows, mixed fleets, access restrictions, driver shifts, pickups as well as deliveries, and asymmetric travel times that vary by hour.

Stating the complexity result is table stakes; drawing the wrong conclusion from it is the common error, and it goes both ways. One direction says the problem is intractable so anything goes, throwing away decades of heuristics that land close to the best known solutions. The other treats it as a solved library call, ignoring that constraint modelling rather than search is where operational plans succeed or fail.

The right conclusion is narrow. You will never prove a plan optimal at operational size, so you decide in advance how long you will search and what you accept when the clock stops, which reframes the task from solving routing to producing the best feasible plan obtainable in the time available, reliably.

Construct, then improve, and keep those phases separate

Every practical approach has the same two phases, and being able to name them is what distinguishes someone who has built this from someone who has read about it.

Construction produces a feasible plan quickly. The classical savings heuristic starts from one route per stop and repeatedly merges the pair whose merge saves the most distance while staying feasible. Insertion heuristics build routes stop by stop at the cheapest feasible position, and they extend naturally to time windows because feasibility is checked at insertion. Either gives you something runnable in seconds, and a feasible plan available early is worth more than an optimal one that arrives after the vans have left.

Improvement then perturbs that plan. The local search operators are small and well understood: reversing a segment within a route, moving a stop to another route, swapping a pair between routes, relocating short chains. Pure local search stops at the first local optimum, so real solvers wrap it in a metaheuristic that escapes: simulated annealing, tabu search, guided local search, or the ruin-and-recreate pattern of large neighbourhood search, which destroys part of the plan and rebuilds it with the insertion heuristic. All are anytime algorithms, so you can stop and take the incumbent, which is exactly what a wall-clock budget requires.

Two budgets, and they are not the same problem

Overnight planning has minutes. It sees the whole day's orders, can afford a large neighbourhood search over the full instance, and produces the plan that will be printed, loaded and driven. Its output is judged on cost and on whether it is executable.

Redispatch has seconds. A driver calls in sick, a vehicle fails, a customer moves a window. Half the fleet is already on the road, most of the plan is history rather than a decision, and you are repairing a small part of it under pressure. Re-solving from scratch is wrong even if it were fast enough, because it will happily reshuffle stops on routes already halfway through. So the repair problem carries constraints the planning problem does not: completed stops are fixed, in-progress routes have a current position and a remaining sequence to disturb as little as possible, and stability is itself part of the objective. Building one code path and configuring it with a shorter time limit is the mistake, because the two differ in what is variable rather than only in how long they get.

The constraints that bind

Most instances are decided by three:

• Time windows. The customer will accept the delivery between two times, and a stop served early may be refused, so the vehicle waits. Windows convert the problem from one of distance into one of schedule, and they interact viciously: two tight windows on opposite sides of the territory can force a route no distance-based objective would ever choose. Whether a window is hard or soft, and what lateness costs, is the highest-leverage modelling decision you will make.
• Capacity. Rarely a single number. Weight, volume, pallet or roll-cage positions, and temperature-controlled compartments are separate dimensions that must all hold, and the binding one differs by product. Modelling only weight when volume binds produces plans that cannot be loaded, and that failure is discovered at the dock by someone who will not trust the system again.
• Driver hours. Driving and rest limits are statutory in most jurisdictions, including under the European Union's drivers' hours rules and the equivalent United States hours-of-service regime, and they are not a soft preference you may trade against cost. They interact with time windows because a mandated break can only be taken at certain points, and a plan that assumes a break can happen anywhere is infeasible in a way the solver will not tell you about.

Then a long tail that is real but instance-specific: access restrictions by weight or dimension on particular roads, low-emission zones, sites accepting deliveries only in booked dock slots, licences required by certain stops. Each is cheap as a filter on which vehicle may serve which stop and expensive to discover after go-live.

Hard, soft, and the weights nobody writes down

A hard constraint makes a plan invalid. A soft constraint makes it worse. Deciding which is which is a business conversation disguised as a configuration question, and getting it backwards is the most common cause of a solver that returns nothing.

The infeasible-instance case deserves an explicit design. If every constraint is hard and the day's orders do not fit the fleet, the honest answer from the solver is "no solution", and that is useless to a planner at half past five in the morning. So you build in a controlled release: leave some stops unassigned at a high penalty, permit bounded lateness at a cost per minute, allow overtime as a priced option. Then the output is always a plan plus an explicit statement of what it could not honour, which is something a human can act on.

Once lateness, overtime, unserved stops and distance all carry costs, the objective is a weighted sum, and those weights encode business priorities that exist nowhere else in writing. A plan trading three late arrivals for shorter total distance is optimal or unacceptable depending entirely on numbers somebody chose, possibly by accident. Surfacing them and reviewing them with operations beats any improvement to the search.

Why the planner overrides your plan every morning

This is the part that separates a strong answer, and it is not about algorithms. Depots override optimiser output routinely, and the reflex is to read that as resistance to change. It is usually information. The planner knows the driver on that route is new and slower on the rural leg, that one customer's goods-in closes early on Fridays regardless of the window on file, that two particular stops must not go on the same van because of a past dispute. None of that was in your model, so your plan is optimal with respect to a world that does not exist.

Which gives you the actual engineering programme. Log every override with a reason, cluster them, and you have a prioritised list of the constraints you failed to model. Feed the accepted overrides back as fixed assignments so the same correction is not made twice. And do not measure the solver only against its own objective, because a plan that scores well and is edited by hand every day is worse than a slightly costlier one that runs untouched.

The same physical-versus-recorded gap that dominates the rest of logistics shows up here as travel times: your matrix is a model of a road network on an average day, and the road tomorrow will have an incident on it. Plans with no slack are optimal against the matrix and fragile against the road, so buffer is a deliberate parameter rather than an admission of imprecision.

A routing system earns its place when the depot stops editing its output, and that happens through modelled constraints and named cost weights rather than through a better search.