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

Researchers introduce GeoRouteNet, a geometry-enhanced neural network solver for the Traveling Salesman Problem that achieves competitive optimality gaps (0.32% on TSP50, 1.26% on TSP100) through architectural innovations and a novel multi-candidate self-comparison reinforcement learning training approach. The method demonstrates superior cross-distribution generalization compared to existing non-autoregressive approaches while maintaining faster inference speeds than traditional solvers.

GeoRouteNet represents a meaningful advance in neural combinatorial optimization, addressing a fundamental challenge in applying deep learning to NP-hard problems: maintaining performance across different problem scales and distributions. The research tackles the tension between inference speed and solution quality by enhancing non-autoregressive models with geometric inductive biases—centered node features, learnable distance basis functions, and distance-aware attention mechanisms that embed structural information directly into the model architecture.

The contribution gains significance from its training methodology. Multi-candidate self-comparison reinforcement learning creates adaptive baselines by comparing multiple candidate solutions within each instance, providing more stable learning signals than traditional approaches. This design choice directly addresses the instability problems that have plagued NAR solvers, as evidenced by the substantial performance gap reduction on TSPLIB instances (from 17.12% to 3.60%).

For the optimization and logistics sectors, this work has practical implications. GeoRouteNet's batch inference throughput exceeding established solvers like Concorde and LKH3 suggests potential deployment advantages in time-sensitive applications where near-optimal solutions under strict latency constraints matter more than theoretical optimality. The research also demonstrates that geometric structure improvements and RL-based training are complementary rather than redundant, suggesting architectural choices directly influence which training strategies prove effective.

The ablation studies provide valuable insights for future research directions, indicating that geometric encoding dominates cross-distribution robustness while multi-candidate training specifically improves solution consistency with strong encoders. This separation of concerns helps the field understand which components drive different performance aspects.

• →GeoRouteNet achieves 0.32% optimality gap on TSP50 and significantly improves cross-distribution generalization compared to prior non-autoregressive solvers.
• →Multi-candidate self-comparison reinforcement learning with adaptive baselines provides more stable training signals for neural combinatorial optimization.
• →Geometric architectural enhancements (distance basis functions, centered features, distance-aware attention) are complementary to RL training improvements.
• →Inference throughput exceeds traditional solvers like Concorde and LKH3, enabling practical deployment in latency-sensitive optimization tasks.
• →Ablation studies confirm geometric structure improvements drive cross-distribution robustness while MCS-RL stabilizes solution quality with strong encoders.