Research map / Reinforcement learning / Visual and representation RL
Combining Reinforcement Learning with Lin-Kernighan-Helsgaun Algorithm for the Traveling Salesman Problem
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's title only (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Replace LKH candidate ordering with VSR-LKH's variable-strategy reinforcement learning | LKH · TSPLIB hard instances | average tour length: 26131.6 -> 26130.4 (kroB150); 57251.1 -> 57214.5 (u1817) | Helped |
| Replace the α-value with the fixed initial Q-value combining distance and α-value (ablation) | LKH (FixQ-LKH) · 27 hard TSPLIB instances | cumulative solution gap | Helped |
| Use Q-learning to adjust the initial Q-values during search (ablation) | FixQ-LKH · 27 hard TSPLIB instances | cumulative solution gap | Helped |
| Use Q-learning, Sarsa, or Monte Carlo individually to reinforce LKH (ablation) | LKH · 27 hard TSPLIB instances | cumulative solution gap | Helped |
| Switch among Q-learning, Sarsa, and Monte Carlo instead of using one strategy (ablation) | LKH · 27 hard TSPLIB instances | cumulative solution gap | Helped |
| Remove Monte Carlo from the variable-strategy method (ablation) | VSR-LKH · gr431, si535, and u1817 | solution quality | Hurt |
| Use Monte Carlo alone rather than a variable strategy (ablation) | LKH · large-scale TSPLIB instances | solution quality | Hurt |
| Vary the reinforcement-learning parameters from their defaults (ablation) | VSR-LKH · 27 hard TSPLIB instances | cumulative solution gap | No clear effect |
| Use the reinforced search rather than LKH during the initial iterations (ablation) | VSR-LKH variants · u574, u1060, u1817, fnl4461, rl5934, and rl11849 | gap to optimal solution over runtime | Mixed |
| Apply VSR-LKH rather than LKH with the same runtime limit | LKH · pla33810 and pla85900 | best tour length: 66061689 -> 66049981 (pla33810); 142418173 -> 142393330 (pla85900) | Helped |
Closest papers by meaning
- H-TSP: Hierarchically Solving the Large-Scale Traveling Salesman Problem (AAAI 2023 · similarity 0.89)
- Generalize a Small Pre-trained Model to Arbitrarily Large TSP Instances (AAAI 2021 · similarity 0.87)
- Unify ML4TSP: Drawing Methodological Principles for TSP and Beyond from Streamlined Design Space of Learning and Search (ICLR 2025 · similarity 0.87)
- SplitNet: A Reinforcement Learning Based Sequence Splitting Method for the MinMax Multiple Travelling Salesman Problem (AAAI 2023 · similarity 0.87)
- Preference Optimization for Combinatorial Optimization Problems (ICML 2025 · similarity 0.86)
- DualOpt: A Dual Divide-and-Optimize Algorithm for the Large-scale Traveling Salesman Problem (AAAI 2025 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.