GeoRouteNet: A Geometry-Aware Non-Autoregressive Neural Solver for the Euclidean Traveling Salesman Problem
About
Non-autoregressive neural solvers amortize computation across traveling salesman problem (TSP) instances, but models trained on random Euclidean instances can degrade when the number or spatial distribution of nodes changes. We study whether explicit geometric features and a richer within-instance training signal improve transfer across graph sizes and spatial distributions. We introduce GeoRouteNet, which augments a non-autoregressive TSP solver with centered node offsets and radii, learnable radial distance bases, distance-aware graph attention, explicit edge messages, and cross-layer representation mixing. We also introduce multi-candidate self-comparison reinforcement learning (MCS-RL), which trains on several sampled tours per instance using a leave-one-out adaptive baseline, winner-candidate guidance, and annealed entropy regularization. In a single-seed study, all neural variants are trained only on random TSP-50 instances and evaluated with the same greedy and beam-search decoders. Under Beam-1000 decoding, GeoRouteNet-MCS-RL obtains gaps of 0.32% on the TSP-50 validation set used for checkpoint selection, 1.26% on a correlated TSP-100 size diagnostic, and 3.60% across 27 TSPLIB EUC_2D instances. The NAR4TSP-PG gaps on the same evaluations are 0.42%, 2.73%, and 17.12%. A 2x2 comparison crosses encoder and training choices. Under PG, the geometry-aware encoder has lower gaps than the reproduced encoder on the TSP-100 diagnostic and TSPLIB. With the geometry-aware encoder, MCS-RL is associated with a further reduction; with the reproduced encoder, it has a higher TSPLIB gap.