Rethinking Positional Encoding for Neural Vehicle Routing
For researchers in neural combinatorial optimization, this work provides a principled analysis and design of positional encodings for routing problems, leading to consistent performance improvements.
This work identifies three structural properties of vehicle routing problems that standard positional encodings fail to capture, and proposes a hierarchical anisometric positional encoding that respects these properties. The proposed encoding consistently outperforms index-based alternatives across diverse VRP variants, with gains that transfer across problem variants, model architectures, and distribution shifts.
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.