Two-Stage Learned Decomposition for Scalable Routing on Multigraphs

• URL: http://arxiv.org/abs/2605.05389v1
• Date: Wed, 06 May 2026 19:23:09 GMT
• Title: Two-Stage Learned Decomposition for Scalable Routing on Multigraphs
• Abstract summary: We consider multigraphs, where parallel edges represent distinct travel options with varying trade-offs.<n>We use a Node-Edge Policy Factorization (NEPF) approach, which splits the routing policy into a node permutation stage and an edge selection stage.<n>Our experiments across six VRP variants demonstrate that NEPF matches or outperforms the state-of-the-art in terms of solution quality.
• Score: 10.10513248720328
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Most neural methods for Vehicle Routing Problems (VRPs) are limited to Euclidean settings or simple graphs. In this work, we instead consider multigraphs, where parallel edges represent distinct travel options with varying trade-offs (e.g., distance vs time). Few methods are designed for such formulations and those that do exist face major scalability issues. We mitigate these scalability issues via a Node-Edge Policy Factorization (NEPF) approach, which splits the routing policy into a node permutation stage and an edge selection stage. To enable the decomposition, we introduce a pre-encoding edge aggregation scheme and a non-autoregressive architecture for the edge stage, as well as a hierarchical reinforcement learning method to train the stages jointly. Our experiments across six VRP variants demonstrate that NEPF matches or outperforms the state-of-the-art in terms of solution quality, while being significantly faster in training and inference.

Related papers

• Improving Cross-Problem Vehicle Routing with Locally Augmented Preferences and Representation Disentanglement [0.0]
  Multi-task vehicle routing problem (VRP) solvers seek to handle multiple VRP variants within a single unified model.<n>We propose a novel training algorithm that applies a local search refinement pass to the best decoded tour before forming preference pairs.<n>Second, a Progressive Layered Extraction (PLE) encoder routes each encoder layer through one shared expert and a set of task-specific experts via a gating mechanism.
  arXiv  Detail & Related papers  (2026-08-25T17:44:23Z)
• A Unified Framework for Lifted Training and Inversion Approaches [42.951318906669506]
  This chapter introduces a unified framework that encapsulates various lifted training strategies.<n>We discuss the implementation of these methods using block-coordinate descent strategies.<n> Numerical results on standard imaging tasks validate the effectiveness and stability of the lifted Bregman approach.
  arXiv  Detail & Related papers  (2025-10-10T19:00:34Z)
• Neural Network Training via Stochastic Alternating Minimization with Trainable Step Sizes [3.246129789918632]
  The training of deep neural networks is inherently a non- optimization problem.<n>Standard approaches such as gradient descent (SGD) require simultaneous updates to parameters.<n>We propose a novel method Alternating Train Miniization with tailored step sizes (SAMT)<n>SAMT achieves better performance with fewer parameter updates compared to state-of-the-art methods.
  arXiv  Detail & Related papers  (2025-08-06T08:23:38Z)
• GASE: Graph Attention Sampling with Edges Fusion for Solving Vehicle Routing Problems [6.084414764415137]
  We propose an adaptive Graph Attention Sampling with the Edges Fusion framework to solve vehicle routing problems. Our proposed model outperforms the existing methods by 2.08%-6.23% and shows stronger generalization ability.
  arXiv  Detail & Related papers  (2024-05-21T03:33:07Z)
• 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)
• Symmetry-preserving graph attention network to solve routing problems at multiple resolutions [1.9304772860080408]
  We introduce the first-ever completely equivariant model and training to solve problems. It is essential to capture the multiscale structure of the input graph. We propose a Multiresolution scheme in combination with Equi Graph Attention network (mEGAT) architecture.
  arXiv  Detail & Related papers  (2023-10-24T06:22:20Z)
• Optimizing Solution-Samplers for Combinatorial Problems: The Landscape of Policy-Gradient Methods [52.0617030129699]
  We introduce a novel theoretical framework for analyzing the effectiveness of DeepMatching Networks and Reinforcement Learning methods. Our main contribution holds for a broad class of problems including Max-and Min-Cut, Max-$k$-Bipartite-Bi, Maximum-Weight-Bipartite-Bi, and Traveling Salesman Problem. As a byproduct of our analysis we introduce a novel regularization process over vanilla descent and provide theoretical and experimental evidence that it helps address vanishing-gradient issues and escape bad stationary points.
  arXiv  Detail & Related papers  (2023-10-08T23:39:38Z)
• 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)
• Crowd Counting via Perspective-Guided Fractional-Dilation Convolution [75.36662947203192]
  This paper proposes a novel convolution neural network-based crowd counting method, termed Perspective-guided Fractional-Dilation Network (PFDNet) By modeling the continuous scale variations, the proposed PFDNet is able to select the proper fractional dilation kernels for adapting to different spatial locations. It significantly improves the flexibility of the state-of-the-arts that only consider the discrete representative scales.
  arXiv  Detail & Related papers  (2021-07-08T07:57:00Z)
• Recurrent Multi-view Alignment Network for Unsupervised Surface Registration [79.72086524370819]
  Learning non-rigid registration in an end-to-end manner is challenging due to the inherent high degrees of freedom and the lack of labeled training data. We propose to represent the non-rigid transformation with a point-wise combination of several rigid transformations. We also introduce a differentiable loss function that measures the 3D shape similarity on the projected multi-view 2D depth images.
  arXiv  Detail & Related papers  (2020-11-24T14:22:42Z)
• Deep Unfolding Network for Image Super-Resolution [159.50726840791697]
  This paper proposes an end-to-end trainable unfolding network which leverages both learning-based methods and model-based methods. The proposed network inherits the flexibility of model-based methods to super-resolve blurry, noisy images for different scale factors via a single model.
  arXiv  Detail & Related papers  (2020-03-23T17:55:42Z)

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.