The Traveling Salesman Problem (TSP) is a classic NP-hard optimization problem, where the goal is to find the shortest possible route that visits each node exactly once. In this thesis, we explore the use of the Monte Carlo Tree Search (MCTS) method—originally developed in the field of artificial intelligence—for approximating solutions to the TSP. In addition to implementing the basic MCTS algorithm, we also introduce enhancements such as heuristically guided simulations. The method was tested on standard benchmark instances from the TSPLIB library. We compare the performance of MCTS against the Nearest Neighbor algorithm, Genetic Algorithm, Ant Colony Optimization, and the advanced Lin-Kernighan heuristic. MCTS did not outperform advanced heuristics such as Lin-Kernighan and was also slower in comparison. However, it achieved better results than simpler methods like Nearest Neighbor or some metaheuristics and demonstrates potential for improvement, especially on larger instances.
|
