Velocity tentative PSO: An optimal velocity implementation based particle swarm optimization to solve traveling salesman problem

• Main Authors: M. A. H., Akhand, Shahina, Akter, M. A., Rashid
• Format: Article
• Language: English
• Published: 2015
• Subjects: QA75 Electronic computers. Computer science
• Online Access: http://eprints.unisza.edu.my/6565/1/FH02-FSTK-15-03714.jpg; http://eprints.unisza.edu.my/6565/
• Institution: Universiti Sultan Zainal Abidin

This paper introduces an effective Particle Swarm Optimization (PSO) based algorithm for solving Traveling Salesman Problem (TSP). Among prominent PSO based methods, the proposed Velocity Tentative PSO (VTPSO) considers Swap Sequence (SS) for velocity operation of the particles. A velocity SS is a collection of several Swap Operators (SOs) where each one indicates two positions in a tour those might be swapped. The existing methods apply all the SOs of the calculated SS on a solution to get a new solution. Conversely, the proposed VTPSO considers the calculated SS as the tentative velocity and checks the tentative solutions when applies the SOs one after another sequentially. The best tentative tour with a portion of SS is considered as the next solution point of a particle in VTPSO. Such intermediate tentative tour evaluation not only helps to get better solution but also reduces overall computational time. The experimental results on a large number of benchmark TSPs reveal that the proposed VTPSO is able to produce better tour compared to other prominent existing methods.