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


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.