Particle swarm optimization with partial search for solving traveling salesman problem

Akhand, M. A. H and Akter, Shahina and Shill, P.C. and Rahman, M.M. Hafizur (2014) Particle swarm optimization with partial search for solving traveling salesman problem. Green University Bangladesh (GUB) Journal of Science and Engineering, 1 (1). pp. 16-25. ISSN 2409-0476

PDF - Published Version Restricted to Registered users only Download (822kB) | Request a copy

Abstract

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.

Item Type:	Article (Journal)
Additional Information:	6724/39781
Uncontrolled Keywords:	Swap Sequence, Swap Operator, Partial Search, Particle Swarm Optimization, Traveling Salesman Problem.
Subjects:	T Technology > TK Electrical engineering. Electronics Nuclear engineering > TK7800 Electronics. Computer engineering. Computer hardware. Photoelectronic devices
Kulliyyahs/Centres/Divisions/Institutes (Can select more than one option. Press CONTROL button):	Kulliyyah of Information and Communication Technology Kulliyyah of Information and Communication Technology
Depositing User:	Dr. M.M. Hafizur Rahman
Date Deposited:	15 Dec 2014 10:14
Last Modified:	19 Jun 2018 15:18
URI:	http://irep.iium.edu.my/id/eprint/39781

Actions (login required)

View Item