PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Arthur Corrêa, Paulo Nascimento, Samuel Moniz

arXiv:2608.24859v1cs.LG

TL;DR

Multi-task VRP solvers still face weakening training supervision and entangled representations across heterogeneous constraints. This paper introduces POLAR, which locally refines tours before preference pairing, and PLE, which routes layers through shared and task-specific experts. Together, they improve reported performance across in-distribution and unseen VRP variants while remaining compatible with multiple backbones.

  • Problem

    Existing multi-task VRP solvers are limited by weakening RL or preference-optimization supervision and by fully shared encoders that entangle constraint-dependent representations.

  • Method

    POLAR refines the best decoded tour with local search before preference comparisons, while PLE progressively combines shared and task-specific experts through learned gating.

  • Results

    21.3% average-gap reduction versus MoSES(CaDA) is reported across 16 in-distribution variants at n = 50.

  • Takeaways & Limitations

    POLAR and PLE improve cross-problem generalization across multiple backbones and VRP variants, including unseen settings.

  • Takeaways & Limitations

    The evaluation follows a unified protocol aligned with prior cross-problem solvers, constraining interpretation to that experimental setting.

Abstract

from arXiv · show

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.

1 INTRODUCTION

Multi-task VRP solvers aim to support heterogeneous routing variants in one model, but existing training and fully shared architectures limit generalization. The paper addresses these gaps with POLAR and PLE.

  • Multi-task learning enables one deployable solver to support diverse VRP variants without retraining a separate model for each operational configuration.
  • Reinforcement learning becomes less informative as policies improve, while preference optimization produces increasingly near-tie comparisons with weak gradients.
  • Fully shared representations can entangle conflicting task signals through gradient interference, limiting encodings for heterogeneous routing constraints.
  • POLAR combines preference optimization with local-search refinement of the best decoded tour before preference pairing.
  • PLE progressively combines shared and task-specific experts through learned gating to separate common routing structure from variant-specific signals.
  • The paper reports extensive experiments and ablations evaluating the combined framework and individual contributions across multi-task VRP settings.

2 PROBLEM DESCRIPTION

The paper studies VRP variants derived from a capacitated routing problem and formed by combining operational constraints. Training and evaluation cover 16 variants, with zero-shot transfer additionally reported on 32 unseen variants.

  • A CVRP instance contains a depot, customer nodes with coordinates and demands, vehicle capacity, travel costs, and routes serving every customer exactly once.
  • A feasible CVRP solution keeps every route’s cumulative demand within vehicle capacity while minimizing total fleet travel distance.
  • Six additional constraints—backhauls, open routes, distance limits, time windows, mixed backhauls, and multi-depots—combine with CVRP to form 48 variants.
  • Backhauls increase vehicle load through pickups and impose linehaul-before-backhaul service order, whereas open routes omit the required depot return.
  • Distance limits cap route distance or duration, and time windows constrain service starts while requiring depot returns before closing time.
  • The main experiments train and evaluate on 16 variants, with zero-shot transfer additionally reported for 32 unseen variants involving mixed backhauls and multi-depots.

3 METHODOLOGY

The methodology combines a progressively disentangled PLE encoder with POLAR preference training. PLE separates shared and constraint-specific computation, while POLAR refines decoded tours before preference comparisons.

  • PLE encoder: PLE replaces a fully shared encoder with shared and task-specific experts, using soft, instance-dependent specialization to separate common and constraint-dependent representations.
  • PLE encoder: Each PLE layer maintains parallel shared and task streams initialized from FiLM-conditioned embeddings, with constraint prompts added to the task stream at the first layer.
  • PLE encoder: The shared expert updates the shared stream before gating, and the normalized shared representation is later added back into the task stream.
  • PLE encoder: At every depth, a gate uses the mean constraint prompt and a graph-level shared summary to allocate task-specific experts and shared-stream contributions.
  • PLE encoder: After the final layer, shared and task streams are concatenated, projected to the embedding dimension, normalized, and passed to the autoregressive decoder.
  • POLAR training: POLAR applies lightweight local search to the best decoded tour before preference labels are formed, strengthening comparisons when raw tours become near-ties.
  • POLAR training: Each training instance produces POMO multi-start trajectories plus one greedy trajectory, after which the best candidate may be refined and rescored under the current policy.
  • POLAR training: POLAR uses pairwise comparisons as relative supervision, yielding O(N^2) comparisons per instance instead of evaluating a sampled trajectory only against a scalar baseline.

