Pheromone Mutation-Based Ant Colony Optimization for Multiple Traveling Salesman Problem

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.