mlsanityData to 14 Oct 2026

Combining Reinforcement Learning with Lin-Kernighan-Helsgaun Algorithm for the Traveling Salesman Problem

arXiv 2012.04461 ↗First posted 8 Dec 2020cs.AI cs.LGcited by 31

Not on the map. Why?

Abstract (arXiv)

We address the Traveling Salesman Problem (TSP), a famous NP-hard combinatorial optimization problem. And we propose a variable strategy reinforced approach, denoted as VSR-LKH, which combines three reinforcement learning methods (Q-learning, Sarsa and Monte Carlo) with the well-known TSP algorithm, called Lin-Kernighan-Helsgaun (LKH). VSR-LKH replaces the inflexible traversal operation in LKH, and lets the program learn to make choice at each search step by reinforcement learning. Experimental results on 111 TSP benchmarks from the TSPLIB with up to 85,900 cities demonstrate the excellent performance of the proposed method.

Key facts. Cited by 31 papers in the map (data through 14 Oct 2026). First posted on arXiv 8 Dec 2020.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 6; 2022: 4; 2023: 6; 2024: 4; 2025: 6; 2026: 5.

31 papers.

Sort:

By area:

  1. 2022DIMES: A Differentiable Meta Solver for Combinatorial Optimization Problemscited by 129
  2. 2021NeuroLKH: Combining Deep Learning Model with Lin-Kernighan-Helsgaun Heuristic for Solving the Traveling Salesman Problemcited by 103
  3. 2023Pointerformer: Deep Reinforced Multi-Pointer Transformer for the Traveling Salesman Problemcited by 50
  4. 2023H-TSP: Hierarchically Solving the Large-Scale Travelling Salesman Problemcited by 43
  5. 2023Searching Large Neighborhoods for Integer Linear Programs with Contrastive Learningcited by 37
  6. 2024Neural Combinatorial Optimization Algorithms for Solving Vehicle Routing Problems: A Comprehensive Survey with Perspectivescited by 23
  7. 2021Meta-Learning-Based Deep Reinforcement Learning for Multiobjective Optimization Problemscited by 20
  8. 2023Distilling Autoregressive Models to Obtain High-Performance Non-Autoregressive Solvers for Vehicle Routing Problems with Faster Inference Speedcited by 19
  9. 2022Reinforced Lin-Kernighan-Helsgaun Algorithms for the Traveling Salesman Problemscited by 12
  10. 2021Generalization in Deep RL for TSP Problems via Equivariance and Local Searchcited by 9
  11. 2022DL-DRL: A double-level deep reinforcement learning approach for large-scale task scheduling of multi-UAVcited by 9
  12. 2021Graph Partitioning and Sparse Matrix Ordering using Reinforcement Learning and Graph Neural Networkscited by 8
19 more
  1. 2025Learning for routing: A guided review of recent developments and future directionscited by 7
  2. 2023A Hierarchical Destroy and Repair Approach for Solving Very Large-Scale Travelling Salesman Problemcited by 4
  3. 2025Learning Constraints-Based Adaptive Hypergraph Neural Networks for Solving Vehicle Routing Problemscited by 3
  4. 2021A New Constructive Heuristic driven by Machine Learning for the Traveling Salesman Problemcited by 2
  5. 2023An Edge-Aware Graph Autoencoder Trained on Scale-Imbalanced Data for Traveling Salesman Problemscited by 2
  6. 2025Unrealized Expectations: Comparing AI Methods vs Classical Algorithms for Maximum Independent Setcited by 2
  7. 2021Reinforced Hybrid Genetic Algorithm for the Traveling Salesman Problemcited by 1
  8. 2024Deep Reinforcement Learning for Multi-Truck Vehicle Routing Problems with Multi-Leg Demand Routescited by 1
  9. 2024Learn to Tour: Operator Design For Solution Feasibility Mapping in Pickup-and-delivery Traveling Salesman Problemcited by 1
  10. 2025Bandit based Dynamic Candidate Edge Selection in Solving Traveling Salesman Problemscited by 1
  11. 2025Unsupervised Learning for the Elementary Shortest Path Problemcited by 1
  12. 2022Approximating Permutations with Neural Network Components for Travelling Photographer Problemcited by 0
  13. 2024An Unsupervised Learning Framework Combined with Heuristics for the Maximum Minimal Cut Problemcited by 0
  14. 2025Blackout DIFUSCOcited by 0
  15. 2026Constraints Matrix Diffusion based Generative Neural Solver for Vehicle Routing Problemscited by 0
  16. 2026The Traveling Thief Problem with Time Windows: Benchmarks and Heuristicscited by 0
  17. 2026A Unified Knowledge Embedded Reinforcement Learning-based Framework for Generalized Capacitated Vehicle Routing Problemscited by 0
  18. 2026Bridging the Gap between Sparse Matrix Reordering and Factorization: A Deep Learning Framework for Fill-in Reductioncited by 0
  19. 2026MViewRouter: Internalizing Geometric Equivariance via Multi-view Alternating Attention for Combinatorial Routingcited by 0