mlsanityData to 14 Oct 2026

NeuroLKH: Combining Deep Learning Model with Lin-Kernighan-Helsgaun Heuristic for Solving the Traveling Salesman Problem

arXiv 2110.07983 ↗First posted 15 Oct 2021cs.AI cs.LGcited by 103

Not on the map. Why?

Abstract (arXiv)

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).

Key facts. Cited by 103 papers in the map (data through 14 Oct 2026). Builds on 23 of its 37 references that are in the map. First posted on arXiv 15 Oct 2021.

Builds on

23 of 37 references.

References · 23

  1. 2015Deep Residual Learning for Image Recognitioncited by 52,096
  2. 2014Adam: A Method for Stochastic Optimizationcited by 37,240
  3. 2015Batch Normalization: Accelerating Deep Network Training by Reducing Internal Covariate Shiftcited by 7,005
  4. 2015Pointer Networkscited by 895
  5. 2018Attention, Learn to Solve Routing Problems!cited by 656
  6. 2018Machine Learning for Combinatorial Optimization: a Methodological Tour d'Horizoncited by 623
  7. 2016Neural Combinatorial Optimization with Reinforcement Learningcited by 608
  8. 2017Learning Combinatorial Optimization Algorithms over Graphscited by 561
  9. 2020POMO: Policy Optimization with Multiple Optima for Reinforcement Learningcited by 348
  10. 2017Residual Gated Graph ConvNetscited by 346
  11. 2018Reinforcement Learning for Solving the Vehicle Routing Problemcited by 333
  12. 2019An Efficient Graph Convolutional Network Technique for the Travelling Salesman Problemcited by 269
11 more
  1. 2018Learning to Perform Local Rewriting for Combinatorial Optimizationcited by 185
  2. 2019Learning Improvement Heuristics for Solving Routing Problemscited by 164
  3. 2020Generalize a Small Pre-trained Model to Arbitrarily Large TSP Instancescited by 162
  4. 2019Neural Large Neighborhood Search for the Capacitated Vehicle Routing Problemcited by 117
  5. 2020Learning 2-opt Heuristics for the Traveling Salesman Problem via Deep Reinforcement Learningcited by 100
  6. 2020Multi-Decoder Attention Model with Embedding Glimpse for Solving Vehicle Routing Problemscited by 100
  7. 2021Deep Policy Dynamic Programming for Vehicle Routing Problemscited by 94
  8. 2021Heterogeneous Attentions for Solving Pickup and Delivery Problem via Deep Reinforcement Learningcited by 36
  9. 2020Combining Reinforcement Learning with Lin-Kernighan-Helsgaun Algorithm for the Traveling Salesman Problemcited by 31
  10. 2020Learning to Solve Vehicle Routing Problems with Time Windows through Joint Attentioncited by 29
  11. 2020Generalization of Machine Learning for Problem Reduction: A Case Study on Travelling Salesman Problemscited by 17

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2022: 15; 2023: 18; 2024: 18; 2025: 30; 2026: 22.

103 papers.

Sort:

By area:

  1. 2023DIFUSCO: Graph-based Diffusion Solvers for Combinatorial Optimizationcited by 221
  2. 2023Neural Combinatorial Optimization with Heavy Decoder: Toward Large Scale Generalizationcited by 142
  3. 2022DIMES: A Differentiable Meta Solver for Combinatorial Optimization Problemscited by 129
  4. 2022Simulation-guided Beam Search for Neural Combinatorial Optimizationcited by 84
  5. 2023DeepACO: Neural-enhanced Ant Systems for Combinatorial Optimizationcited by 78
  6. 2023RL4CO: an Extensive Reinforcement Learning for Combinatorial Optimization Benchmarkcited by 71
  7. 2024MVMoE: Multi-Task Vehicle Routing Solver with Mixture-of-Expertscited by 70
  8. 2023Towards Omni-generalizable Neural Methods for Vehicle Routing Problemscited by 69
  9. 2022Learning Generalizable Models for Vehicle Routing Problems via Knowledge Distillationcited by 62
  10. 2022Pareto Set Learning for Neural Multi-objective Combinatorial Optimizationcited by 56
  11. 2023Searching Large Neighborhoods for Integer Linear Programs with Contrastive Learningcited by 37
  12. 2025Rethinking Light Decoder-based Solvers for Vehicle Routing Problemscited by 37
