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

arXiv: https://arxiv.org/abs/2012.04461 · HTML: https://mlsanity.com/paper/2012.04461/

## Key facts

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

## Built on by (most cited first, 30 of 31)

- [DIMES: A Differentiable Meta Solver for Combinatorial Optimization Problems](https://mlsanity.com/paper/2210.04123/) (2022)
- [NeuroLKH: Combining Deep Learning Model with Lin-Kernighan-Helsgaun Heuristic for Solving the Traveling Salesman Problem](https://mlsanity.com/paper/2110.07983/) (2021)
- [Pointerformer: Deep Reinforced Multi-Pointer Transformer for the Traveling Salesman Problem](https://mlsanity.com/paper/2304.09407/) (2023)
- [H-TSP: Hierarchically Solving the Large-Scale Travelling Salesman Problem](https://mlsanity.com/paper/2304.09395/) (2023)
- [Searching Large Neighborhoods for Integer Linear Programs with Contrastive Learning](https://mlsanity.com/paper/2302.01578/) (2023)
- [Neural Combinatorial Optimization Algorithms for Solving Vehicle Routing Problems: A Comprehensive Survey with Perspectives](https://mlsanity.com/paper/2406.00415/) (2024)
- [Meta-Learning-Based Deep Reinforcement Learning for Multiobjective Optimization Problems](https://mlsanity.com/paper/2105.02741/) (2021)
- [Distilling Autoregressive Models to Obtain High-Performance Non-Autoregressive Solvers for Vehicle Routing Problems with Faster Inference Speed](https://mlsanity.com/paper/2312.12469/) (2023)
- [Reinforced Lin-Kernighan-Helsgaun Algorithms for the Traveling Salesman Problems](https://mlsanity.com/paper/2207.03876/) (2022)
- [Generalization in Deep RL for TSP Problems via Equivariance and Local Search](https://mlsanity.com/paper/2110.03595/) (2021)
- [DL-DRL: A double-level deep reinforcement learning approach for large-scale task scheduling of multi-UAV](https://mlsanity.com/paper/2208.02447/) (2022)
- [Graph Partitioning and Sparse Matrix Ordering using Reinforcement Learning and Graph Neural Networks](https://mlsanity.com/paper/2104.03546/) (2021)
- [Learning for routing: A guided review of recent developments and future directions](https://mlsanity.com/paper/2507.00218/) (2025)
- [A Hierarchical Destroy and Repair Approach for Solving Very Large-Scale Travelling Salesman Problem](https://mlsanity.com/paper/2308.04639/) (2023)
- [Learning Constraints-Based Adaptive Hypergraph Neural Networks for Solving Vehicle Routing Problems](https://mlsanity.com/paper/2503.10421/) (2025)
- [A New Constructive Heuristic driven by Machine Learning for the Traveling Salesman Problem](https://mlsanity.com/paper/2108.10224/) (2021)
- [An Edge-Aware Graph Autoencoder Trained on Scale-Imbalanced Data for Traveling Salesman Problems](https://mlsanity.com/paper/2310.06543/) (2023)
- [Unrealized Expectations: Comparing AI Methods vs Classical Algorithms for Maximum Independent Set](https://mlsanity.com/paper/2502.03669/) (2025)
- [Reinforced Hybrid Genetic Algorithm for the Traveling Salesman Problem](https://mlsanity.com/paper/2107.06870/) (2021)
- [Deep Reinforcement Learning for Multi-Truck Vehicle Routing Problems with Multi-Leg Demand Routes](https://mlsanity.com/paper/2401.08669/) (2024)
- [Learn to Tour: Operator Design For Solution Feasibility Mapping in Pickup-and-delivery Traveling Salesman Problem](https://mlsanity.com/paper/2404.11458/) (2024)
- [Bandit based Dynamic Candidate Edge Selection in Solving Traveling Salesman Problems](https://mlsanity.com/paper/2505.15862/) (2025)
- [Unsupervised Learning for the Elementary Shortest Path Problem](https://mlsanity.com/paper/2508.01557/) (2025)
- [Approximating Permutations with Neural Network Components for Travelling Photographer Problem](https://mlsanity.com/paper/2205.00242/) (2022)
- [An Unsupervised Learning Framework Combined with Heuristics for the Maximum Minimal Cut Problem](https://mlsanity.com/paper/2408.08484/) (2024)
- [Blackout DIFUSCO](https://mlsanity.com/paper/2502.05221/) (2025)
- [Constraints Matrix Diffusion based Generative Neural Solver for Vehicle Routing Problems](https://mlsanity.com/paper/2603.07568/) (2026)
- [The Traveling Thief Problem with Time Windows: Benchmarks and Heuristics](https://mlsanity.com/paper/2604.06724/) (2026)
- [A Unified Knowledge Embedded Reinforcement Learning-based Framework for Generalized Capacitated Vehicle Routing Problems](https://mlsanity.com/paper/2605.14416/) (2026)
- [Bridging the Gap between Sparse Matrix Reordering and Factorization: A Deep Learning Framework for Fill-in Reduction](https://mlsanity.com/paper/2605.17339/) (2026)

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