A comparison of state-of-the-art reinforcement learning algorithms applied to the traveling salesman problem

Combinatorial optimization problems are highly relevant for real-world applications. For complex problems, the use of exact solution techniques is limited to small problem sizes and, hence, effective heuristic approaches are needed. Furthermore, most approaches require that for different input data solutions have to be computed individually for each single problem instance. Recent developments in Reinforcement Learning (RL) provide promising alternatives as they-after being trained-allow to provide heuristic out-of-the-box solutions for arbitrary input data. Transformer-based RL approaches even have the capability to generalize with regard to the problem size and allow to provide quick solutions for problems that are larger than they have been trained on. However, despite their potential, the amount of different RL algorithms is large and their performance for combinatorial optimization problems is unclear. To resolve this issue, we compare the performance of different stateof-the-art RL algorithms when applied to the classical Traveling Salesman Problem (TSP) and the Orienteering Problem (OP). We find that some RL algorithms achieve promising results with (i) near-optimal performance compared to optimal solutions for single tractable problem instances, while (ii) providing the capability to generalize regarding both the input data (continuous coordinates) and the problem size (number of nodes).