提升多问题车辆路径求解,让模型更通用、更高效。
Improving Cross-Problem Vehicle Routing with Locally Augmented Preferences and Representation Disentanglement

- 用局部优化增强偏好对比,训练更有效
- 减少21.3%与最优解的差距,跨问题表现更强
- 适合需要统一求解多种路径问题的研究者
多任务车辆路径问题(VRP)求解器旨在用单一模型处理多种VRP变体,避免为每类问题单独训练。现有方法在训练和架构上仍存局限:强化学习受奖励尺度差异与优势信号衰减影响,偏好优化则因生成路径趋同而陷入监督不足;全共享编码器将约束相关表征混杂,制约泛化能力。本文提出两种模型无关改进:一是基于局部搜索优化的偏好训练算法POLAR,通过优化最佳解再构建偏好对,显著提升边际信息量;二是渐进式分层提取(PLE)编码器,通过门控机制让每层经由共享专家与任务专属专家,逐步分离通用路径结构与约束特异性表征。在16个分布内变体上,相较最强基线平均差距降低21.3%;在32个未见变体中,有27个优于先前神经方法。消融实验验证两项贡献均能提升多种骨干模型的跨问题泛化能力。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。