EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

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

Chun-Sheng Zhao, Li-Pei Wong iD

PLOS ONE · 2025

DOI: 10.1371/journal.pone.0319711 ↗

Kurz gefasst

Fachartikel in der Zeitschrift PLOS ONE, 2025. Verfasst von Chun-Sheng Zhao und 1 weiteren Autor:innen. Beteiligte Einrichtung: School of Computer Sciences, Universiti Sains Malaysia, Pulau Pinang, Malaysia. Hauptthemen laut MEDLINE: Models, Theoretical, Problem Solving. Die Arbeit nennt 50 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0).

AbstractSchlagwörterBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

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.

Schlagwörter

MeSH-Schlagwörter (MEDLINE)

Models, TheoreticalProblem SolvingHumansAlgorithms

Autor:innen und Institutionen

  • School of Computer Sciences, Universiti Sains Malaysia, Pulau Pinang, Malaysia.

ORCID-Profile: Li-Pei Wong

Zitieren

APA

Zhao, C. S., & Wong, L. P. (2025). A transformer-based structure-aware model for tackling the traveling salesman problem. PLOS ONE. https://doi.org/10.1371/journal.pone.0319711

Vancouver

Zhao CS, Wong LP. A transformer-based structure-aware model for tackling the traveling salesman problem. PLOS ONE. 2025. doi:10.1371/journal.pone.0319711

BibTeX
@article{Zhao2025,
  author = {Zhao, Chun-Sheng and Wong, Li-Pei},
  title = {A transformer-based structure-aware model for tackling the traveling salesman problem},
  journal = {PLOS ONE},
  year = {2025},
  doi = {10.1371/journal.pone.0319711}
}
Kostenlos starten →