Multi-Subdomain Grouping-Based Particle Swarm Optimization for the Traveling Salesman Problem
Authors:
Open Access
- 18 December 2020
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Access
- Vol. 8, 227497-227510
Abstract
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%.Keywords
Funding Information
- Key Research and Development Project of Shandong Province (2018YFJH0704, 2019GHZ007)
- National Natural Science Foundation of China (51909127)
- Doctoral Scientific Research Starting Foundation of Qingdao University of Science and Technology
This publication has 44 references indexed in Scilit:
- A new hybrid method based on Particle Swarm Optimization, Ant Colony Optimization and 3-Opt algorithms for Traveling Salesman ProblemApplied Soft Computing, 2015
- A new particle swarm optimization algorithm with adaptive inertia weight based on Bayesian techniquesApplied Soft Computing, 2015
- Hybrid evolutionary fuzzy learning scheme in the applications of traveling salesman problemsInformation Sciences, 2014
- Application of an Improved Ant Colony Optimization on Generalized Traveling Salesman ProblemEnergy Procedia, 2012
- Honey bees mating optimization algorithm for the Euclidean traveling salesman problemInformation Sciences, 2011
- A Hybrid Multi-Swarm Particle Swarm Optimization algorithm for the Probabilistic Traveling Salesman ProblemComputers & Operations Research, 2010
- General k-opt submoves for the Lin–Kernighan TSP heuristicMathematical Programming Computation, 2009
- Two-level genetic algorithm for clustered traveling salesman problem with application in large-scale TSPsTsinghua Science and Technology, 2007
- Acceleration factor harmonious particle swarm optimizerInternational Journal of Automation and Computing, 2006
- Genetic Algorithms and the Optimal Allocation of TrialsSIAM Journal on Computing, 1973