Presented at AAAI-25, DRHG (Destroy and Repair using Hyper-Graphs) is a novel iterative framework designed to solve large-scale routing problems like the Traveling Salesman Problem (TSP). By representing partially destroyed solutions as condensed hyper-graphs, DRHG enables neural networks to search significantly larger "neighborhoods" than previous methods. This approach achieves state-of-the-art performance on problems with up to 10,000 nodes.
Scaling Neural Combinatorial Optimization
Routing problems, including the Traveling Salesman Problem (TSP) and Capacitated Vehicle Routing Problem (CVRP), are NP-hard yet fundamental to logistics and manufacturing. Traditional Neural Combinatorial Optimization (NCO) methods typically fall into two categories:
- Non-iterative (One-shot): These build solutions from scratch. While fast, they struggle with large-scale instances because early errors can propagate through the entire tour.
- Iterative (Local Search): These improve existing solutions. However, most neural iterative solvers are limited to small "neighborhoods" (e.g., simple node swaps).
The central challenge addressed by DRHG is how to allow a neural network to efficiently search a large neighborhood—re-routing many nodes simultaneously—without being overwhelmed by the complexity of the full graph.
Methodology: The Destroy-and-Repair Framework
DRHG utilizes a Destroy-and-Repair framework powered by a unique Hyper-Graph Representation.
The process consists of four main steps:
- Destroy: A portion of an existing solution is "destroyed" by removing edges, resulting in several intact segments and a set of isolated nodes.
- Hyper-Graph Reduction: This is the core innovation. Instead of processing every node, the model treats each intact segment as a single "hyper-edge," considering only the two endpoints. This drastically reduces the input size for the neural network.
- Neural Repair: A Transformer-based model, featuring a light encoder and a heavy decoder with Linear Attention, learns to connect isolated nodes and hyper-edges into a new, complete tour.
- Training: The model is trained via Supervised Learning (SL) using high-quality solutions from classical solvers (e.g., Concorde for TSP and HGS for CVRP) as ground truth.
Scale Invariance and Efficiency
By reducing segments to hyper-edges, the input size depends on the amount of destruction rather than the total problem size. This allows a model trained on 100 nodes to effectively repair a 10,000-node tour. Furthermore, the hyper-graph formulation focuses the model's "attention budget" solely on the parts of the problem that require fixing.
Experimental Results
The researchers evaluated DRHG on synthetic and real-world benchmarks (TSPLib and CVRPLib) with instances ranging from 100 to 10,000 nodes.
Key findings include:
- State-of-the-Art Performance: On TSP100, DRHG achieved a 0.000% optimality gap. For massive TSP10,000 instances, it maintained a 1.33% gap, significantly outperforming recent neural methods like SIL (2.23%) and LEHD (12.50%).
- Computational Efficiency: DRHG is substantially faster than exact solvers. For TSP1000, it finds near-optimal solutions in approximately 1.7 minutes.
- Robust Generalization: The model demonstrated strong performance on real-world libraries, indicating it learns fundamental routing principles rather than just memorizing synthetic data.
- High Precision: On TSP100, DRHG produced non-optimal solutions in only 1.29% of cases, compared to 18.22% for the next best competitor, BQ.
Conclusion and Future Work
DRHG demonstrates that hyper-graph reduction is a powerful tool for scaling NCO to massive problems. While highly effective for TSP, its performance on CVRP is slightly less dominant due to additional constraints like vehicle capacity. Future research may explore "learned" destruction strategies to identify weak parts of a tour more effectively or apply hyper-graph reduction to other combinatorial domains like scheduling and circuit design.
Summary updated