Enhancing Transformer-based Routing by Encoding Distance via Relative Positional Encoding

This paper studies Relative Positional Encoding (RPE) as an additive bias in Transformer attention for the Team Orienteering Problem (TOP). By explicitly encoding pairwise spatial relationships between graph nodes, the Transformer encoder produces more spatially informed graph representations, enabling the decoder to estimate better routes. Experiments on instances with up to 100 nodes reportedly show consistent gains in collected rewards and optimality gaps compared with vanilla Transformer architectures used in other state-of-the-art work. The results support explicit relational modeling as a way to improve scalability and generalization in neural combinatorial optimization.