Overview
The Capacitated Vehicle Routing Problem (CVRP) adds a load limit to the standard vehicle-routing problem. Given a depot, a fleet of identical vehicles, and a set of customers awaiting deliveries, the goal is to minimize the fleet’s total travel distance. Every route must begin and end at the depot, every customer must be served exactly once, and no vehicle can exceed its capacity. CVRP is a generalization of the traveling salesman problem: TSP is the special case with one vehicle and no binding capacity constraint. It also inherits TSP’s difficulty—CVRP is NP-hard.
LKH is Keld Helsgaun’s implementation of the local-search method introduced by Lin and Kernighan in 1973. LKH was released in 2000 and extended to capacity-constrained routing in 2017; I benchmarked against version 3.0.13.
The question I spent five months exploring was Can a learned policy make LKH itself better?
LKH improves a tour by repeatedly perturbing it and then repairing the damage. LKH’s loop looks like this:
Imitation Learning
LKH generates its own training data. Every improvement trial produces a tour before the trial and a better tour after it, so a single solver run is a stream of labeled examples showing what a good move looks like. The first approach I tried was the direct one: train a network to imitate those moves.
Building the dataset
I generated 100-customer CVRP instances with RL4CO’s CVRPGenerator and ran LKH on each for 1,000 improvement trials with tracking enabled. Parsing the tracking logs yields before-and-after pairs: the tour LKH held at trial t, and the improved tour it held at trial t+1.
Each pair became a training example containing tensor representations of both tours, an adjacency matrix for each solution, and labels identifying which node connections changed between them.
The model
The policy is a hierarchical CVRP model. An N2S-style encoder processes node and edge features, three self-attention layers model the relationships between them, and a decoder produces a complete tour using either greedy or sampled decoding.
The model quickly overfit a single instance, confirming that the training pipeline worked. But offline accuracy only shows that a model can reproduce patterns in its training data. The real test is online performance: does LKH improve when the network becomes part of its search loop?
Putting it inside the solver
Answering that question required modifying LKH itself. I added a neural callback to the C source—nn_callback.o and FindTourWithNN.o—so LKH could send its current tour to the network at each trial and receive a proposal in return. If the proposal was cheaper than the incumbent, LKH accepted it. Otherwise, it fell back to its standard perturbation and merge process.
An early version accepted every network proposal unconditionally, producing a strange sawtooth pattern in the results. Correcting the acceptance rule removed that artifact, and the network began to outperform LKH on a few instances.
| Instance | LKH baseline | LKH + network | Δ |
|---|---|---|---|
| 0 | 1,316,407 | 1,301,936 | −1.1% |
| 1 | 1,881,923 | 1,877,234 | −0.2% |
| 2 | 1,592,379 | 1,600,879 | +0.5% |
| 3 | 1,554,463 | 1,571,381 | +1.1% |
| 4 | 1,759,140 | 1,788,439 | +1.7% |
| 5 | 1,263,915 | 1,269,911 | +0.5% |
| 6 | 1,565,304 | 1,562,655 | −0.2% |
| 7 | 1,809,913 | 1,820,645 | +0.6% |
Final tour cost after 1,000 trials. Lower is better, and the winning result is bold. The network won three of eight instances—promising, but ultimately misleading.
Eight instances were not enough to support a conclusion. Across 100 instances, the result was much less flattering.
Trying to close the gap
I trained three variants. A dual-model setup used one policy during early trials and another during later trials, based on the idea that improving a rough tour and polishing a strong one require different skills. A single “wide” model trained across trials 200–1,000 covered both phases. A third variant repeatedly fed the network its own output, refining the tour three times before returning it to LKH.
Why it lost
The failures were ultimately more informative than the wins, and they pointed to several specific problems.
Repeated refinement creates a distribution shift. The three-iteration refinement model delivered the clearest lesson. It was trained on pairs whose inputs were LKH-perturbed tours, but its own outputs do not follow that same distribution. By the second pass, the model is already processing data unlike anything it saw during training; the third pass compounds the problem. Its 25/0/75 win-tie-loss record reflects that mismatch.
The fallback rate stayed flat. If the network’s proposals improved over time, LKH should have needed to reject them less often. It did not.
Sampling did not improve greedy decoding. Generating eight samples and keeping the best one made performance worse. The model was trained with greedy decoding, while sampled decoding chooses nodes without looking ahead and can lead to capacity violations that the greedy policy avoids.
The two systems represent tours differently. The network uses node 0 as the depot and repeats it to separate routes. LKH instead creates depot copies—nodes 102, 103, 104, and so on. Every exchange between the two systems required a translation step, creating a persistent source of bugs.
All four problems trace back to the same architectural mismatch. Generating a complete, capacity-feasible tour for 100 customers is a much harder task than editing a few edges. The network had to meet that higher bar at every trial simply to compete with LKH.
Pivoting: learn the perturbation, not the tour
I stopped asking the network to produce a finished tour and returned to the original loop. The policy only needs to control the first step, from A to B. LKH is better at everything downstream, so it should keep doing that work.
Rather than starting from scratch, I initialized the policy with the imitation model. It already knew how to interpret a CVRP instance, encode a tour, and respect capacity constraints, even though it had never been trained to perturb. During training, the network processed each input twice: once with sampled decoding and once with greedy decoding. The reward difference became the advantage, so when the sampled tour outperformed the greedy tour, the policy increased the likelihood of those sampled actions.
This was the project’s most encouraging result. The policy was measurably learning to perturb: its improvement rate more than doubled, and its mean reward moved from clearly negative to positive. The run was noisy, and the learned policy still did not beat LKH’s own perturbation end to end, but it was the first experiment in which the learning signal moved decisively in the right direction.
Neural Deconstruction Search
The final approach reduced the action space even further. Instead of generating a perturbed tour, the network selected which customers to remove. It sampled M customers from the current best tour, a greedy repair heuristic reinserted them, and the resulting tour went to LKH.
In principle, this should be an easier problem to learn. The network decides only where to perturb, not how to reconstruct the tour, and greedy repair preserves most of the incumbent solution so each change remains local.
This approach did not work. The reward declined over training, and the semester ended before I could determine exactly why. My leading hypothesis is that the reward design was the problem: it measured raw LKH improvement rather than advantage over a greedy baseline. As a result, the signal may have been dominated by the difficulty of whichever instance the policy happened to sample.
Reflections
The headline result is negative, but it is a useful one.
Generating an entire solution is the wrong division of labor. A mature solver already enforces feasibility, repairs damage, and performs local search efficiently and reliably. Asking a network to reproduce that entire pipeline means competing with decades of solver development at every trial. A better approach is to let the network make one decision that the solver currently makes at random. The perturbation experiment—the only one whose learning curve clearly improved—supports that direction.
Offline imitation accuracy says little about online usefulness. The model clearly learned recognizable LKH behavior, yet it still lost 68 out of 100 online comparisons. The two metrics were nearly uncorrelated, and I relied on the offline result for longer than I should have.
The instrumentation was more valuable than the model. The flat fallback curve showed that the network was not gradually improving, while the refinement model’s collapse exposed the distribution shift. Without those diagnostics, I would have kept tuning hyperparameters even though the underlying problem was architectural.