Abstract
The Traveling Salesman Problem (TSP) is a classical NP-hard combinatorial optimization problem with significant practical applications. The Lin-Kernighan-Helsgaun (LKH) algorithm and its extension, LKH-3, represent the state-of-the-art in local search heuristics for TSP and its variants. These algorithms rely on candidate sets to maintain efficiency, typically determined by static measures like the $\alpha$-measure. In this work, we introduce Variable Strategy Reinforced LKH (VSR-LKH) and VSR-LKH-3, which integrate reinforcement learning (RL) to adaptively select candidate edges. By replacing inflexible traversal operations with a learning-based decision process, our methods significantly improve performance across standard TSP benchmarks and complex variants like the TSP with Time Windows (TSPTW) and Colored TSP (CTSP).
Introduction
The Traveling Salesman Problem is often considered the benchmark for combinatorial optimization. While exact solvers exist, they struggle with massive scales, making heuristics essential. The LKH algorithm is the gold standard, utilizing "k-opt" moves—swapping $k$ edges to find a shorter tour. However, LKH's efficiency depends on a "candidate set" for each city, traditionally ranked by static metrics. These static metrics fail to adapt to the specific topology discovered during a search. Recent deep-learning approaches, such as NeuroLKH, attempt to address this but face scalability issues due to the computational overhead of neural networks on instances with tens of thousands of cities.
Methodology
The core innovation of this research is treating the edge selection in the $k$-opt process as a Markov Decision Process (MDP). In this framework, the current city represents the state, selecting a city from the candidate set to form a new edge is the action, and the reduction in tour length or constraint violation is the reward.
Instead of a computationally expensive deep neural network, VSR-LKH utilizes a Q-table to store the "quality" of edges. To ensure robustness and escape local optima, the algorithm employs a Variable Strategy inspired by Variable Neighborhood Search. It cycles through three RL methods—Q-learning, Sarsa, and Monte Carlo—switching strategies if the solution fails to improve after a set number of iterations. This allows the search to leverage the different exploration and exploitation biases of each RL method.
For constrained variants like TSPTW and CTSP, VSR-LKH-3 employs a specialized reward function. This function prioritizes reducing constraint violations (e.g., missing a time window) over path length, ensuring the discovery of feasible solutions in highly restricted search spaces.
Experimental Results
The algorithms were evaluated on a massive suite of 236 benchmarks, including standard TSP instances with up to 85,900 cities.
- Superior Scalability: VSR-LKH significantly outperformed NeuroLKH on large-scale instances. Unlike deep-learning models that are limited by their training data, VSR-LKH learns "on the fly" for every new instance, maintaining the speed of LKH while gaining adaptivity.
- Robustness on Hard Instances: On 60 "hard" TSP instances, VSR-LKH found better or equal solutions in 159 out of 160 cases compared to standard LKH.
- New Best Solutions: For the Colored TSP (CTSP), VSR-LKH-3 discovered 12 new best-known solutions among 65 public instances, surpassing the previous state-of-the-art GMA algorithm.
- Efficiency: The RL overhead is minimal, allowing the algorithm to process the massive 85,900-city instance (pla85900) within reasonable time limits.
Conclusion
By marrying traditional reinforcement learning with the powerful LKH framework, VSR-LKH demonstrates that RL does not need to be "deep" to be effective. The use of Q-tables preserves the efficiency required for massive combinatorial problems while providing the adaptivity needed to outperform static heuristics. Future work will explore applying these reinforced local search techniques to even more complex variants, such as the Capacitated Vehicle Routing Problem (CVRP), where constraint handling is a primary challenge.
Summary updated