Particle swarm optimization with partial search for solving traveling salesman problem

• Main Authors: Akhand, M. A. H, Akter, Shahina, Shill, P.C., Rahman, M.M. Hafizur
• Format: Article
• Language: English
• Published: Green University Press 2014
• Subjects: TK7800 Electronics. Computer engineering. Computer hardware. Photoelectronic devices
• Online Access: http://irep.iium.edu.my/39781/1/J17-03_PSOPS-TSP_GreenUnv.pdf; http://irep.iium.edu.my/39781/; http://green.edu.bd/academics/journal/45-gubjse/525-gubjse-volume-1-issue-1-july-2014

Traveling Salesman Problem (TSP) is a well-studied combinatorial optimization problem and recently a number of Particle Swarm Optimization (PSO) based methods have been investigated to solve TSP. Among the popular conventional PSO based methods, several methods consider Swap Sequence (SS) and Swap Operator (SO) for velocity operation to get a new solution (i.e., TSP tour) from an existing tour. A method calculates velocity SS for each particle and then update a particle applying all its SOs. This study outlined an effective technique, called Partial Search (PS), that deals with the optimal implementation of calculated velocity SS owing to achieve better solution, i.e., tour with lower cost. Since every individual SO of a SS generates a tenable solution, PS technique explores intermediate tours after implementing each and every SO. PS technique is found easy to employ in the conventional methods because all follow same method for particle update. Two PSO based methods have been proposed in this study employing PS technique in two popular conventional methods. A proposed method (with PS) outperformed its convention method when tested on a large number of benchmark TSPs. Experimental studies revealed that PS is an effective technique to get better solution as well as to trim down overall problem solving time.