Near-Optimal Traveling Salesman Solution with Deep Attention

The Traveling Salesman Problem (TSP) is a well-known problem in computer science that requires finding the shortest possible route that visits every city exactly once. TSP has broad applications in logistics, routing, and supply chain management, where finding optimal or near-optimal solutions efficiently can lead to substantial cost and time reductions. However, traditional solvers rely on iterative processes that can be computationally expensive and time-consuming for large-scale instances. This research proposes a novel deep learning architecture designed to predict optimal or near-optimal TSP tours directly from the problem’s distance matrix, eliminating the need for extensive iterations to save total solving time. The proposed model leverages the attention mechanism to effectively focus on the most relevant parts of the network, ensuring accurate and efficient tour predictions. It has been tested on the TSPLIB benchmark dataset and observed significant improvements in both solution quality and computational speed compared to traditional solvers such as Gurobi and Genetic Algorithm. This method presents a scalable and efficient solution for large-scale TSP instances, making it a promising approach for real-world traveling salesman applications.

@article{Kafakthong2024,
  title     = {Near-Optimal Traveling Salesman Solution with Deep Attention},
  journal   = {International Journal of Advanced Computer Science and Applications},
  volume    = {15},
  number    = {12},
  year      = {2024},
  publisher = {The Science and Information Organization},
  author    = {Natdanai Kafakthong and Krung Sinapiromsaran},
  doi       = {10.14569/IJACSA.2024.0151295},
  url       = {https://doi.org/10.14569/IJACSA.2024.0151295}
}