Modifying Ant Colony Optimization from Constructive to Local Search based approach : Application on large-scale problems

Traditional Ant Colony Optimization algorithms have demonstrated strong performance across various optimization problems. However, they are prone to premature convergence and their computational cost increases remarkably as the problem size does. These limitations are largely attributed to the construction-based approach, where solutions are rebuilt from scratch in each cycle, contrasting with local search methods that iteratively refine existing solutions. This paper introduces a novel adaptation of the Ant Colony Optimization metaheuristic to solve large-scale Traveling Salesman Problems. The proposed Ant-ILS modifies the Ant colony optimization metaheuristic from a construction-based to a local search-based approach. A pheromone-guided 2-Opt function is integrated to refine an initial population of solutions generated by the Nearest Neighbor heuristic. Additionally, a simple mechanism is proposed to mitigate stagnation during the local search process. Experimental evaluations on various TSPLIB instances highlight the algorithm’s superior performance, showcasing its competitiveness against state-of-the-art methods.