Destroy and Repair Using Hyper Graphs for Routing
This addresses the problem of suboptimal solutions in routing problems like TSP and CVRP for researchers and practitioners in optimization, though it is incremental as it builds on existing iterative methods.
The paper tackled the limitation of restricted neighborhood searches in iterative Neural Combinatorial Optimization methods for routing problems by proposing a Destroy-and-Repair framework based on Hyper-Graphs (DRHG), which achieved state-of-the-art performance on TSP with up to 10,000 nodes and strong generalization to real-world datasets.
Recent advancements in Neural Combinatorial Optimization (NCO) have shown promise in solving routing problems like the Traveling Salesman Problem (TSP) and Capacitated Vehicle Routing Problem (CVRP) without handcrafted designs. Research in this domain has explored two primary categories of methods: iterative and non-iterative. While non-iterative methods struggle to generate near-optimal solutions directly, iterative methods simplify the task by learning local search steps. However, existing iterative methods are often limited by restricted neighborhood searches, leading to suboptimal results. To address this limitation, we propose a novel approach that extends the search to larger neighborhoods by learning a destroy-and-repair strategy. Specifically, we introduce a Destroy-and-Repair framework based on Hyper-Graphs (DRHG). This framework reduces consecutive intact edges to hyper-edges, allowing the model to pay more attention to the destroyed part and decrease the complexity of encoding all nodes. Experiments demonstrate that DRHG achieves stateof-the-art performance on TSP with up to 10,000 nodes and shows strong generalization to real-world TSPLib and CVRPLib problems.