Particle Swarm Optimization-Based Algorithms for Traveling Salesman Problem
Tian-Le Jin, Qi-Jia Jiang, Zhao-Kun Shao · 2025
Particle Swarm Optimization (PSO) is an optimization technique grounded in swarm intelligence, drawing inspiration from how bird flocks or fish schools coordinate their movements. In this work, we propose a novel discrete PSO (DPSO) method tailored for the Traveling Salesman Problem (TSP), a well-known NP-hard challenge that seeks the shortest route visiting each city exactly once before returning to the start. Because TSP is inherently discrete, we adapt PSO to handle city-sequence permutations effectively. To reduce unnecessary elongations of the travel path, our approach introduces a specialized crossover deletion mechanism that eliminates disadvantageous route crossovers. In an experimental study using a 50-city TSP, comparative results demonstrate that the proposed DPSO not only delivers high-quality solutions but also accelerates convergence and enhances solution accuracy.