Abstract: The Traveling Salesman Problem (TSP) remains a fundamental challenge in combinatorial optimization with applications in logistics, routing, and network design. Classical local search methods face a trade-off between solution quality and computational efficiency: while 3-opt delivers better solutions than 2-opt, its O(n3) complexity renders it impractical for large instances. This paper presents a reinforcement learning (RL) approach that addresses this challenge through intelligent guidance of local search operators. Our method employs a simple one-dimensional Q-table that learns to identify poorly positioned cities and directs 2-opt and 3-opt operations toward the most promising tour segments. We evaluate the approach on 55 TSPLIB benchmark instances ranging from 51 to 18,512 cities. For instances up to 1,000 cities, RL-guided 3-opt (RL-3opt) achieves optimality gaps of 0.9–2.2% compared to 3.8–4.3% for classical 3-opt, with execution times reduced from hours to under one second and speedups reaching 32,323×. For instances between 1,000–5,000 cities, RL-3opt maintains computational efficiency (100–30,000× speedups) while achieving competitive 6.3% gaps. Both RL-2opt and RL-3opt execute in sub-second to a few seconds even on problems with over 18,000 cities. All experiments run on standard CPU hardware without GPU acceleration, demonstrating that effective TSP optimization remains accessible without specialized resources.

Sanaa El Jaghaoui and Aissa Kerkour Elmiad. “Q-Learning Guided Local Search for the Traveling Salesman Problem”. International Journal of Advanced Computer Science and Applications (IJACSA) 16.12 (2025). http://dx.doi.org/10.14569/IJACSA.2025.01612115

@article{Jaghaoui2025,
title = {Q-Learning Guided Local Search for the Traveling Salesman Problem},
journal = {International Journal of Advanced Computer Science and Applications},
doi = {10.14569/IJACSA.2025.01612115},
url = {http://dx.doi.org/10.14569/IJACSA.2025.01612115},
year = {2025},
publisher = {The Science and Information Organization},
volume = {16},
number = {12},
author = {Sanaa El Jaghaoui and Aissa Kerkour Elmiad}
}