Research map / Graph learning / Graph algorithms and clustering
Destroy and Repair Using Hyper-Graphs for Routing
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes DRHG, a supervised destroy-and-repair NCO framework that compresses consecutive intact tour edges into fixed hyper-edges so the repair model's input scales with destruction size rather than problem size.
Problem
Iterative neural routing solvers are limited to restricted neighborhoods (low-level operators or single-segment reconstruction), yielding suboptimal solutions on TSP and CVRP, especially at large scale.
Approach
Destroy the tour into segments and isolated nodes, reduce each intact segment to a fixed hyper-edge represented by its two endpoints, and train a light-encoder/heavy-linear-attention-decoder model with supervised learning to repair the reduced hyper-graph, enabling arbitrary-neighborhood reconnection with input size bounded by the destruction degree.
Key results
- On TSP100 DRHG (T=1000) reaches a 0.000% gap (±0.007%) versus 0.002% for LEHD RRC1000, and it is non-optimal on only 129 of 10,000 instances.
- DRHG-FT achieves 1.33% gap on TSP10K, 0.88% on TSP5K and 0.29% on TSP1K, outperforming SIL, which is trained separately per scale.
- On TSPLib, DRHG (T=1000) reports an average gap of 0.95% versus 1.59% for LEHD and 2.95% for BQ, and on CVRPLib 11.49% versus 2.36% for LEHD.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| fine-tune DRHG for large-scale TSP | DRHG · TSP1K, TSP5K, and TSP10K | Gap: 0.45% -> 0.29%; 2.05% -> 0.88%; 3.46% -> 1.33% | Helped |
| use DRHG instead of LEHD RRC1000 | routing solver · TSP200 and TSP500 | Gap: 0.0182% -> 0.010%; 0.167% -> 0.111% | Helped |
| use DRHG instead of LEHD RRC 1000 | routing solver · CVRP100 and CVRP200 | Gap: -0.11% -> -0.02%; -0.38% -> -0.16% | Mixed |
| use DRHG instead of LEHD RRC 1000 | routing solver · CVRP500 and CVRP1K | Gap: -0.35% -> 1.31%; -0.76% -> 7.66% | Hurt |
| use DRHG instead of LEHD R. 1K | routing solver · TSPLib all | optimality gap: 1.59% -> 0.95% | Helped |
| use DRHG instead of LEHD R. 1K | routing solver · CVRPLib All | optimality gap: 2.36% -> 11.49% | Hurt |
| use training sample size [20, 80] instead of [30, 70] (ablation) | DRHG · TSP200, TSP500, TSP1K, TSP5K, and TSP10K | Gap: 0.014% -> 0.0098%; 0.127% -> 0.113%; 0.268% -> 0.258%; 1.47% -> 1.42%; 3.06% -> 2.85% | Helped |
| use training sample size [10, 90] instead of [20, 80] (ablation) | DRHG · TSP200, TSP500, TSP1K, TSP5K, and TSP10K | Gap: 0.0098% -> 0.0149%; 0.113% -> 0.121%; 0.258% -> 0.271%; 1.42% -> 1.63%; 2.85% -> 3.384% | Hurt |
| use inference destruction size [20, 200] instead of [20, 100] (ablation) | DRHG · TSP200 and TSP1K to TSP10K | Gap: 0.0567% -> 0.0098%; 0.393% -> 0.258%; 1.70% -> 1.42%; 3.34% -> 2.85% | Helped |
| increase inference destruction size from [20, 200] to [20, 500] (ablation) | DRHG · TSP500 | Gap: 0.113% -> 0.111% | Helped |
| increase inference destruction size from [20, 200] to [20, 500] or [20,1000] (ablation) | DRHG · TSP1K, TSP5K, and TSP10K | Gap: 0.258% -> 0.309% / 0.449%; 1.42% -> 1.67% / 2.05%; 2.85% -> 3.07% / 3.46% | Hurt |
Surprising findings
- On CVRPLib, DRHG (11.49% average gap) is far behind LEHD (2.36%), though DRHG is competitive on CVRP100 and CVRP200.
Limitations
- The CVRP design does not fully realize the potential of DRHG, with weaker CVRP and CVRPLib results than LEHD.
- Model trained only on up to 100-node instances; repair quality degrades when destruction becomes too extensive.
Experimental setup
Datasets: TSP100 synthetic instances TSP1000 synthetic instances CVRP100 synthetic instances TSPLib CVRPLib
Benchmarks: TSP100 TSP200 TSP500 TSP1K TSP5K TSP10K CVRP100 CVRP200 CVRP500 CVRP1K TSPLib CVRPLib
Metrics: objective value optimality gap inference time
Baselines: Concorde LKH3 HGS POMO BQ DIMES DIFUSCO LEHD GLOP SIL DACT Learning 2-Opt
Builds on: LEHD DACT POMO
Closest papers by meaning
- Neural Solver Selection for Combinatorial Optimization (ICML 2025 · similarity 0.88)
- Improving Generalization of Neural Combinatorial Optimization for Vehicle Routing Problems via Test-Time Projection Learning (NeurIPS 2025 · similarity 0.87)
- Memory-Enhanced Neural Solvers for Routing Problems (NeurIPS 2025 · similarity 0.87)
- Neural Combinatorial Optimization for Robust Routing Problem with Uncertain Travel Times (NeurIPS 2024 · 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.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.