Source-linked AI summary
NeuroLKH: Combining Deep Learning Model with Lin-Kernighan-Helsgaun Heuristic for Solving the Traveling Salesman Problem
Liang Xin, Wen Song, Zhiguang Cao, Jie Zhang
TL;DR
Large-scale TSP is difficult because exact methods are impractical and learned solvers have remained weaker than LKH. NeuroLKH trains a Sparse Graph Network to supply LKH with edge scores and node penalties, and experiments report consistent improvements, larger-size generalization, and extensions to other routing problems.
Problem
Exact TSP solving is impractical at large scale, while existing deep learning solvers remain weaker than LKH and generally limited to relatively small problems.
Method
NeuroLKH jointly trains a Sparse Graph Network with supervised edge-score learning and unsupervised node-penalty learning to construct candidates and transform edge distances for LKH.
Results
NeuroLKH consistently and significantly improves baseline algorithms across training sizes and time limits, generalizes to larger sizes and TSPLIB, and applies to CVRP, PDP, and CVRPTW.
Takeaways & Limitations
Combining learned routing patterns with LKH enables a single model to guide strong heuristic search across sizes, distributions, and several routing problems.
Takeaways & Limitations
Neither LKH nor NeuroLKH guarantees that every edge in the optimal tour appears in the candidate set, although multiple trials may still find optimal solutions.
Abstract
from arXiv · showhide
We present NeuroLKH, a novel algorithm that combines deep learning with the strong traditional heuristic Lin-Kernighan-Helsgaun (LKH) for solving Traveling Salesman Problem. Specifically, we train a Sparse Graph Network (SGN) with supervised learning for edge scores and unsupervised learning for node penalties, both of which are critical for improving the performance of LKH. Based on the output of SGN, NeuroLKH creates the edge candidate set and transforms edge distances to guide the searching process of LKH. Extensive experiments firmly demonstrate that, by training one model on a wide range of problem sizes, NeuroLKH significantly outperforms LKH and generalizes well to much larger sizes. Also, we show that NeuroLKH can be applied to other routing problems such as Capacitated Vehicle Routing Problem (CVRP), Pickup and Delivery Problem (PDP), and CVRP with Time Windows (CVRPTW).
1 Introduction
TSP is important in applications, but exact methods are impractical at large scale and learned solvers remain weaker than LKH. NeuroLKH combines learning with LKH to improve search, generalize across sizes and distributions, and extend to other routing problems.
- Motivation: Exact TSP methods have exponential worst-case complexity, while heuristics seek near-optimal solutions with lower complexity for practical applications.The passage contrasts optimality guarantees with practical performance goals.
- Motivation: Deep learning methods learn instance patterns but remain substantially weaker than strong traditional heuristics and are generally limited to relatively small problems.Traditional heuristics are manually designed using expert knowledge.
- Approach: NeuroLKH combines a Sparse Graph Network with LKH to learn edge scores and node penalties for candidate generation and distance transformation.The learned penalties avoid iterative per-instance optimization, while edge scores improve the candidate set.
- Generalization: One network trained across a wide range of sizes generalizes to substantially larger problems with minutes of unsupervised offline fine-tuning.The fine-tuning adjusts node-penalty scales for different sizes.
- Results: NeuroLKH improves baseline algorithms across training sizes and larger unseen sizes, generalizes to TSPLIB distributions, and extends to CVRP, PDP, and CVRPTW.The reported routing extensions use generated test datasets and traditional benchmarks.
2 Related works
Prior learning-based routing methods remain far from LKH, while NeuroLKH differs by learning patterns that improve LKH rather than replacing its search or selecting within its original candidates. It substantially outperforms VSR-LKH on training-distribution instances and remains comparable on TSPLIB.
- Existing learning methods: Deep learning routing work has focused on construction heuristics or learning actions that improve existing solutions, yet performance remains far from LKH.Examples include sequential node selection, edge selection, and learned 2-opt decisions.
- Generalization: A method that transfers from fixed-size small graphs to larger problems remains inferior to LKH and deteriorates rapidly as problem size increases.It samples small subgraphs, infers results, and merges them.
- Comparison with VSR-LKH: VSR-LKH uses reinforcement learning during each instance search and guides edge selection within an edge candidate set generated by original LKH.This differs from NeuroLKH's learned patterns and learned candidate-set construction.
- Comparison with VSR-LKH: NeuroLKH significantly outperforms VSR-LKH across training-distribution settings, especially under short time limits, while achieving similar TSPLIB performance.TSPLIB contains node distributions very different from NeuroLKH's training distributions.
3 Preliminaries: LKH algorithm
LKH repeatedly improves tours through λ-opt exchanges, using a precomputed candidate set to restrict and prioritize search. Minimum 1-Tree sensitivity and optimized node penalties improve candidate quality and transform distances while preserving the optimal tour.
- LKH search: LKH performs multiple trials from random tours and iteratively applies improving λ-opt exchanges until no such exchange remains.The tour is replaced whenever an exchange reduces its distance.
- Candidate-set construction: LKH creates candidate sets using α-measures derived from Minimum Spanning Tree sensitivity analysis.The TSP graph is represented as an undirected weighted graph, and a spanning tree has |V| − 1 edges without cycles.
- Candidate-set search: The edge candidate set contains the k smallest α-measure edges per node and restricts which edges can be added during λ-opt search.Edges with smaller α-measures receive higher search priority; k defaults to 5.
- Penalty transformation: Adding node penalties transforms edge distances as c_i,j = s_i,j + π_i + π_j without changing the optimal TSP tour, while changing the Minimum 1-Tree.The transformed distances support candidate-set construction and search guidance.
- Penalty optimization: Subgradient optimization maximizes a lower bound by pushing Minimum 1-Tree node degrees toward 2, improving α-measures and transformed distances.The update is π_τ+1 = π_τ + t_τ(d_τ − 2).
4 The proposed NeuroLKH algorithm
NeuroLKH combines a Sparse Graph Network with LKH to learn edge scores and node penalties, replacing hand-crafted candidate generation and costly instance-specific optimization. Its outputs guide edge-distance transformation, candidate selection, and repeated LKH search.
- NeuroLKH addresses LKH limitations by learning edge scores and node penalties with a Sparse Graph Network.The edge scores create the candidate set, while node penalties support edge-distance transformation.
- Sparse Graph Network: The SGN represents each TSP instance as a sparse directed graph containing the γ shortest outgoing edges per node.Sparsification is described as important for training on large instances and generalizing to larger sizes.
- Sparse Graph Network: The SGN uses an encoder with two decoders for edge scores and node penalties, trained jointly with supervised and unsupervised objectives.The combined loss is L = Lβ + ηπLπ, balancing the edge and node-penalty losses.
- NeuroLKH algorithm: NeuroLKH converts SGN outputs into an edge-distance transformation and a top-k candidate set before running multiple LKH trials.The pipeline converts the instance, predicts β and π, transforms distances, creates candidates, and searches with LKH.
- NeuroLKH algorithm: The transformed distance is c_i,j = s_i,j + π_i + π_j, while larger edge scores receive higher priority during LKH exchanges.The transformation preserves the optimal solution tour, and candidate edges are selected by the top-k scores for each node.
- NeuroLKH algorithm: Using a trained SGN makes inference faster than LKH’s per-instance subgradient optimization and replaces hand-crafted search guidance with learned patterns.The learned transformation and candidate set guide LKH trials through a forward pass of the model.
5 Experiments
Experiments compare NeuroLKH with LKH and VSR-LKH on TSP across training and larger generalization sizes, then evaluate extensions to CVRP, PDP, and CVRPTW. NeuroLKH consistently improves solution quality and is especially effective under short time limits.
- Comparison on training sizes: NeuroLKH significantly and consistently outperforms LKH and VSR-LKH across TSP training sizes of 100, 200, and 500 nodes and different time limits.Optimality gaps are reduced by at least an order of magnitude in most cases.
- Generalization analysis on larger sizes: NeuroLKH generalizes to TSP sizes of 1000, 2000, and 5000 nodes, with significant and consistent improvement over the baselines.Edge scores generalize directly, while node penalties require a simple fine-tuning step for larger instances.
- Comparison on training sizes: NeuroLKH reaches good TSP solutions faster, converges to better solutions eventually, and provides particularly substantial gains under short time limits.The comparison tracks objective values after each trial against running time; NeuroLKH also reduces computational time at equal objective value.
- Generalization to TSPLIB benchmark: On 24 hard TSPLIB instances, NeuroLKH finds optimal solutions 6.13 times on average versus 3.75 times for LKH, while VSR-LKH reaches 6.42 times.A mixed-distribution model, NeuroLKH_M, reaches 6.79 times on average for the hard instances and 8.74 times across all 72 instances.
- Performance on traditional benchmarks: On traditional benchmarks, NeuroLKH improves average performance on 38, 38, and 31 of 43 CVRPLIB instances under 100, 1000, and 10000-trial time limits, respectively.On Solomon R2-type instances, it outperforms LKH in 32 of 33 settings.
6 Conclusion
NeuroLKH combines a Sparse Graph Network with LKH to guide candidate-edge generation and distance transformation. Experiments show strong generalization across larger TSP instances, node distributions, and several routing problems, while demand and time-window distribution transfer remains limited.
- NeuroLKH trains one Sparse Graph Network to predict edge scores and node penalties for guiding LKH.Edge scores generate the edge candidate set, while node penalties transform edge distances.
- NeuroLKH consistently improves over baseline algorithms across different time limits and generalizes to larger graph sizes and varied node distributions.
- NeuroLKH also applies effectively to CVRP, PDP, and CVRPTW.
- For CVRP and CVRPTW, larger-size generalization does not directly extend to unseen demand and time-window distributions without training.The paper identifies this distribution-transfer limitation as future research.
A Experiments for TSP
The TSP experiments evaluate candidate-edge quality, parameter settings, comparisons with deep-learning methods, and generalization across problem sizes. NeuroLKH retains strong candidate coverage and substantially outperforms competing methods while scaling to much larger instances.
- 0.68% and 0.67% of optimal edges are missed by LKH candidate sets for TSP100 and TSP500, respectively.
- γ = 20 leaves only 0.01% of training-dataset optimal edges missing from NeuroLKH’s sparse graph.Experiments compare γ values of 10, 20, and 30.
- The node-penalty output is bounded to [−10, 10], matching observed penalty ranges for training instances with coordinates between 0 and 1.The experiments use C = 10.
- NeuroLKH significantly outperforms other deep-learning methods on TSP100 and generalizes to TSP instances with up to 5000 nodes.Most compared methods can hardly handle problems above 100 nodes, while one large-problem exception remains inferior to LKH.
B Experiments for TSPLIB
TSPLIB experiments compare LKH, VSR-LKH, NeuroLKH, and a mixed-distribution NeuroLKH model across repeated runs. The evaluation records optimal-solution success, tour quality, and runtime for each instance.
- NeuroLKH is trained on uniformly distributed-node instances, while NeuroLKH_M additionally uses clustered and mixed node distributions.
- The experiments run each algorithm 10 times per instance with the number of trials set to the number of nodes.
- The reported measures include optimal-solution success times, best and average tour distance, and average running time.The optimal tour distance is shown under each instance name.
C Experiments for Other Routing Problems
NeuroLKH is evaluated on CVRP, PDP, and CVRPTW against LKH under matched time limits. It improves solution quality across sizes and limits, with nearly all reported differences statistically significant.
- PDP requires visiting each pickup before its paired delivery, while CVRP and CVRPTW involve routes with additional vehicle-capacity or time-window constraints.These problems extend routing beyond the TSP setting.
- NeuroLKH and LKH show similar performance trends across CVRP, PDP, and CVRPTW under the longest tested time limits.
- More than 99% confidence supports almost all NeuroLKH improvements over LKH across sizes and time limits.Exceptions occur for the smallest problem sizes at the longest time limits, including 77.9% confidence for CVRPTW40.
D Experiments on CVRPLIB and Solomon Benchmark
The experiments evaluate NeuroLKH on CVRPLIB and Solomon benchmark instances, using diverse CVRP and CVRPTW distributions and repeated comparisons with LKH.
- CVRPLIB: CVRPLIB experiments use CVRP instances combining three depot-positioning, three customer-positioning, and seven demand distributions.The training set covers 101–300 nodes, with approximately 120,000 generated instances in total.
- Solomon Benchmark: Solomon experiments use CVRPTW instances with 100 customers and varied time-window distributions.The R2-type benchmark is used, with uniformly generated coordinates, Gaussian demands, fixed service times, and multiple time-window parameter settings.
- Evaluation Protocol: Both LKH and NeuroLKH are run 100 times per instance under time limits corresponding to LKH runs with 100, 1000, and 10000 trials.The evaluation reports average running time, best and average tour distance, and optimal-solution success counts.