arXiv:2605.11910cs.AI2026-05

为车辆路径问题设计更符合几何结构的位置编码,提升模型性能。

Rethinking Positional Encoding for Neural Vehicle Routing

  • 基于路径的几何特性设计分层非对称位置编码
  • 在多种车辆路径问题上性能优于传统索引编码
  • 适合需要精准空间建模的路径优化任务

基于Transformer的模型已成为车辆路径问题(VRPs)神经组合优化的主流方法,但位置编码(PE)在其中的作用仍不明确。与自然语言中均匀分布的词元不同,路径解具有多个结构性特征,使标准NLP位置编码不适用。本文形式化了三种应被路由感知位置编码尊重的特性:节点间非等距距离、循环与方向敏感拓扑,以及以枢纽为中心的层级多路径全局结构,并提出几何基础的统一设计原则。基于此,我们分析并比较了来自NLP、图注意力与专用路由三类的位置编码方法,提出一种分层非对称位置编码,结合基于距离索引的循环一致路内编码与以枢纽锚定的角度跨路编码。在多种VRP变体上的大量实验表明,几何接地的编码在性能上持续优于基于索引的替代方案,且优势可跨问题变体、模型架构和分布偏移转移。

原文摘要 · Abstract (English)

Transformer-based models have become the dominant paradigm for neural combinatorial optimization (NCO) of vehicle routing problems (VRPs), yet the role of positional encoding (PE) in these architectures remains largely unexplored. Unlike natural language, where tokens are uniformly spaced on a line, routing solutions exhibit several properties that render standard NLP positional encodings inadequate. In this work, we formalize three such structural properties that a routing-aware PE should respect, namely anisometric node distances, cyclic and direction-aware topology, and hierarchical depot-anchored global multi-route structure, combining them with a unifying design principle of geometric grounding. Guided by these criteria, we analyze and compare PE methods spanning NLP, graph-transformer, and routing-specific families, and propose a hierarchical anisometric PE that combines a distance-indexed, circularly consistent in-route encoding with a depot-anchored angular cross-route encoding. Extensive experiments across diverse VRP variants demonstrate that geometry-grounded PE consistently outperforms index-based alternatives, with gains that transfer across problem variants, model architectures, and distribution shifts.

路径优化位置编码Transformer几何建模

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