arXiv:2605.10122cs.AIcs.LG2026-05

提升神经路由求解器对复杂约束的感知能力,实现更高效的状态嵌入。

Rethinking Constraint Awareness for Efficient State Embedding of Neural Routing Solver

  • 提出约束感知残差调制模块,动态融合约束信息优化状态嵌入
  • 在单任务与多任务场景下,显著提升大规模实例求解性能
  • 特别适合需处理多种复杂约束的现实路由问题求解

重型编码器-轻量解码器(HELD)神经路由求解器因其在多种车辆路径问题(VRPs)中的广泛应用而备受关注。然而,面对具有复杂约束的VRP变体时,现有方法表现不佳。本文从解码阶段状态嵌入生成机制的角度重新审视现有神经求解器,发现当前机制限制了注意力计算中的观察空间,成为高质量解生成的关键瓶颈。通过详尽的实验分析,证实保持全局观察空间的必要性。为克服全局观察空间固有的约束无关性缺陷,本文提出简单而有效的约束感知残差调制(CARM)模块,通过自适应地将约束相关变量融入上下文嵌入,显著增强约束感知能力,使求解器能充分利全局观察空间生成高效状态嵌入。在两个单任务和五个多任务神经路由求解器上的广泛实验表明,引入CARM模块后,基线性能持续提升。尤为突出的是,配备CARM的求解器在扩展至大规模实例以及泛化到未见的VRP变体方面均取得显著改进。这些发现为神经路由求解器的架构设计提供了重要启示。

原文摘要 · Abstract (English)

Heavy-Encoder-Light-Decoder (HELD) neural routing solvers have emerged as a promising paradigm due to their broad applicability across multiple vehicle routing problems (VRPs). However, they typically struggle with VRP variants with complex constraints. To address this limitation, this paper systematically revisits existing neural solvers from the perspective of the generation mechanism for state embeddings (i.e., query vector prior to compatibility calculation) during decoding. We identify that current mechanisms restrict the observation space during attention computation, introducing a key bottleneck to achieving high-quality solutions. Through detailed empirical analysis, we demonstrate the necessity of preserving a global observation space. To overcome the constraint-agnostic drawback inherent to global observation spaces, we propose a simple yet powerful Constraint-Aware Residual Modulation (CARM) module. By adaptively modulating the context embedding with constraint-relevant variables, CARM effectively enhances constraint awareness, enabling the neural solver to fully leverage the global observation space and generate an efficient state embedding. Extensive experimental results across two single-task and five multi-task neural routing solvers confirm that the CARM module consistently boosts baseline performance. Notably, solvers equipped with our CARM achieve substantial improvements in scaling to large-scale instances and in generalizing to unseen VRP variants. These findings provide valuable insights for the architectural design of neural routing solvers.

神经路由约束感知状态嵌入路径优化

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。