Title: The optimisation of travelling salesman problem based on parallel ant colony algorithm

Authors: Amin Jarrah; Ali S. Al Bataineh; Abedalmuhdi Almomany

Addresses: Department of Computer Engineering, Hijjawi Faculty for Engineering Technology, Yarmouk University, Irbid, Jordan ' Department of Electrical and Computer Engineering, David Crawford School of Engineering, Norwich University, Northfield, Vermont, USA ' Department of Computer Engineering, Hijjawi Faculty for Engineering Technology, Yarmouk University, Irbid, Jordan

Abstract: General search algorithms offer some solutions to solve and avoid the constraints of the finding shortest path problem. Ant Colony Optimisation (ACO) is a meta-heuristic search-based and probabilistic searching technique for an optimal path. However, ACO is computationally intensive and may not achieve the desired performance. Thus, a parallel implementation of the ACO for the travelling salesman problem is proposed and implemented on FPGA platform. Different optimisation techniques are adopted and applied to enhance the performance of the algorithm. The overall results have shown a 28-fold improvement in performance due to the applied optimisation techniques with different numbers of ants and iterations. The speedup is improved by increasing the number of iterations/ants which further validated the proposed method. The network on chip methodology was also adopted to connect the ants where a comprehensive analysis of FPGA chip traffic is modelled and emulated to get the best architecture.

Keywords: ant colony optimisation; FPGA; TSP problem; high-level synthesis; parallel architecture; optimisation techniques.

DOI: 10.1504/IJCAT.2022.129382

International Journal of Computer Applications in Technology, 2022 Vol.69 No.4, pp.309 - 321

Received: 03 Jul 2021
Accepted: 27 Oct 2021
Published online: 07 Mar 2023 *

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