Parameter Tuning for Ant Colony Optimization based Multiple Traveling Salesman Problem Optimization

In the realm of combinatorial optimization, the Multiple Traveling Salesman Problem (MTSP) presents a unique challenge by requiring optimal routes for multiple salesmen. This study introduces an innovative approach that integrates Ant Colony Optimization (ACO) and the 2-opt heuristic to tackle an MTSP with 50 cities and 5 salesmen, characterized by heterogeneous city categories and differentiated visitation requirements. The proposed ACO algorithm, inspired by the natural foraging behavior of ants, employs a dynamic pheromone updating mechanism to guide the search process toward optimal or near-optimal solutions. Additionally, we place a strong emphasis on investigating the effects of ACO parameter variations, including the pheromone importance factor, heuristic factor, number of iterations, and the size of the ant colony. Concurrently, the 2-opt heuristic, known for eliminating route crossings to enhance path efficiency, is applied as a post-optimization step to refine the solutions obtained from ACO. A series of computational experiments was conducted to evaluate the performance of the combined ACO and 2-opt approach, demonstrating significant improvements in solution quality and computational efficiency. Our results indicate that optimal parameter settings can significantly enhance the ACO’s ability to find near-optimal solutions more efficiently.