4 EXPERIMENTS

Experiments evaluate the framework on 16 VRP variants using a unified protocol, comparing POLAR and PLE across multiple backbones and sensitivity settings. The full model achieves the best neural objective and gap on all in-distribution variants, while ablations show consistent benefits from both components.

  • Experimental setup: The evaluation covers 16 VRP variants, standardized protocols, separate models for n=50 and n=100, and comparisons with neural and traditional solvers.The experiments use established instance generation, evaluation budgets, and reporting conventions, with PyVRP and OR-Tools as traditional references.
  • Main results: 1.192% and 2.102% are the mean gaps of the proposed method at n=50 and n=100, respectively, averaged over 16 in-distribution variants.Relative average-gap reductions are 21.3% and 20.1% versus MoSES(CaDA), and 22.7% and 15.9% versus FiLMMeD(CaDA), for n=50 and n=100.
  • Main results: The proposed model attains the best neural objective and gap on all 16 variants at both instance sizes.No performance drop relative to competing neural methods was observed on any of the 16 tasks.
  • POLAR ablation: POLAR achieves the lowest average gap across all four backbones, improving over both RL and PO without pronounced degradation on individual variants.On the proposed backbone, mean gaps are 1.432% for RL, 1.282% for PO, and 1.192% for POLAR; POLAR is best on 16/16 variants for that model.
  • POLAR ablation: POLAR is uniformly better than PO across the temperature sweep, with both methods performing best at α=0.05.The difference widens as α increases and peaks at α=0.09; α=0.05 is used subsequently.
  • PLE ablation: PLE has the lowest average gap across all four backbones and outperforms both Shared and parameter-matched Deep-24 encoders.Deep-24 improves over Shared but remains strictly worse than PLE, indicating that extra capacity alone does not explain the gains.
  • PLE sensitivity: Increasing the number of PLE task-specific experts improves average performance with diminishing returns while substantially increasing training time.The experiments identify κ=3 as a favorable balance between near-best solution quality and lower average epoch time than κ=4.

5 CONCLUSION

The paper concludes that POLAR strengthens preference supervision and PLE disentangles shared and constraint-dependent representations in unified multi-task VRP solvers. Their combination improves performance across many variants, while harder and more complex real-world constraints remain an open limitation.

  • Conclusion: POLAR refines the best decoded tour before pairwise comparison, preserving more informative preference margins as the policy converges.PLE separately routes common routing structure and constraint-dependent representations through progressively coupled shared and task-specific experts.
  • Conclusion: POLAR improves four distinct MTL backbones over both RL and PO, while PLE outperforms fully shared and parameter-matched deeper shared encoders.Ablation studies confirm the individual contribution of both components.
  • Conclusion: The remaining limitation is handling harder and more complex real-world constraints.The authors propose expanding the benchmark to hundreds of VRP variants under richer constraints.

A.2 MULTI-TASK LEARNING FOR VRPS

Multi-task learning unifies VRP variants, but prior methods leave encoder sharing and computational cost unresolved. PLE addresses these issues with progressively shared and task-specific computation in a single model.

  • Multi-task VRP solvers: MTPOMO established cross-problem VRP modeling over 16 variants, followed by MVMoE’s hierarchical mixture-of-experts approach for capacity and generalization.Later methods refine representations, decoder capacity, scalability, and cross-size generalization.
  • Representation disentanglement: Recent decoder-focused methods leave the encoder largely shared and therefore do not directly resolve interference among heterogeneous constraints.This limitation motivates a distinct research direction centered on representation disentanglement.
  • Representation disentanglement: MoSES requires multiple experts for each constraint type, making training costly, while SPSM uses one task-specific module to capture variant-specific features.PLE instead progressively merges shared and task-specific representations within a single model.
  • Representation disentanglement: PLE is designed to provide finer disentanglement without separate experts and remains agnostic to the underlying model architecture.The paper reports consistent gains across various baselines with no performance drops on any problem variant.

