Information Processing Letters 103 (2007) 169–176
www.elsevier.com/locate/ipl
Particle swarm optimization-based algorithms
for TSP and generalized TSP
X.H. Shi
a
,Y.C.Liang
a,b,∗
,H.P.Lee
b,c
,C.Lu
b
,Q.X.Wang
a
a
College of Computer Science and Technology, Jilin University, Key Laboratory of Symbol Computation and Knowledge Engineering
of the Ministry of Education, Changchun 130012, China
b
Institute of High Performance Computing, Singapore 117528, Singapore
c
Department of Mechanical Engineering, National University of Singapore, 9 Engineering Drive 1, Singapore 119260, Singapore
Received 31 July 2005; received in revised form 10 February 2007
Available online 31 March 2007
Communicated by Wen-Lian Hsu
Abstract
A novel particle swarm optimization (PSO)-based algorithm for the traveling salesman problem (TSP) is presented. An uncertain
searching strategy and a crossover eliminated technique are used to accelerate the convergence speed. Compared with the existing
algorithms for solving TSP using swarm intelligence, it has been shown that the size of the solved problems could be increased by
using the proposed algorithm.
Another PSO-based algorithm is proposed and applied to solve the generalized traveling salesman problem by employing the
generalized chromosome. Two local search techniques are used to speed up the convergence. Numerical results show the effective-
ness of the proposed algorithms.
© 2007 Elsevier B.V. All rights reserved.
Keywords: Algorithms; Particle swarm optimization; Traveling salesman problem; Generalized traveling salesman problem; Swap operator
1. Introduction
The Particle swarm optimization (PSO) algorithm,
originally developed by Kennedy and Eberhart [1], is
a method for optimization on metaphor of social behav-
ior of flocks of birds and/or schools of fish. Similar to
genetic algorithms (GAs), the PSO is also an optimizer
based on population. The system is initialized firstly in a
set of randomly generated potential solutions, and then
is performed to search for the optimum one iteratively.
*
Corresponding author.
E-mail address: ycliang@jlu.edu.cn (Y.C. Liang).
It finds the optimum solution by swarms following the
best particle. Compared to GAs, the PSO has much
better intelligent background and could be performed
more easily. According to its advantages, the PSO is not
only suitable for scientific research, but also engineer-
ing applications. Presently the PSO has attracted broad
attention in the fields of evolutionary computing, op-
timization and many others [2–5]. Although the PSO
is developed for continuous optimization problems ini-
tially, there have been some reported works focused on
discrete problems recently [6,7].
The traveling salesman problem (TSP) is a well-
known and extensively studied benchmark for many
new developments in combinatorial optimization [8,9],
0020-0190/$ – see front matter © 2007 Elsevier B.V. All rights reserved.
doi:10.1016/j.ipl.2007.03.010