Pheromone Mutation-Based Ant Colony Optimization for Multiple Traveling Salesman Problem
Mengmeng Gao, Weijie Yu, Bing Sun, Tong Qian, Yu Bai · 2025
The multiple traveling salesman problem (MTSP) has important application value in many fields, such as scheduling, manufacturing, and logistics. In this problem, a group of salesmen collaborate to visit a set of cities. To efficiently solve MTSP, it is considered as a two-layer optimization problem. In the upper layer, K-means clustering algorithm is applied to assign cities to salesmen. In the lower layer, the routes of each salesman are optimized by a pheromone mutation-based ant colony optimization (PM-ACO) algorithm. In PM-ACO, a novel pheromone mutation strategy is proposed to help the colony jump out of the local optima by perturbing the pheromone on some edges. To further enhance convergence and diversity, the 2-opt algorithm is employed to search the neighborhood of high-quality solutions by reversing edges. Experimental results on TSPLIB instances with different sizes demonstrate that the proposed PM-ACO outperforms other improved algorithms, showing its superior performance.