Multi-Subdomain Grouping-Based Particle Swarm Optimization for the Traveling Salesman Problem

Traveling salesman problem (TSP) has been widely applied to various fields of production and life. In order to solve the TSP, this work optimizes the architecture of the particle swarm optimization (PSO) by introducing a preprocessing multi-subdomain grouping approach to divide the entire search space into several sub-regions, based on the geographical center of planned cities. To solve subdomain problems, the global search ability of PSO is further improved using genetic mutation and particle competition mechanism to maintain the population diversity during late iterations. An effective simplified 4-opt is finally employed to eliminate path-crossing after connecting all subdomain paths in a time saving way. Comparison with three of our previous algorithms and seven algorithms from other reports reveals that the proposed algorithm shows good performance in both the computing efficiency and route quality. Particularly, it is suitable for small (or medium)-sized TSP problems with relatively percentage error values below 4.8%.