38 more
  1. 2022Learning to Solve Routing Problems via Distributionally Robust Optimizationcited by 31
  2. 2024Learning to Handle Complex Constraints for Vehicle Routing Problemscited by 29
  3. 2024Cross-Problem Learning for Solving Vehicle Routing Problemscited by 24
  4. 2023Meta-SAGE: Scale Meta-Learning Scheduled Adaptation with Guided Exploration for Mitigating Scale Shift on Combinatorial Optimizationcited by 23
  5. 2024Neural Combinatorial Optimization Algorithms for Solving Vehicle Routing Problems: A Comprehensive Survey with Perspectivescited by 23
  6. 2022Deep Reinforcement Learning Guided Improvement Heuristic for Job Shop Schedulingcited by 20
  7. 2022Learning to Solve Vehicle Routing Problems: A Surveycited by 16
  8. 2024Imperative Learning: A Self-supervised Neuro-Symbolic Learning Framework for Robot Autonomycited by 16
  9. 2025MTL-KD: Multi-Task Learning Via Knowledge Distillation for Generalizable Neural Vehicle Routing Solvercited by 13
  10. 2022Reinforced Lin-Kernighan-Helsgaun Algorithms for the Traveling Salesman Problemscited by 12
  11. 2022Neural Topological Ordering for Computation Graphscited by 12
  12. 2025Improving Generalization of Neural Combinatorial Optimization for Vehicle Routing Problems via Test-Time Projection Learningcited by 12
  13. 2025Preference Optimization for Combinatorial Optimization Problemscited by 11
  14. 2025Adversarial Generative Flow Network for Solving Vehicle Routing Problemscited by 10
  15. 2025Learning to Insert for Constructive Neural Vehicle Routing Solvercited by 10
  16. 2024Collaboration! Towards Robust Neural Methods for Routing Problemscited by 9
  17. 2022Learning to Solve Multiple-TSP with Time Window and Rejections via Deep Reinforcement Learningcited by 8
  18. 2024GREAT: A Graph Edge Attention Network for the Electric Vehicle Routing Problem with Asymmetric Costscited by 8
  19. 2024Learning to Optimize for Mixed-Integer Non-linear Programming with Feasibility Guaranteescited by 8
  20. 2023Neural Airport Ground Handlingcited by 7
  21. 2023Symmetric Replay Training: Enhancing Sample Efficiency in Deep Reinforcement Learning for Combinatorial Optimizationcited by 7
  22. 2025Learning for routing: A guided review of recent developments and future directionscited by 7
  23. 2025MOTIF: Multi-strategy Optimization via Turn-based Interactive Frameworkcited by 7
  24. 2025Hybrid-Balance GFlowNet for Solving Vehicle Routing Problemscited by 7
  25. 2025Multi-Task Vehicle Routing Solver via Mixture of Specialized Experts under State-Decomposable MDPcited by 7
  26. 2022DOGE-Train: Discrete Optimization on GPU with End-to-end Trainingcited by 6
  27. 2022Neural Networks for Local Search and Crossover in Vehicle Routing: A Possible Overkill?cited by 6
  28. 2023Too Big, so Fail? -- Enabling Neural Construction Methods to Solve Large-Scale Routing Problemscited by 6
  29. 2024Less Is More -- On the Importance of Sparsification for Transformers and Graph Neural Networks for TSPcited by 6
  30. 2023On Using Admissible Bounds for Learning Forward Search Heuristicscited by 5
  31. 2023Routing Arena: A Benchmark Suite for Neural Routing Solverscited by 5
  32. 2024Leader Reward for POMO-Based Neural Combinatorial Optimizationcited by 5
  33. 2025ELENA: Epigenetic Learning through Evolved Neural Adaptationcited by 5
  34. 2025EFormer: An Effective Edge-based Transformer for Vehicle Routing Problemscited by 5
  35. 2025Learning to Segment for Vehicle Routing Problemscited by 5
  36. 2023A Hierarchical Destroy and Repair Approach for Solving Very Large-Scale Travelling Salesman Problemcited by 4
  37. 2023NeuroCUT: A Neural Approach for Robust Graph Partitioningcited by 4
  38. 2024iMTSP: Solving Min-Max Multiple Traveling Salesman Problem with Imperative Learningcited by 4

50 most cited of 103 All 103 (JSON)