Parallel Solution for UAV Route Planning Problem using Ant Colony Optimisation on GPU with CUDA

Cekmez U., Ozsiginan M.

22nd IEEE Signal Processing and Communications Applications Conference (SIU), Trabzon, Turkey, 23 - 25 April 2014, pp.1122-1125 identifier identifier

  • Publication Type: Conference Paper / Full Text
  • Doi Number: 10.1109/siu.2014.6830431
  • City: Trabzon
  • Country: Turkey
  • Page Numbers: pp.1122-1125
  • Yıldız Technical University Affiliated: Yes


Using evolutionary algorithms to solve the optimisation problems yields valuable resutls in a reasonable time. But since the problem domain gets bigger, the still results may not be reached in such a short time. Thus, the new approaches to solve this complexity are being used, that is, for now, the GPU parallelization in contrast to traditional CPUs. Additional advantage of GPUs are: low energy consumption, better performance/price ratio, easy access, high bandwidth, etc. In this study, the Ant Colony Optimisation, a type of an evolutionary algorithm, is examined and re-designed so it is executed on GPU in a parallel manner. The aim here is to use it to solve the route planning problems for UAV. In this context, proposed algorithm is tested in a well-known engineering problem (TSP), and experimental evaluation is conducted to compare with CPUs. The obtained results indicate that our approach leads to a considerable speedup. These results explicitly show that GPUs have a potential for acceleration of ACO in a parallel manner, and it allows to solve more complex real world tasks.