Destroy and Repair Using Hyper Graphs for Routing

• URL: http://arxiv.org/abs/2502.16170v1
• Date: Sat, 22 Feb 2025 10:04:58 GMT
• Title: Destroy and Repair Using Hyper Graphs for Routing
• Authors: Ke Li, Fei Liu, Zhengkun Wang, Qingfu Zhang,
• Abstract summary: We introduce a Destroy-and-Repair framework based on Hyper-Graphs.<n>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.
• Score: 14.391263435675587
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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.

Related papers

• TuneNSearch: a hybrid transfer learning and local search approach for solving vehicle routing problems [43.89334324926175]
  TuneNSearch is a hybrid transfer learning and local search approach for addressing different variants of vehicle routing problems (VRP) We first pre-train a reinforcement learning model on the multi-depot VRP, followed by a short fine-tuning phase to adapt it to different variants. Results show that TuneNSearch outperforms many existing state-of-the-art models trained for each VRP variant, requiring only one-fifth of the training epochs.
  arXiv  Detail & Related papers  (2025-03-16T21:34:11Z)
• Towards Constraint-Based Adaptive Hypergraph Learning for Solving Vehicle Routing: An End-to-End Solution [4.965709007367529]
  Vehicle routing problems are characterized by vast solution spaces and intricate constraints. This study introduces a novel end-to-end framework that combines constraint-oriented hypergraphs with reinforcement learning.
  arXiv  Detail & Related papers  (2025-03-13T14:42:44Z)
• L2R: Learning to Reduce Search Space for Generalizable Neural Routing Solver [12.396576646539252]
  Constructive neural optimization (NCO) has attracted growing research attention due to its ability to solve complex routing problems without relying on handcrafted rules. Existing NCO methods face challenges in generalizing to large-scale problems due to high computational complexity and inefficient capture of structural patterns. We propose a novel learning-based search space reduction method that adaptively selects a small set of promising candidate nodes at each step of the constructive NCO process.
  arXiv  Detail & Related papers  (2025-03-05T03:25:09Z)
• An Efficient Learning-based Solver Comparable to Metaheuristics for the Capacitated Arc Routing Problem [67.92544792239086]
  We introduce an NN-based solver to significantly narrow the gap with advanced metaheuristics. First, we propose direction-aware facilitating attention model (DaAM) to incorporate directionality into the embedding process. Second, we design a supervised reinforcement learning scheme that involves supervised pre-training to establish a robust initial policy.
  arXiv  Detail & Related papers  (2024-03-11T02:17:42Z)
• Spatial-temporal-demand clustering for solving large-scale vehicle routing problems with time windows [0.0]
  We propose a decompose-route-improve (DRI) framework that groups customers using clustering. Its similarity metric incorporates customers' spatial, temporal, and demand data. We apply pruned local search (LS) between solved subproblems to improve the overall solution.
  arXiv  Detail & Related papers  (2024-01-20T06:06:01Z)
• Robust Stochastically-Descending Unrolled Networks [85.6993263983062]
  Deep unrolling is an emerging learning-to-optimize method that unrolls a truncated iterative algorithm in the layers of a trainable neural network.<n>We show that convergence guarantees and generalizability of the unrolled networks are still open theoretical problems.<n>We numerically assess unrolled architectures trained under the proposed constraints in two different applications.
  arXiv  Detail & Related papers  (2023-12-25T18:51:23Z)
• GLOP: Learning Global Partition and Local Construction for Solving Large-scale Routing Problems in Real-time [17.450373393248984]
  GLOP is a unified hierarchical framework that efficiently scales toward large-scale routing problems. For the first time, we hybridize non-autoregressive neurals for coarse-grained problem partitions and autoregressive neurals for fine-grained route constructions. Experiments show that GLOP achieves competitive and state-of-the-art real-time performance on large-scale routing problems.
  arXiv  Detail & Related papers  (2023-12-13T15:46:58Z)
• Iterative Soft Shrinkage Learning for Efficient Image Super-Resolution [91.3781512926942]
  Image super-resolution (SR) has witnessed extensive neural network designs from CNN to transformer architectures. This work investigates the potential of network pruning for super-resolution iteration to take advantage of off-the-shelf network designs and reduce the underlying computational overhead. We propose a novel Iterative Soft Shrinkage-Percentage (ISS-P) method by optimizing the sparse structure of a randomly network at each and tweaking unimportant weights with a small amount proportional to the magnitude scale on-the-fly.
  arXiv  Detail & Related papers  (2023-03-16T21:06:13Z)
• Decision Diagram-Based Branch-and-Bound with Caching for Dominance and Suboptimality Detection [9.175779296469194]
  This paper presents new ingredients to speed up the search by exploiting the structure of dynamic programming models. The key idea is to prevent the repeated expansion of nodes corresponding to the same dynamic programming states by querying expansion thresholds cached throughout the search. Experiments show that the pruning brought by this caching mechanism allows significantly reducing the number of nodes expanded by the algorithm.
  arXiv  Detail & Related papers  (2022-11-22T10:18:33Z)
• RDRN: Recursively Defined Residual Network for Image Super-Resolution [58.64907136562178]
  Deep convolutional neural networks (CNNs) have obtained remarkable performance in single image super-resolution. We propose a novel network architecture which utilizes attention blocks efficiently.
  arXiv  Detail & Related papers  (2022-11-17T11:06:29Z)
• Edge Rewiring Goes Neural: Boosting Network Resilience via Policy Gradient [62.660451283548724]
  ResiNet is a reinforcement learning framework to discover resilient network topologies against various disasters and attacks. We show that ResiNet achieves a near-optimal resilience gain on multiple graphs while balancing the utility, with a large margin compared to existing approaches.
  arXiv  Detail & Related papers  (2021-10-18T06:14:28Z)
• Phase Retrieval using Expectation Consistent Signal Recovery Algorithm based on Hypernetwork [73.94896986868146]
  Phase retrieval is an important component in modern computational imaging systems. Recent advances in deep learning have opened up a new possibility for robust and fast PR. We develop a novel framework for deep unfolding to overcome the existing limitations.
  arXiv  Detail & Related papers  (2021-01-12T08:36:23Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.