Title: An improved particle swarm optimisation for solving generalised travelling salesman problem

Authors: Yu-xi Gao; Yan-min Wang; Zhi-li Pei

Addresses: Department of Computer Science, Jilin Business and Technology College, 130062, China ' Department of Computer Science, Jilin Business and Technology College, 130062, China ' College of Computer Science and Technology, Key Laboratory of Symbol Computation and Knowledge Engineering of Ministry of Education, Jilin University, 130012, China; College of Computer Science and Technology, Inner Mongolia University for the Nationalities, Tongliao 028000, China

Abstract: In this paper, we present an improved algorithm based on an improved particle swarm optimisation (PSO), and we use it to solve the generalised travelling salesman problem (GTSP). We design a novel optimised implementation approach to reduce the processing costs involved with routing in the conventional PSO and we also improved the performance of the PSO. As the main work of this paper, we use the improved algorithm in TSP based on the 'generalised chromosome' coding technique of the GTSP, the above proposed method is extended for solving the GTSP. Two local search techniques are also added into the method. In order to test our methods, we use four GTSP problems for benchmarking. The results show that the method is effective for solving the GTSP problem. The proposed PSO-based algorithm could provide a suitable approach for solving the GTSP.

Keywords: particle swarm optimisation; improved PSO; generalised travelling salesman problem; GTSP; local search.

DOI: 10.1504/IJCSM.2012.051624

International Journal of Computing Science and Mathematics, 2012 Vol.3 No.4, pp.385 - 393

Received: 26 Oct 2012
Accepted: 05 Nov 2012

Published online: 30 Aug 2014 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article