A.3 ALTERNATIVE TRAINING PARADIGMS

Neural VRP research is moving beyond reinforcement learning toward preference-based and self-labeling approaches, but preference quality can deteriorate as sampled solutions converge. POLAR addresses this by refining only the best decoded tour before comparison, while retaining scale-invariant preference supervision and broad MTL compatibility.

  • Alternative training paradigms: Self-labeling and preference optimization reduce reliance on unstable scalar rewards used in reinforcement learning.Preference optimization frames learning as discriminating better from worse solutions rather than maximizing a reward.
  • Alternative training paradigms: Ranking-only preference construction is scale-invariant, but prior local-search refinement can impose high per-epoch computational cost.The prior approach exhaustively refined many solutions and was demonstrated only for single-task CVRP and TSP settings.
  • POLAR: POLAR combines scale-invariant preference supervision with cross-problem local search, selectively refining only the best solution before forming preference pairs.The selective design avoids the excessive burden of refining a larger subset of solutions.
  • POLAR: As policies converge, increasingly similar generated tours produce smaller quality gaps that can stall preference learning.POLAR targets this issue by improving anchor-solution quality through a targeted search procedure.
  • Solver framework: Attention-based autoregressive VRP solvers encode instances into node embeddings and sequentially construct feasible solutions with masked actions.The policy samples actions during training, while inference selects the highest-probability feasible node greedily.

D DETAILED ARCHITECTURE OVERVIEW

The architecture combines constraint-conditioned input representations, progressively routed shared and task-specific encoder experts, and an autoregressive decoder with feasibility masking. The design also analyzes when local-search supervision should activate, favoring late activation to reduce wall-clock time while preserving informative margins.

  • Encoder: Input depot and customer features are projected into a shared d-dimensional latent space before constraint conditioning.Customer features include coordinates, demands, time windows, and service times, while depot features include coordinates and distance limits.
  • Encoder: A six-element constraint vector generates both a prompt and FiLM parameters, allowing identical raw attributes to receive constraint-dependent interpretations.FiLM modulates customer embeddings as γ ⊙ h_i + β before attention is applied.
  • PLE encoder: Each PLE layer uses shared and task-specific Transformer experts with gated routing, progressively separating common routing structure from constraint-specific representations.Expert blocks include normalization, self-attention, scaled residuals, SwiGLU feed-forward layers, and coordinate-based rotary positional embeddings.
  • Decoder: The decoder initializes from final node embeddings and autoregressively selects feasible nodes using the current partial-solution state and cached keys and values.The dynamic state includes remaining capacities, elapsed and route lengths, and whether open routes are active.
  • Decoder: A preference-gated multi-head mechanism weights head outputs before residual refinement, normalization, and SwiGLU processing produce the final decoder representation.The authors report substantially greater shallow-decoder expressiveness with negligible overhead relative to heavy decoder architectures.
  • Decoder: Compatibility scores are computed between the final decoder representation and encoded nodes, with infeasible nodes assigned −∞ before action probabilities are formed.Training samples from the resulting distribution, whereas inference chooses nodes greedily.
  • Training analysis: Late local-search activation is motivated by early tours being too poor for refinement to yield informative preference margins.The study compares the default schedule, activating local search in the final 50 epochs, against activation from epoch 1.

E.2 PREFERENCE-MARGIN ANALYSIS

POLAR addresses weakening preference supervision by refining the best decoded tour before pair formation, producing more decisive cost and policy comparisons. PLE separates shared routing information from constraint-dependent processing through layered expert pathways.

  • Preference-margin analysis: POLAR applies local search to the best decoded tour before assigning preference labels, targeting near-ties that weaken preference-optimization gradients.The refined tour is re-scored under the current policy before pairwise comparisons.
  • Preference-margin analysis: Higher cost gaps and lower near-tie rates indicate more decisive contrasts in the preference set.Near-ties are defined using relative cost-gap tolerances ε ∈ {0.1, 0.5, 1, 5}%.
  • Preference-margin analysis: POLAR increases policy-space preference gaps across all reported ε values relative to PO, supporting stronger supervision beyond lower tour costs alone.The policy metrics re-score refined tours under the current policy.
  • PLE expert contributions: Task pathways contribute 71.1–89.3% of embedding-update magnitude in the first five layers, while the shared pathway contributes 10.7–28.9%.These measurements quantify expert contributions immediately before the final RMSNorm.
  • PLE expert contributions: In the final layer, task experts contribute 26.0%, 34.1%, and 39.9%, while the shared residual contributes 0.02%.The reported shift concentrates the final embedding update on constraint-dependent refinement.

