GeoRouteNet: Geometry-Enhanced Non-Autoregressive Neural Solver for the Traveling Salesman Problem

Neural solvers for the Traveling Salesman Problem (TSP) often struggle with cross-distribution generalization and stability when using non-autoregressive (NAR) architectures. While NAR models offer high parallel inference throughput, they frequently lack the geometric inductive biases necessary to handle spatial distributions beyond their training data. This paper introduces GeoRouteNet, a model designed to address these limitations by incorporating explicit geometric features and a novel training objective.

To improve the encoder, the authors integrate centered node coordinates, learnable radial distance basis functions, and distance-aware graph attention. These components allow the model to better capture Euclidean relationships and maintain translation invariance. On the training side, the authors propose Multi-Candidate Self-Comparison Reinforcement Learning (MCS-RL). Instead of comparing a single sampled tour to a greedy baseline, MCS-RL samples multiple candidate tours, constructs an adaptive baseline from peer candidates, and uses winner-candidate guidance to reinforce high-quality solutions.

GeoRouteNet significantly outperforms existing NAR baselines across multiple benchmarks. On random TSP50 instances, it achieves an optimality gap of 0.32% under Beam-1000 decoding. More importantly, it demonstrates strong cross-distribution robustness; on 27 stratified TSPLIB instances, the optimality gap drops from 17.12% (in the reproduced baseline) to 3.60%.

Ablation studies reveal that the geometric encoder and the MCS-RL training objective are complementary. The geometric structure is the primary driver of cross-distribution generalization, while the MCS-RL training further stabilizes and refines solution quality when paired with the stronger encoder. Additionally, the model maintains high inference throughput, exceeding that of traditional solvers like Concorde and LKH3 in batch settings.

This work bridges the gap between the speed of non-autoregressive neural solvers and the accuracy of traditional heuristics. By demonstrating that geometric inductive biases and multi-candidate training can significantly improve generalization, the paper provides a scalable path for deploying neural optimization in real-world logistics and routing applications where high throughput and reliable performance are both required.