Improving Cross-Problem Vehicle Routing with Locally Augmented Preferences and Representation Disentanglement

• URL: http://arxiv.org/abs/2608.24859v1
• Date: Tue, 25 Aug 2026 17:44:23 GMT
• Title: Improving Cross-Problem Vehicle Routing with Locally Augmented Preferences and Representation Disentanglement
• Abstract summary: 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.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Multi-task vehicle routing problem (VRP) solvers seek to handle multiple VRP variants within a single unified model, avoiding the need to train a separate model for every variant. In spite of recent progress, current approaches remain limited on two fronts. On the training side, reinforcement learning suffers from reward-scale disparities and shrinking advantage signals as policies improve, whereas preference optimization stagnates once sampled tours become near-identical and thus fundamentally limited by the quality of the policy's own generated solutions, leaving both paradigms with weak supervision as training progresses. On the architecture side, existing fully shared encoders entangle constraint-dependent representations across heterogeneous variants, which limits generalization. We address these gaps with two model-agnostic contributions. First, we propose Preference Optimization with Locally Augmented Refinement (POLAR), a novel training algorithm that applies a local search refinement pass to the best decoded tour before forming preference pairs, yielding much more informative pairwise margins. 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, progressively separating common routing structure from constraint-specific encodings. Through extensive experiments on various VRP variants, we show that POLAR and PLE together elevate the current state-of-the-art among neural multi-task solvers. We reduce the average gap to reference solutions by 21.3% relative to the strongest published baseline on 16 in-distribution variants, and outperform prior neural methods on 27 out of 32 unseen variants. Ablation studies confirm the efficacy of each contribution, showing that both improve cross-problem generalization across multiple backbone model architectures.

Related papers

• Towards Generalization-Oriented Models for Vehicle Routing Problems with Mixture-of-Experts [8.616895584914579]
  We propose Residual Refined Experts with Instance-level Gating (R2E-IG) to improve cross-distribution generalization.<n>R2E-IG achieves competitive performance against state-of-the-art baselines on both in-distribution and out-of-distribution instances.
  arXiv  Detail & Related papers  (2026-05-26T09:46:54Z)
• Two-Stage Learned Decomposition for Scalable Routing on Multigraphs [10.10513248720328]
  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.
  arXiv  Detail & Related papers  (2026-05-06T19:23:09Z)
• FiLMMeD: Feature-wise Linear Modulation for Cross-Problem Multi-Depot Vehicle Routing [0.0]
  We present a novel unified neural-based model for 24 different MDVRP variants.<n>FiLMMeD consistently outperforms state-of-the-art baselines.
  arXiv  Detail & Related papers  (2026-04-30T16:48:13Z)
• HAD: Combining Hierarchical Diffusion with Metric-Decoupled RL for End-to-End Driving [51.268878540511054]
  We propose HAD, an end-to-end planning framework with a Hierarchical Diffusion Policy.<n>We show that HAD achieves new state-of-the-art performance on both NAVSIM and HUGSIM.
  arXiv  Detail & Related papers  (2026-04-04T04:12:47Z)
• Multi-Agent DRL for V2X Resource Allocation: Disentangling Challenges and Benchmarking Solutions [51.22818149833102]
  Multi-agent reinforcement learning (MARL) has emerged as a promising approach for radio resource allocation in vehicle-to-everything (C-V2X) networks.<n>However, the multifaceted challenges inherent to MARL are often intertwined, making it difficult to understand their individual impact on performance in vehicular environments.<n>We bridge this gap by formulating C-V2X RRA as a sequence of multi-agent interference games with progressively increasing complexity.
  arXiv  Detail & Related papers  (2026-02-18T14:46:56Z)
• Unrolled Neural Networks for Constrained Optimization [83.29547301151177]
  Our framework comprises two coupled neural networks that jointly approximate the saddle point of the Lagrangian.<n>We numerically evaluate the framework on mixed-integer quadratic programs and power allocation in wireless networks.
  arXiv  Detail & Related papers  (2026-01-24T03:12:41Z)
• Unrolled Graph Neural Networks for Constrained Optimization [83.29547301151177]
  We study the dynamics of the dual ascent algorithm in two coupled graph neural networks (GNNs)<n>We propose a joint training scheme that alternates between updating the primal and dual networks.<n>Our numerical experiments demonstrate that our approach yields near-optimal near-feasible solutions.
  arXiv  Detail & Related papers  (2025-09-21T16:55:41Z)
• SHIELD: Multi-task Multi-distribution Vehicle Routing Solver with Sparsity and Hierarchy [26.708590440636527]
  We introduce SHIELD, a novel model that leverages both sparsity and hierarchy principles.<n>We develop a context-based clustering layer that exploits the presence of hierarchical structures in the problems to produce better local representations.<n>Our results demonstrate the superiority of our approach over existing methods on 9 real-world maps with 16 VRP variants each.
  arXiv  Detail & Related papers  (2025-06-10T03:55:14Z)
• Accelerating Vehicle Routing via AI-Initialized Genetic Algorithms [53.75036695728983]
  Vehicle Routing Problems (VRP) are a fundamental NP-hard challenge in Evolutionary optimization.<n>We introduce an optimization framework where a reinforcement learning agent is trained on prior instances and quickly generates initial solutions.<n>This framework consistently outperforms current state-of-the-art solvers across various time budgets.
  arXiv  Detail & Related papers  (2025-04-08T15:21:01Z)
• TuneNSearch: a hybrid transfer learning and local search approach for solving vehicle routing problems [44.035549471545586]
  TuneNSearch is a hybrid transfer learning and local search approach for addressing diverse variants of the vehicle routing problem (VRP)<n>Our method uses reinforcement learning to generate high-quality solutions, which are refined by an efficient local search procedure.
  arXiv  Detail & Related papers  (2025-03-16T21:34:11Z)
• Generalized Schrödinger Bridge Matching [54.171931505066]
  Generalized Schr"odinger Bridge (GSB) problem setup is prevalent in many scientific areas both within and without machine learning. We propose Generalized Schr"odinger Bridge Matching (GSBM), a new matching algorithm inspired by recent advances. We show that such a generalization can be cast as solving conditional optimal control, for which variational approximations can be used.
  arXiv  Detail & Related papers  (2023-10-03T17:42:11Z)
• NormAUG: Normalization-guided Augmentation for Domain Generalization [60.159546669021346]
  We propose a simple yet effective method called NormAUG (Normalization-guided Augmentation) for deep learning. Our method introduces diverse information at the feature level and improves the generalization of the main path. In the test stage, we leverage an ensemble strategy to combine the predictions from the auxiliary path of our model, further boosting performance.
  arXiv  Detail & Related papers  (2023-07-25T13:35:45Z)
• Learning to Solve Routing Problems via Distributionally Robust Optimization [14.506553345693536]
  Recent deep models for solving routing problems assume a single distribution of nodes for training, which severely impairs their cross-distribution generalization ability. We exploit group distributionally robust optimization (group DRO) to tackle this issue, where we jointly optimize the weights for different groups of distributions and the parameters for the deep model in an interleaved manner during training. We also design a module based on convolutional neural network, which allows the deep model to learn more informative latent pattern among the nodes.
  arXiv  Detail & Related papers  (2022-02-15T08:06:44Z)

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.