Local Topological Information as a Powerful Enhancer for Generalizable Neural Method in Travelling Salesman Problem

The generalization challenges faced by neural methods in solving the Travelling Salesman Problem (TSP) have attracted substantial attention. Current neural approaches predominantly rely on Deep Neural Networks with global receptive fields to capture global features, often overlooking the critical role of local topological information. To address this limitation, we propose a Global & Local Encoder (G&L-Encoder) that efficiently integrates local and global information within the feature space. The G-Encoder, with global receptive field, takes charge of capturing global features and facilitating the fusion of global and local information, while the L-Encoder, with its local neighborhood receptive field, extracts finer-grained features specific to each node's neighborhood, serving as an essential complement to the global one. Furthermore, we propose a simple yet efficient supervised learning framework, leveraging the recursive optimality inherent in optimal solutions to dig into their implicit knowledge. Extensive experiments on the TSP demonstrate that our method significantly improves generalization performance and achieves state-of-the-art results on medium-scale TSP tasks. Our source code is available at https://github.com/bxxseu/GL-POMO.