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

Chun-Sheng Zhao and Li-Pei Wong

PLOS ONE, 2025, vol. 20, issue 4, 1-24

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 the dynamic evolution of tour generation, a Transformer-based structure-aware model is developed for solving TSP. Employing deep reinforcement learning for training, the proposed model achieves deviation rates of 0.03%, 0.16%, and 1.13% for 20-node, 50-node, and 100-node TSPs, respectively, in comparison with the Concorde solver. It consistently surpasses classic heuristics, OR Tools, and various comparative learning-based approaches in multiple scenarios while showcasing a remarkable balance between time efficiency and solution quality. Extensive tests validate the effectiveness of the improvement mechanisms, underscore the significant impact of graph structure information on solving TSP using deep neural networks, and also reveal the scalability and limitations.

Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
https://journals.plos.org/plosone/article?id=10.1371/journal.pone.0319711 (text/html)
https://journals.plos.org/plosone/article/file?id= ... 19711&type=printable (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:plo:pone00:0319711

DOI: 10.1371/journal.pone.0319711

Access Statistics for this article

More articles in PLOS ONE from Public Library of Science
Bibliographic data for series maintained by plosone ().