An Improved Set-based Particle Swarm Optimization for Solving the Multiple Traveling Salesman Problem
Yidan Zhang, Wei–Jie Yu, Tong Qian, Bing Sun, Yu Bai · 2025
This paper proposes an improved set-based par-ticle swarm optimization (IS-PSO) algorithm to extend the applicability of particle swarm optimization (PSO) to discrete optimization problems, such as the multiple traveling salesman problem (MTSP). In IS-PSO, K-means clustering is employed to decompose the MTSP into multiple simpler traveling salesman problems (TSPs), with each group of cities assigned to a single salesman. Then the routes of multiple salesmen are optimized by set-based PSO simultaneously, and a 2-opt-based local search method is integrated to enhance solution quality and diversity. To further improve search efficiency, a parameter adaptation strat-egy is introduced to adjust the inertia weight and acceleration coefficients during the search process. Experimental results on 10 TSPLIB instances with different scales demonstrate that IS- PSO outperforms two classic and two advanced algorithms, showing its potential in solving MTSPs.