Rethinking Positional Encoding for Neural Vehicle Routing
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , , , , , , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2026
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866911673858654208 |
|---|---|
| author | Hua, Chuanbo Berto, Federico Hottung, Andre Zepeda, Nayeli Gast Ma, Yining Ma, Zihan Wong-Chung, Paula Kwon, Changhyun Wu, Cathy Tierney, Kevin Park, Jinkyoo |
| author_facet | Hua, Chuanbo Berto, Federico Hottung, Andre Zepeda, Nayeli Gast Ma, Yining Ma, Zihan Wong-Chung, Paula Kwon, Changhyun Wu, Cathy Tierney, Kevin Park, Jinkyoo |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2605_11910 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Rethinking Positional Encoding for Neural Vehicle Routing Hua, Chuanbo Berto, Federico Hottung, Andre Zepeda, Nayeli Gast Ma, Yining Ma, Zihan Wong-Chung, Paula Kwon, Changhyun Wu, Cathy Tierney, Kevin Park, Jinkyoo Artificial Intelligence 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. |
| title | Rethinking Positional Encoding for Neural Vehicle Routing |
| topic | Artificial Intelligence |
| url | https://arxiv.org/abs/2605.11910 |