Understanding Heatmap-Based Neural TSP Solvers as the Distance-Shifter

Heatmap-based neural solvers for the Traveling Salesman Problem (TSP) typically generate probability heatmaps and then extract tours with post-hoc search heuristics. In this paper, we show that this pipeline is fundamentally a distance shifter: any probability heatmap can be converted into a surrogate distance matrix through a simple logarithmic transformation, and searching for the maximum-probability tour is therefore equivalent to solving another TSP. This observation has two important implications. First, heatmap generation does not reduce the NP-hardness of TSP, and conventional post-hoc search algorithms such as MCTS, beam search, and $k$-opt are often suboptimal compared to specialized TSP solvers. Second, instead of learning heatmaps via costly reinforcement learning or classification, we can directly learn the distance-shifting transformation through supervised regression. Building on these insights, we propose a unified distance-shifting paradigm for neural TSP solvers, which includes (i) a rule-based method that converts pretrained heatmaps into surrogate distances, and (ii) learnable distance-shifting architectures, including SVSNet—an ultra-compact model based on singular value shrinkage with only four learnable parameters—and DTNet, a bidirectional cross-attention model in three sizes (0.02M/0.14M/1.09M parameters). Extensive experiments on general asymmetric/symmetric non-metric/Euclidean TSP across four distance distributions show that our methods surpass the SOTA heuristic LKH on in-distribution instances and remain comparable to it under out-of-distribution shifts, while consistently outperforming existing DL-based neural solvers. Moreover, trained on only 1,000 small instances, our models transfer directly from ATSP-100 to ATSP-1000 and generalize across distributions far more robustly than other DL-based solvers, all with extreme parameter efficiency, offering a promising lightweight direction for neural combinatorial optimization. Data and code will be released upon publication.