A New Approach to Efficiently Solving the Traveling Salesman Problem (TSP) by Combining Artificial Intelligence Techniques and Ant Colony Metaheuristics

The efficient resolution of complete NP problems, such as the Traveling Salesman Problem (TSP), particularly for large instances, remains a major challenge in operations research and combinatorial optimization, especially for many businesses, particularly in sectors such as logistics, urban planning, and networks, where efforts are made daily to optimize routes and delivery times. Optimization methods inspired by collective behavior, such as Ant Colony Optimization (ACO), offer competitive results for solving these types of problems. The main problem is the size of the instances because, when it becomes large, many existing algorithms fail to converge to a good solution within a reasonable timeframe: the execution time is generally very long, and the solution obtained is generally far from being the optimal solution to the problem. In this article, we propose a new way of approaching the resolution of the TSP through new metaheuristics inspired by artificial intelligence techniques and ant colony theory. To evaluate the effectiveness of our methodology, particularly the Multi-colony Ant Colony Optimization version 2-SK (MACOV2SK) method, simulations were performed on several instances of the TSP, focusing on large-scale instances. The experimental results clearly demonstrate that the proposed approach significantly improves upon several other approaches in the literature in terms of execution time and solution quality, especially for large-scale problems.