An Overview of the State-of-the-Art Machine Learning Methods for Traveling Salesman Problem
Stjepan Požgaj, Adrian Satja Kurdija, Marin Šilić, Goran Delač, Klemo Vladimir · 2024
The traveling salesman problem is one of the most well-known combinatorial optimization problems that has been studied for decades due to its importance in theory and practice. Traditional approaches to solving this problem include exact and heuristic algorithms, and recently, due to the significant development and excellent results of machine learning in various fields, more and more attention is paid to machine learning approaches. The main motivation for introducing machine learning into solving combinatorial optimization problems was that the development of classical hand-crafted heuristics requires theoretical and empirical expertise, which in the case of machine learning can be replaced by data. Also, the advantage of learned heuristics is that they can be trained on a set of instances of a specific problem that we want to solve in practice, which classical heuristics do not take into account because they are usually developed for the general case. In this paper, we give a detailed overview of machine learning approaches for solving the traveling salesman problem developed so far.