Research map / Reinforcement learning / Visual and representation RL
H-TSP: Hierarchically Solving the Large-Scale 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 the learned lower-level policy with LKH-3 (ablation) | H-TSP · Random1000, Random2000, Random5000, Random10000 | Gap (%): 6.62 -> 4.06; 7.39 -> 5.01; 7.10 -> 5.10; 7.32 -> 5.57 | Helped |
| Replace the learned lower-level policy with LKH-3 (ablation) | H-TSP · Random1000, Random2000, Random5000, Random10000 | Time (s): 0.33 -> 3.53; 0.72 -> 6.88; 1.66 -> 15.12; 3.32 -> 27.94 | Hurt |
| Remove the visited-node fragment from sub-problem generation (ablation) | H-TSP · Random1000 | Gap (%): 6.76 -> 7.42 (+0.66) | Hurt |
| Remove the k-NN graph from sub-problem generation (ablation) | H-TSP · Random1000 | Gap (%): 6.76 -> 7.69 (+0.93) | Hurt |
| Remove joint training of the upper- and lower-level policies (ablation) | H-TSP · Random1000 | Gap (%): 6.76 -> 7.53 (+0.77) | Hurt |
| Remove lower-level warm-up training (ablation) | H-TSP · Random1000 | Gap (%): 6.76 -> 27.05 (+20.29) | Hurt |
| Replace the upper-level policy with a random policy (ablation) | H-TSP · Four TSP datasets | Optimality gap | Hurt |
| Replace the lower-level policy with Farthest Insertion (ablation) | H-TSP · Four TSP datasets | Optimality gap | Hurt |
Closest papers by meaning
- Generalize a Small Pre-trained Model to Arbitrarily Large TSP Instances (AAAI 2021 · similarity 0.90)
- Combining Reinforcement Learning with Lin-Kernighan-Helsgaun Algorithm for the Traveling Salesman Problem (AAAI 2021 · similarity 0.89)
- Pointerformer: Deep Reinforced Multi-Pointer Transformer for the Traveling Salesman Problem (AAAI 2023 · similarity 0.89)
- DualOpt: A Dual Divide-and-Optimize Algorithm for the Large-scale Traveling Salesman Problem (AAAI 2025 · similarity 0.88)
- Position: Rethinking Post-Hoc Search-Based Neural Approaches for Solving Large-Scale Traveling Salesman Problems (ICML 2024 · similarity 0.88)
- GLOP: Learning Global Partition and Local Construction for Solving Large-Scale Routing Problems in Real-Time (AAAI 2024 · similarity 0.87)
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.