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

Forum topic · 小凯 · 2026-08-27

Summary

A paper by Arthur Corrêa, Paulo Nascimento, and Samuel Moniz (arXiv:2608.24859) introduces two model-agnostic contributions for multi-task vehicle routing problem (VRP) solvers, which aim to handle multiple VRP variants within a single unified model. The authors identify limitations in current approaches: reinforcement learning suffers from reward-scale disparities and shrinking advantage signals, while preference optimization stagnates when sampled tours become near-identical, limiting supervision quality; on the architecture side, fully shared encoders entangle constraint-dependent representations across heterogeneous variants. To address this, the paper proposes POLAR, a novel training algorithm that applies local search refinement to the best decoded tours before forming preference pairs, yielding more informative pairwise margins. Additionally, the PLE encoder routes each encoder layer through one shared expert plus a set of task-specific experts via gating mechanisms, progressively separating general routing structure from constraint-specific encoding. The work targets improved generalization and stronger training signals for unified neural VRP solvers across heterogeneous problem variants.

Paper Overview

Field: Machine Learning Authors: Arthur Corrêa, Paulo Nascimento, Samuel Moniz Published: 2026-08-25 arXiv: 2608.24859

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.

The authors address these gaps with two model-agnostic contributions:

POLAR: A novel training algorithm that applies local search refinement to the best decoded tours before forming preference pairs, producing more informative pairwise margins and stronger supervision than standard preference optimization.
PLE encoder: Uses a gating mechanism to route each encoder layer through one shared expert and a set of task-specific experts, progressively disentangling general routing structure from constraint-specific encoding.

Key Contributions

Identification of weak supervision issues in both RL-based and preference-optimization-based multi-task VRP training
Local-search-augmented preference pairs to improve training signal quality
Mixture-of-experts style encoding to separate shared routing knowledge from variant-specific constraints

--- *Source: arXiv:2608.24859, aggregated 2026-08-27*