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

IEEE Access

Jiabao Zhong¹  Ying Cui¹  Fengru Yang¹  Shixin Li¹  Penghao Li¹ 

[1] College of Electromechanical Engineering, Qingdao University of Science and Technology, Qingdao, China;

关键词: Traveling salesman problem;    particle swarm optimization;    mutation;    particle competition mechanism;    multi-subdomain grouping;    k-opt;   

DOI  :  10.1109/ACCESS.2020.3045765

来源: DOAJ

【 摘 要 】

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%.

【 授权许可】

Unknown