Title: A new hybrid gravitational particle swarm optimisation-ACO with local search mechanism, PSOGSA-ACO-Ls for TSP

Authors: Nizar Rokbani; Pavel Kromer; Ikram Twir; Adel M. Alimi

Addresses: High Institute of Applied Science and Technology of Sousse, ISSAT-Sousse, University of Sousse, Tunisia; REsearch Groups in Intelligent Machines (REGIM-Lab.), National Engineering School of Sfax, Sfax, LR11ES48, 3038, Tunisia ' Department of Computer Science, FEECS, VŠB-Technical University of Ostrava, Czech Republic ' High Institute of Applied Science and Technology of Sousse, ISSAT-Sousse, University of Sousse, Tunisia ' REsearch Groups in Intelligent Machines (REGIM-Lab.), National Engineering School of Sfax, Sfax, LR11ES48, 3038, Tunisia

Abstract: The travelling salesman problem (TSP) is a hard combinatorial optimisation problem and a popular benchmarking problem at the same time. The TSP has also a number of practical real-world and industrial applications, such as routing in internet of things, IoT, networks, path planning in robotics and many others. In this paper, a new hybrid algorithm for the TSP is proposed; it combines gravitational particle swarm optimisation (PSOGSA) and ACO, and is called ant supervised by gravitational particle swarm optimisation with a local search, PSOGSA-ACO-LS. PSOGSA is used to optimise ACO settings while a local search mechanism, 2-Opt is employed by ACO to ameliorate its local solutions. The proposed method is evaluated using a set a test benches from the TSPLib database including: eil51, berlin52, st70, eil76, rat99, eil101, kroA100, and kroA200. Experimental results show that ACO-GPSO-LS is able to solve the set of TSP instances listed below including the large TSP data sets: kroA100, eli101 and kroA200.

Keywords: particle swarm optimisation; PSO; ant colony optimisation; ACO; travelling salesman problem; TSP; local search; hybridisation.

DOI: 10.1504/IJIEI.2019.101565

International Journal of Intelligent Engineering Informatics, 2019 Vol.7 No.4, pp.384 - 398

Received: 05 Jul 2018
Accepted: 16 Jan 2019
Published online: 12 Aug 2019 *

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