IEEE Access (Jan 2021)
An Enhanced Swap Sequence-Based Particle Swarm Optimization Algorithm to Solve TSP
Abstract
The Traveling Salesman Problem (TSP) is a combinatorial optimization problem that is useful in a number of applications. Since there is no known polynomial-time algorithm for solving large scale TSP, metaheuristic algorithms such as Ant Colony Optimization (ACO), Bee Colony Optimization (BCO), and Particle Swarm Optimization (PSO) have been widely used to solve TSP problems through their high quality solutions. Several variants of PSO have been proposed for solving discrete optimization problems like TSP. Among them, the basic algorithm is the Swap Sequence based PSO (SSPSO), however, it does not perform well in providing high quality solutions. To improve the performance of the swap sequence based PSO, this paper introduces an Enhanced Swap Sequence based PSO (Enhanced SSPSO) algorithm by integrating the strategies of the Expanded PSO (XPSO) in the swap sequence based PSO. This is because although XPSO is only suitable for solving continuous optimization problems, it has a high performance among the variants of PSO. In our work, the TSP problem is used to model a package delivery system in the Kuala Lumpur area. The problem set consists of 50 locations in Kuala Lumpur. Our aim is to find the shortest route in the delivery system by using the enhanced swap sequence based PSO. We evaluate the algorithm in terms of effectiveness and efficiency while solving TSP. To evaluate the proposed algorithm, the solutions to the TSP problem obtained from the proposed algorithm and swap sequence based PSO are compared in terms of the best solution, mean solution, and time taken to converge to the optimal solution. The proposed algorithm is found to provide better solutions with shorter paths when applied to TSP as compared to swap sequence based PSO. However, the swap sequence based PSO is found to converge faster than the proposed algorithm when applied to TSP.
Keywords
