A Hybrid Algorithm ACS-GA for Solving the Traveling Salesman Problem

Traveling Salesman Problem (TSP), a well-known combinatorial optimization problem, aims to find the shortest path for a salesman to visit all the given cities and return to the departure city, with each city visited once and only once. To solve the problem, we propose a hybrid metaheuristic algorithm that combines the ant colony system(ACS) and genetic algorithm(GA). Distinguishing from previous hybrid algorithms, the two algorithms in our proposed hybrid algorithm run independently in parallel, exchange each other’s optimal solutions in a fixed iteration cycle and incorporate the exchanged optimal solutions into the independently running algorithm through update pheromone or add to the candidate parent. The experimental part uses data instances with a city size distribution between 51 and 226. The results of running the ACS, GA, Tabu Search (TS), and hybrid algorithms ACS-GA were compared. The results show that our hybrid algorithm ACS-GA outperforms the results of the single algorithm in terms of solution quality and stability overall. This research provides a better solution to optimizing TSP by proposing a novel hybrid metaheuristic algorithm.