Enhancing the Traveling Salesman Problem Solutions with Reinforcement Learning: A Variant Exploration-Exploitation Approach Beyond ε-Greedy

Abstract

In light of significant advancements in the field of artificial intelligence, the traveling salesman problem (TSP) has emerged as a pivotal challenge for AI researchers. This paper endeavors to harness the strengths of reinforcement learning in addressing the TSP, introducing an alternative to the traditional exploration-exploitation dilemma through a variant of the ε-greedy strategy. We tested our approach on standard TSP instances from the TSPLIB dataset, employing both the Q-learning and SARSA algorithms for our experiments. Our findings reveal that our alternative exploration-exploitation method markedly outperforms the conventional ε-greedy approach, showcasing a notable increase in speed and efficacy.