With the growing recognition of the unique advantages of reinforcement learning and genetic algorithms in addressing combinatorial optimization problems, this study aims to integrate these two methods to collectively tackle the classic combinatorial optimization challenge of the Traveling Salesman Problem (TSP). The Traveling Salesman Problem (TSP) stands as a quintessential combinatorial optimization challenge, tasked with determining the shortest path among designated cities. This paper introduces an innovative approach by amalgamating reinforcement learning’s path selection prowess with genetic algorithms’ global search strategy, aiming to uncover superior solutions in TSP. Specifically, the experiment employs a dual Q-learning algorithm within reinforcement learning to identify multiple optimal paths, serving as progenitors for the genetic algorithm to further enhance performance. The paper meticulously outlines the problem modeling process, elucidating TSP instance definitions, descriptions, and precise objective function definitions. Experimental findings underscore the substantial enhancements achievable in TSP optimization through this comprehensive approach, offering a fresh perspective and methodology for tackling combinatorial optimization challenges.

TSP is one of the most famous problems in graph theory, as well as one of the typical NP-hard problems in combinatorial optimization. Its applications range from how to plan the most reasonable and efficient road traffic to how to better set up nodes in the Internet environment to facilitate information flow, among others. Reinforcement learning has been widely regarded as an effective tool for solving combinatorial optimization problems. This paper attempts to solve the TSP problem using different reinforcement learning algorithms and evaluated the performance of three RL algorithms (Q-learning, Sarsa, and Double Q-Learning) under different reward functions, ε-greedy decay strategies, and running times. The results show that the Double Q-Learning algorithm is the best algorithm, as it could produce results closest to the optimal solutions, and by analyzing the results, better reward strategies and epsilon-greedy decay strategies are obtained.