Contents
Figure 1: Vehicle Routing with Reinforcement Learning: Can a Neural Policy Beat Heuristics? — the classical baseline is stronger than most tutorials admit
Your dispatcher draws routes on a map in ten minutes and calls it "good enough." Your solver takes thirty seconds and does better. Now someone wants a neural network to do it in thirty milliseconds. Can it actually win?
I have not benchmarked a neural policy on a live fleet, so the neural side of this post is analysis backed by published results. The classical side I did measure, on two CVRP instances, and one of those numbers surprised me enough to change the argument. My honest read: "sometimes, and not where the headlines say."
What Is the Vehicle Routing Problem?
The VRP asks you to serve a set of customers with a fleet of vehicles at minimum total cost, usually distance or travel time. Each customer is visited exactly once, and every route starts and ends at a depot.
Real versions add constraints. The most common is the capacitated VRP (CVRP), where each vehicle has a load limit. Others add time windows (VRPTW), pickup and delivery pairs, or multiple depots. VRP is NP-hard, so exact solvers struggle as instances grow.
How Classical Heuristics Work
Before judging a neural policy, you need to respect what it competes against. Decades of operations research produced very strong tools:
- Nearest neighbour: build a route by always visiting the closest unserved customer.
- Clarke-Wright savings: start with one route per customer and merge pairs by the distance each merge saves.
- 2-opt and Or-opt: swap and relocate stops to shorten an existing route.
- Metaheuristics: guided local search, simulated annealing and tabu search escape local optima.
The heavy hitters are LKH-3 and HGS (hybrid genetic search), which dominate routing benchmarks [3]. Google's OR-Tools routing library is the accessible, solid option, and it is the baseline I use in most posts, including the OR-Tools vs reinforcement learning comparison on this site [5].
How RL Approaches VRP
Neural methods usually frame routing as a sequential decision process: pick the next customer, then the next, until every stop is served.
Constructive policies:
- State: customer locations, demands, remaining capacity, current partial route.
- Action: choose the next unvisited node, or return to the depot.
- Reward: negative total route length.
- Masking: block visited nodes and customers that exceed remaining capacity.
The reference architecture is the attention model from Kool, van Hoof and Welling, which encodes customers with a transformer and decodes routes step by step, trained with policy gradients and a baseline [1]. POMO then exploits the symmetry that a route can start anywhere: it samples many rollouts from different first nodes and uses their shared reward as a baseline, which cuts variance and improves quality without a learned critic [2].
Improvement policies take a different route: start from a decent solution and learn which local search move to apply, or learn to destroy and repair parts of it. I like this family best, because it borrows structure from proven heuristics instead of ignoring it.
Hybrids go further: predict promising edges and hand a sparse graph to a solver, or use a network to guide HGS or LKH.
What I Measured
A fair argument needs a real baseline, so I generated two CVRPs and ran three classical methods on each. Random points in a 100 × 100 km square, demands 1 to 10, capacity 50, seed 42, distances in metres, OR-Tools 9.15.6755 with guided local search.
| Instance | Method | Cost (m) | Time | Gap vs best |
|---|---|---|---|---|
| 50 customers | Nearest neighbour | 1,355,874 | 0.3 ms | +33.2% |
| 50 customers | Clarke-Wright | 1,133,407 | 1.3 ms | +11.3% |
| 50 customers | OR-Tools, 1 s | 1,054,540 | 1.00 s | +3.6% |
| 50 customers | OR-Tools, 10 s | 1,018,118 | 10.00 s | best |
| 200 customers | Nearest neighbour | 4,100,266 | 2.7 ms | +14.3% |
| 200 customers | Clarke-Wright | 3,473,282 | 12.9 ms | −3.1% |
| 200 customers | OR-Tools, 1 s | 3,668,608 | 1.00 s | +2.3% |
| 200 customers | OR-Tools, 10 s | 3,668,608 | 10.00 s | +2.3% |
The 200-customer row is the one worth staring at. A thirteen-millisecond savings heuristic produced a solution 3.1% cheaper than a ten-second guided-local-search run, and doubling the solver's budget changed nothing at all.
That is not an argument against solvers; it is an argument about baselines. OR-Tools' default first-solution strategy is the weak link here: switching it to SAVINGS moved the 200-customer result from 3,668,608 to 3,585,870, which is still 3.1% behind the hand-written merge. If your solver baseline is one call with default parameters, you have not measured the solver — you have measured a default.
It also sets the bar for any neural policy: on 50 customers, the solver is within 3.6% of its best result after one second, and on 200 customers it is within 2.3%. A learned policy has to beat those numbers at millisecond latency, and it has to do it after training.
So, Can a Neural Policy Beat Heuristics?
Here is the blunt scorecard. The answer changes with the metric.
| Dimension | Classical heuristics | Neural policies |
|---|---|---|
| Quality, one instance | HGS and LKH-3 usually win | Trails at larger sizes |
| Hard constraints | Native and exact | Needs masking or repair |
| Generalisation | No retraining | Can collapse off-distribution |
| Auditability | Deterministic, inspectable | Black box |
| Inference speed | Seconds to minutes | Milliseconds |
| Batched throughput | One instance at a time | Thousands on a GPU |
| Dynamic, stochastic settings | Re-solve each change | Policy reacts instantly |
The reported pattern in the literature is consistent: constructive neural methods run far faster than classical solvers but usually trail them in quality on static benchmarks. They close the gap on small instances and struggle as customer counts grow into the hundreds or thousands [1][2]. Verify against recent papers, because this field moves quickly.
Where RL Actually Earns Its Keep
Dynamic Routing
Food delivery, ride-hailing and same-day couriers receive requests while vehicles already drive. A static solver must re-plan constantly and cannot anticipate future orders without heavy stochastic modelling. A policy trained on simulated demand can learn to hold a driver near a likely hotspot. This is RL's strongest argument, and it is the one the static benchmarks cannot measure.
Latency-Critical Dispatch
If you need an answer in milliseconds, a solver may not fit the budget. A neural policy delivers a good route immediately, and a good fast answer beats a perfect late one. The 1-second row above is what "too slow" looks like at scale.
High-Volume Repetition
Suppose a logistics platform solves similar problems all day. Training cost spreads across millions of decisions, and the economics flip in RL's favour. Estimate your volume honestly before the pitch meeting, because at ten instances a day they never flip.
How to Test Fairly
Want to run your own comparison? Follow this protocol:
- Define metrics: route cost, runtime and constraint violations.
- Tune your baseline. My Clarke-Wright result above is exactly why: an untuned solver loses to a 13-millisecond heuristic.
- Match budgets: report quality at equal wall-clock time, and separately at equal quality.
- Test across sizes, including instances larger than your training data.
- Use standard benchmarks: CVRPLIB instances, such as the X set, let you compare against published numbers [4].
- Count total cost: training time, engineering effort and maintenance.
A weak baseline makes any method look brilliant. Tune the solver like you want it to win.
Tools to Start With
- Google OR-Tools: your first baseline, and the routing library used above [5].
- HGS-CVRP and LKH-3: your quality ceiling, with published benchmark results [3].
- RL4CO: a library for neural combinatorial optimisation benchmarks.
- Gymnasium and PyTorch: for custom environments and policies, as in the job shop scheduling tutorial.
- CVRPLIB: benchmark instances and best-known solutions [4].
Verify each tool's current version and maintenance status before committing. Half the "state of the art" repositories in this field have not seen a commit since their paper.
Common Pitfalls
- Beating a weak baseline. Nearest neighbour loses to everything, and it lost by 33% here. That proves nothing.
- Ignoring generalisation. A policy trained on 50 customers may collapse at 500.
- Treating constraints as soft. Use action masking so the agent cannot build infeasible routes.
- Skipping training cost. A model that needed days of GPU time did not run "in milliseconds" in any honest accounting.
- Using unrealistic distances. Random Euclidean points differ from real road networks, which is why CVRPLIB numbers and yours will not match exactly.
- Comparing one run against one run. Guided local search is time-limited and varies between runs, so repeat before declaring a winner.
Most mistakes in this comparison are unfair comparisons, not bad algorithms.
Best Book to Read
| Book | Description | Get it |
|---|---|---|
| Vehicle Routing: Problems, Methods, and Applications | the standard reference on the savings heuristic, local search, metaheuristics and the benchmark conventions this post relies on, and the book that makes VRP papers readable. | View on Amazon |
As an Amazon Associate I earn from qualifying purchases. Links on this page are affiliate links, and I may earn a commission at no extra cost to you.
If your routing depends on predicted demand, pair it with a forecasting title, since the predict-then-optimise pattern is where most real fleets actually start.
Wrapping Up
On a single static problem, a well-tuned heuristic like HGS or LKH-3 usually beats a neural policy on quality. Neural methods win on speed, on batched repetition and in dynamic settings, and the strongest systems blend both.
So run one small experiment this week. Race a neural policy against OR-Tools on the same instances, and tune the solver first — otherwise you are racing a default, not a baseline. If the solver takes it, you saved a risky rewrite. If the policy wins on speed, you found a real use case, and your solver can congratulate it through gritted teeth.
Frequently Asked Questions
Can a neural policy beat OR-Tools on vehicle routing?
Rarely on a single static instance. In the benchmark for this post, OR-Tools reached within 3.6% of its own best 50-customer result in one second, and a neural constructive policy would have to beat that while paying for training. Neural methods win on batched inference speed and on dynamic problems, not on static quality.
Is Clarke-Wright still worth implementing?
Yes, and it is a better baseline than nearest neighbour. On the 200-customer instance measured here, a 13-millisecond Clarke-Wright implementation produced a solution 3.1% cheaper than a ten-second OR-Tools guided-local-search run. That says as much about baseline tuning as about the heuristic.
What is the attention model for VRP?
The encoder-decoder architecture from Kool, van Hoof and Welling that encodes customers with a transformer and decodes a route one node at a time, trained with policy gradients and a baseline. It is the reference point most later constructive methods compare against.
Does POMO improve on the attention model?
POMO exploits the symmetry that a route can start anywhere: it samples many rollouts from different first nodes and uses their shared reward as a baseline. That reduces variance and improves quality without a learned critic, and most modern constructive methods build on it.
When should I use a learned routing policy in production?
When requests arrive continuously, the fleet is already moving, and a re-plan must finish in milliseconds, or when you can batch thousands of similar instances on a GPU. For static daily planning with hard constraints, a solver plus a savings heuristic is still the safer engineering choice.
Sources
[1]Kool, van Hoof and Welling, Attention, Learn to Solve Routing Problems! — the attention encoder-decoder model and its policy-gradient training setup: arxiv.org/abs/1803.08475[2]Kwon et al., POMO: Policy Optimization with Multiple Optima for Reinforcement Learning — the multi-start rollout baseline used by most modern constructive methods: arxiv.org/abs/2010.16011[3]Vidal, HGS-CVRP: Hybrid Genetic Search for the CVRP — the reference implementation of the hybrid genetic search that dominates CVRP benchmarks: github.com/vidalt/HGS-CVRP[4]CVRPLIB — the standard CVRP instance sets, including the X set, with best-known solutions for comparison: vrp.galgos.inf.puc-rio.br[5]Google OR-Tools, Routing and vehicle routing — the routing library documentation, including the first-solution strategies compared in the benchmark: developers.google.com/optimization/routing