F COMPUTATIONAL ANALYSIS

The computational analysis separates the overhead of PLE from that of POLAR. PLE adds encoder capacity with limited timing impact, while local refinement is the main source of additional training cost.

  • PLE overhead: PLE increases parameter count from 1.84M to 6.98M under κ = 3, but its encoder overhead has a smaller effect on training time.The encoder processes each instance once, unlike the repeatedly scoring autoregressive decoder.
  • POLAR overhead: POLAR is the main source of additional computational cost, increasing PLE training time from 12m 15s to 14m 49s at n=100.Refinement is activated only during the final 50 of 300 epochs.
  • Benchmark context: Table 8 reports objective values and gaps to best-known solutions for CVRPLib Set-X instances.The table compares benchmark performance across neural models.

G RESULTS ON PUBLIC BENCHMARKS

On CVRPLib Set-X instances, the proposed method generalizes across graph sizes without fine-tuning and achieves the strongest reported neural performance in the supplied results.

  • Set-X evaluation: 5.860% mean gap is achieved on the full Set-X dataset, a 30.5% relative reduction versus RouteFinder and 30.6% versus MoSES(CaDA).The method has the lowest neural gap on 81 of 100 instances.
  • Set-X evaluation: The proposed method has the lowest neural mean gap across all reported size ranges: 3.710% for fewer than 251 customers, 5.680% at mid-scale, and 8.215% at large scale.Models trained at n=100 were evaluated on Set-X without fine-tuning.
  • Set-X evaluation: The method degrades less as graph size grows than prior multi-task solvers, indicating stronger cross-size generalization.This conclusion follows the reported size-stratified Set-X gaps.

H ZERO-SHOT EVALUATION ON UNSEEN VARIANTS

The zero-shot evaluation tests constraint combinations withheld during training. The proposed model achieves the best neural results on most unseen variants, including all mixed-backhaul variants.

  • Zero-shot evaluation: 27 of 32 unseen variants have the best neural objective and gap under the proposed method.The evaluation uses strict zero-shot testing without fine-tuning.
  • Zero-shot evaluation: The model ranks first on all eight mixed-backhaul variants.Mixed backhauls and multi-depots were never activated during training.
  • Zero-shot evaluation: On multi-depot instances, the model has the lowest neural gap on 19 of 24 variants, while FiLMMeD(CaDA) or CaDA lead on the remaining five.These results quantify transfer to unseen multi-depot combinations.
  • Representation view: Figure 3 compares variant-colored t-SNE embeddings across four models, contrasting shared encoders with their PLE counterparts.Columns represent MTPOMO, MVMoE, RouteFinder, and the proposed model.

I REPRESENTATION GEOMETRY

A t-SNE view of final encoder node embeddings compares four backbones trained with and without PLE on 16 in-distribution VRP variants. Across backbones, PLE produces more separated, tighter, and more homogeneous clusters, indicating reduced representation entanglement.

  • Representation geometry: t-SNE is applied to final encoder node embeddings from MTPOMO, MVMoE, RouteFinder, and the proposed model, trained with and without PLE.The comparison uses n=50 training on 16 main in-distribution variants.
  • Representation geometry: Without PLE, embeddings from all four backbones mix across variants into a few broad, overlapping clusters.
  • Representation geometry: With PLE, embeddings form clusters that are more separated, tighter, and more homogeneous across the same backbones.
  • Representation geometry: The observed clustering contrast indicates that PLE reduces entanglement in encoder representations used by the decoder.
Loading 2608.24859v1…