Vehicle Routing — From Exact Optimization To Real Drivers

A Different Kind Of Decision

The decisions so far have been quantities — how much to order, how many nurses, which generators. This one is combinatorial: choose a set of routes. The difference is not a matter of degree. A vehicle-routing instance with 100 customers has more feasible solutions than there are atoms in the observable universe, and no amount of forecasting accuracy helps you search them.

The honest way to start is with the formulation that is provably right, on an instance small enough for it to finish. Nine customers, capacity 25, at least two vehicles: a mixed-integer program returns the exact optimum, 217.2, in 1.1 seconds, and reports that it is optimal rather than merely the best found. That certificate is the thing exact methods give you and nothing else does.

It also does not scale, so the next rung is a classical heuristic — Clarke–Wright savings to build routes by merging the pairs that save the most, then 2-opt to uncross the result. On the nine-customer instance it lands on 217.2: the same answer as the exact solver, at a 0.0% gap, in under a millisecond. On 100 customers it produces 1,178 over 12 routes in 4 milliseconds. That it matches the optimum on the small case is not proof it will elsewhere — it is a sanity check that the heuristic is implemented correctly, which is why the small instance is worth solving twice.

A production solver is the reference point. Google OR-Tools with guided local search reaches 1,165, 1.1% shorter than the hand-rolled heuristic — and takes 8 seconds to do it, against 4 milliseconds. That ratio is the honest summary of what the extra machinery buys on an instance this size.

Learning Where To Search

Then the machine-learning rung, which is predict-then-optimize applied to the search itself rather than to the demand. An edge classifier is trained on 51,750 arcs — of which only 2.5% appear in a solution — to predict which arcs are worth considering at all. Keeping each node's best few candidates prunes the graph, and the optimizer searches what is left.

At k = 12 candidates per node the pruned graph holds 726 edges — 14% of all pairs — while covering 93% of the arcs the full solution uses, and the route it finds measures 1,164 against the full-graph heuristic's 1,178. Slightly better, from searching a seventh of the space, in 3 milliseconds. The learning does not solve the problem; it decides where the solver should look.

Real Drivers Disagree With The Optimizer

That is the methods ladder on a synthetic instance. The second notebook asks whether any of it describes reality, using the 2021 Amazon Last Mile Routing Research Challenge: 6,112 real routes across 17 delivery stations, with the sequence each driver actually took.

Drivers do not follow the optimizer, and the gap is large. Across 60 routes averaging 138 stops, the distance a driver actually drove is a median 1.15× the travelling-salesman optimum — 15% further. On the standard reading that is 15% of waste to be recovered by better software.

The standard reading is wrong here, and one extra measurement shows it. Counting zone switches — how often a route leaves one delivery zone and enters another — the TSP route switches a median of 41 times while the driver switches 23. Drivers are not failing to optimize distance; they are optimizing something else, and paying distance for it. Anyone who has parked a van knows why: re-entering a zone means re-parking, re-orienting, and re-walking a building you already left.

Building an optimizer that respects that structure settles it. A zone-aware route costs 1.06× the TSP distance — recovering most of the driver's 15% penalty — while cutting switches to 21, fewer even than the driver manages, and matching 56% of the driver's actual stop-to-stop transitions against pure TSP's 51%.

The objective was wrong, not the drivers. An optimizer measured only on distance declares experienced drivers 15% inefficient; an optimizer given the constraint they are actually working under agrees with them far more, and beats them on the criterion they care about. That is the routing version of this section's thesis: the hard part is rarely the search, it is knowing what to put in the objective.

Notebooks

References

• Dantzig, G. B. & Ramser, J. H. (1959). The truck dispatching problem. Management Science 6(1), 80–91. — the problem, named
• Clarke, G. & Wright, J. W. (1964). Scheduling of vehicles from a central depot to a number of delivery points. Operations Research 12(4), 568–581. — the savings heuristic
• Croes, G. A. (1958). A method for solving traveling-salesman problems. Operations Research 6(6), 791–812. — 2-opt
• Merchán, D. et al. (2024). 2021 Amazon Last Mile Routing Research Challenge: data set. Transportation Science 58(1), 8–11. — the real routes
• Bengio, Y., Lodi, A. & Prouvost, A. (2021). Machine learning for combinatorial optimization: a methodological tour d'horizon. European Journal of Operational Research 290(2), 405–421. — where the learned-candidate idea sits