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

TL;DR

The paper introduces POLAR, a preference optimization method that enhances training signals by refining top solutions via local search before comparison, and PLE, a progressive encoder architecture that disentangles shared routing patterns from problem-specific constraints. These components together improve multi-task vehicle routing performance across diverse variants.

Why It Matters

Multi-task VRP solvers are critical for scalable logistics planning, but suffer from poor training signals and poor generalization. This work enables more robust, generalizable models that require less retraining for new routing scenarios.

Key Findings

• POLAR improves preference-based training by generating more informative comparison margins through local search refinement of top solutions.
• PLE enables better cross-problem generalization by progressively separating common routing structure from constraint-specific features using a gated expert architecture.
• The combined approach reduces the average gap to reference solutions by 21.3% on in-distribution variants and outperforms prior methods on 27 out of 32 unseen variants.