Rethinking Positional Encoding for Neural Vehicle Routing

• URL: http://arxiv.org/abs/2605.11910v1
• Date: Tue, 12 May 2026 10:22:31 GMT
• Title: Rethinking Positional Encoding for Neural Vehicle Routing
• Abstract summary: We formalize three structural properties that a routing-aware PE should respect.<n>We propose a hierarchical anisometric PE that combines a distance-indexed, circularly consistent in-route encoding with a depot-anchored angular cross-route encoding.
• Score: 29.116133441162173
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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.

Related papers

• GAIA: Geometry-Adaptive Operator Learning for Forward and Inverse Problems [17.161755403211252]
  We introduce the Geometry-Adaptive Integral Autoencoder (GAIA), an operator learning model that encodes the domain boundary and the interior field distribution into geometry tokens.<n>This yields a single architecture for forward (including BVPs) and inverse problems on arbitrary domains in one pass.<n>We evaluate GAIA on seven 2D and 3D benchmarks, four of which are new or substantially extended benchmarks for inverse problems and BVP.
  arXiv  Detail & Related papers  (2026-07-01T16:14:22Z)
• Communicability-Inspired Positional Encoding (CIPE) [17.120735986111217]
  Communicability-Inspired Positional size (CIPE) is a principled framework for attention-compatible graph positional encodings.<n> CIPE improves structure-agnostic Transformers by 35.5% on average across seven benchmarks.<n>It also consistently improves structure-biased graph Transformers, where competing PEs often yield only marginal benefits.
  arXiv  Detail & Related papers  (2026-06-24T01:56:20Z)
• MViewRouter: Internalizing Geometric Equivariance via Multi-view Alternating Attention for Combinatorial Routing [15.591644835298213]
  MView is a multi-view framework that internalizes geometric symmetries as a structural inductive bias to achieve indecision across routing problem variants.<n>Our approach introduces a Multi-view Alternating Attention (MAA) mechanism that enables parallel processing over the $D_4$ symmetry group.<n> Experiments on TSP and CVRP benchmarks, as well as real-world TSPLIB instances, demonstrate that MView achieves competitive solution quality and strong zero-shot generalization.
  arXiv  Detail & Related papers  (2026-05-31T08:09:02Z)
• Beyond Point-Wise Matching: Structural Representation Alignment for Accelerating Diffusion Transformers [93.3976834364707]
  We propose sREPA, a structural REPresentation Alignment framework to enforce consistency in the relational geometry of feature maps.<n>By encouraging the model to internalize holistic spatial layouts and structural correlations from pre-trained features, sREPA achieves faster and more stable convergence.
  arXiv  Detail & Related papers  (2026-05-16T12:01:04Z)
• Two-Stage Learned Decomposition for Scalable Routing on Multigraphs [10.10513248720328]
  We consider multigraphs, where parallel edges represent distinct travel options with varying trade-offs.<n>We use a Node-Edge Policy Factorization (NEPF) approach, which splits the routing policy into a node permutation stage and an edge selection stage.<n>Our experiments across six VRP variants demonstrate that NEPF matches or outperforms the state-of-the-art in terms of solution quality.
  arXiv  Detail & Related papers  (2026-05-06T19:23:09Z)
• Implicit Neural Representations: A Signal Processing Perspective [54.57279006229212]
  Implicit neural representations (INRs) mark a fundamental shift in signal modeling, moving from discrete sampled data to continuous functional representations.<n>This article examines the evolution of INRs from a signal processing perspective, emphasizing spectral behavior, sampling theory, and multiscale representation.<n>We highlight the utility of INRs across a broad range of applications, including inverse problems in medical and radar imaging, compression, and 3D scene representation.
  arXiv  Detail & Related papers  (2026-04-16T14:12:06Z)
• Rethinking Input Domains in Physics-Informed Neural Networks via Geometric Compactification Mappings [17.201530991184814]
  We introduce a mapping paradigm that reshapes the input coordinates through differentiable geometric compactification mappings.<n>We show that this approach yields more uniform residual distributions and higher solution accuracy on representative 1D and 2D PDEs.
  arXiv  Detail & Related papers  (2026-02-18T05:27:53Z)
• EFormer: An Effective Edge-based Transformer for Vehicle Routing Problems [25.234292937274212]
  We introduce EFormer, an Edge-based Transformer model that uses edge as the sole input for VRPs.<n>Our approach employs a precoder module with a mixed-score attention mechanism to convert edge information into temporary node embeddings.<n>EFormer outperforms established baselines on synthetic datasets.
  arXiv  Detail & Related papers  (2025-06-19T16:07:11Z)
• Revisiting LRP: Positional Attribution as the Missing Ingredient for Transformer Explainability [53.21677928601684]
  Layer-wise relevance propagation is one of the most promising approaches to explainability in deep learning.<n>We propose specialized theoretically-grounded LRP rules designed to propagate attributions across various positional encoding methods.<n>Our method significantly outperforms the state-of-the-art in both vision and NLP explainability tasks.
  arXiv  Detail & Related papers  (2025-06-02T18:07:55Z)
• Toward Relative Positional Encoding in Spiking Transformers [76.72869420863749]
  Spiking neural networks (SNNs) are bio-inspired networks that mimic how neurons in the brain communicate through discrete spikes.<n>We introduce several strategies to approximate relative positional encoding in spiking Transformers while preserving the binary nature of spikes.
  arXiv  Detail & Related papers  (2025-01-28T06:42:37Z)
• MultiSPANS: A Multi-range Spatial-Temporal Transformer Network for Traffic Forecast via Structural Entropy Optimization [34.27143920444722]
  We propose MultiSPANS to model complex multi-range dependencies using localtemporal and road network knowledge. We employ structural entropy theory to optimize the spatial attention mechanism. Experiments demonstrate the superiority of the presented framework over several state-of-the-art methods in real-world traffic datasets.
  arXiv  Detail & Related papers  (2023-11-06T05:19:06Z)
• GTA: A Geometry-Aware Attention Mechanism for Multi-View Transformers [63.41460219156508]
  We argue that existing positional encoding schemes are suboptimal for 3D vision tasks. We propose a geometry-aware attention mechanism that encodes the geometric structure of tokens as relative transformation. We show that our attention, called Geometric Transform Attention (GTA), improves learning efficiency and performance of state-of-the-art transformer-based NVS models.
  arXiv  Detail & Related papers  (2023-10-16T13:16:09Z)
• Learning to Iteratively Solve Routing Problems with Dual-Aspect Collaborative Transformer [14.680514752270375]
  This paper presents a novel Dual-Aspect Collaborative Transformer (DACT) to learn embeddings for the node and positional features separately. The positional features are embedded through a novel cyclic positional encoding (CPE) method to allow Transformer to effectively capture the circularity and symmetry of VRP solutions.
  arXiv  Detail & Related papers  (2021-10-06T07:21:41Z)
• A Rotation-Invariant Framework for Deep Point Cloud Analysis [132.91915346157018]
  We introduce a new low-level purely rotation-invariant representation to replace common 3D Cartesian coordinates as the network inputs. Also, we present a network architecture to embed these representations into features, encoding local relations between points and their neighbors, and the global shape structure. We evaluate our method on multiple point cloud analysis tasks, including shape classification, part segmentation, and shape retrieval.
  arXiv  Detail & Related papers  (2020-03-16T14:04:45Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.