A transformer-based structure-aware model for tackling the traveling salesman problem.

ABSTRACT: Leveraging the Transformer architecture to develop end-to-end models for addressing combinatorial optimization problems (COPs) has shown significant potential due to its exceptional performance. Nevertheless, a multitude of COPs, including the Traveling Salesman Problem (TSP), displays typical graph structure characteristics that existing Transformer-based models have not effectively utilized. Hence, this study focuses on TSP and introduces two enhancements, namely closeness centrality encoding and spatial encoding, to strengthen the Transformer encoder's capacity to capture the structural features of TSP graphs. Furthermore, by integrating a decoding mechanism that not only emphasizes the starting and most recently visited nodes, but also leverages all previously visited nodes to capture

SUBMITTER: Zhao CS 

PROVIDER: S-EPMC11975067 | biostudies-literature | 2025

REPOSITORIES: biostudies-literature