An Improved Wolf Pack Algorithm with Two-Part Encoding Technique for Solving Multiple Traveling Salesman Problem

The Multiple Traveling Salesman Problem (MTSP), an extension of the Traveling Salesman Problem (TSP), involves assigning multiple salesmen to visit a series of cities and optimizing the visiting order to minimize the total distance. As a typical NP-hard problem, the conventional approach is to develop approximate or heuristic solutions. In this paper, we propose an Improved Wolf Pack Algorithm (IWPA) to solve this problem. First, the K-means clustering algorithm is used to preprocess cities, dividing them into clusters managed by the nearest salesman. Then, the greedy strategy plans the initial path for each salesman, thus forming a high-quality initial solution to guide the population's search direction. Finally, the solution and the randomly generated population are introduced into the wolf pack algorithm, represented by a two-part encoding technique to minimize the size of the problem search space. By simulating wolves' predation strategies, the algorithm iteratively performs local and global optimizations. Experimental results show that the algorithm achieves good performance on MTSPs of different scales, effectively reducing total distance and path crossings, and demonstrating better task allocation and path planning.