Research map / Graph learning / Graph algorithms and clustering
NeuroLKH: Combining Deep Learning Model with Lin-Kernighan-Helsgaun Heuristic for Solving the Traveling Salesman Problem
Liang Xin, Wen Song, Zhiguang Cao, Jie Zhang
Read the paperCheck your idea against 137,217 papers
AI-extracted. The measured effects below were read by AI from the paper's full text (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 |
|---|---|---|---|
| Use SGN-predicted edge scores and node penalties to guide LKH | LKH · TSP 100 | Obj: 7.755071 -> 7.753332 | Improved |
| Use SGN-predicted edge scores and node penalties to guide LKH | LKH · TSP 5000 | Obj: 51.025519 -> 50.965382 | Improved |
| Use SGN edge-score candidate sets to guide LKH | LKH · CVRP 500 | Obj: 42.1621 -> 41.7311 | Improved |
| Use SGN edge-score candidate sets to guide LKH | LKH · PDP 200 | Obj: 13.8390 -> 13.6246 | Improved |
| Use SGN edge-score candidate sets to guide LKH | LKH · CVRPTW 200 | Obj: 26.1757 -> 25.4000 | Improved |
| Increase sparse graph degree from 10 to 20 (ablation) | NeuroLKH · TSP500 | percentage of optimal edges missed in the candidate set: 0.643% -> 0.209% | Improved |
| Increase sparse graph degree from 20 to 30 (ablation) | NeuroLKH · TSP500 | average ranking of optimal edges: 1.646 -> 1.640 | Improved |
| Train on a mixture of uniform and clustered node distributions instead of uniform-only (ablation) | NeuroLKH · TSPLIB hard instances | optimal solutions found on average: 6.13 -> 6.79 | Improved |
| Train on a mixture of uniform and clustered node distributions instead of uniform-only (ablation) | NeuroLKH · TSPLIB all 72 instances | optimal solutions found on average: 7.92 -> 8.74 | Improved |
| Increase sparse graph degree beyond 20 (ablation) | NeuroLKH · TSP500 | average ranking of optimal edges: 1.646 -> 1.640 | No clear effect |
| Use edge scores without fine-tuning node penalties for varied node distributions | NeuroLKH · TSPLIB easy instances | optimal solutions found: fails to solve 11 of the 48 easy instances optimally | Mixed |
Closest papers by meaning
- Improving Generalization of Neural Combinatorial Optimization for Vehicle Routing Problems via Test-Time Projection Learning (NeurIPS 2025 · similarity 0.88)
- Destroy and Repair Using Hyper-Graphs for Routing (AAAI 2025 · similarity 0.87)
- CaDA: Cross-Problem Routing Solver with Constraint-Aware Dual-Attention (ICML 2025 · similarity 0.87)
- GLOP: Learning Global Partition and Local Construction for Solving Large-Scale Routing Problems in Real-Time (AAAI 2024 · similarity 0.86)
- Neural Solver Selection for Combinatorial Optimization (ICML 2025 · similarity 0.86)
- Neural Combinatorial Optimization for Robust Routing Problem with Uncertain Travel Times (NeurIPS 2024 · similarity 0.86)
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.
