An Innovative Q-Learning and ACO Approaches for the Traveling Salesman Problem

In this study, we introduce an innovative Q-learning and Ant Colony Optimization algorithms for solving the Traveling Salesman Problem (TSP). Given that an optimal tour for the TSP does not contain cross-edges, our approaches focus on minimizing the number of cross-edges in the tour. Experiments on TSPLIB instances, of sizes between 51 and 159, show the effectiveness of these approaches and highlight the rapid convergence to better solutions compared to classical methods based direct minimization the tour length.