Parallelization of the ant colony optimization for the shortest path problem using OpenMP and CUDA

Finding efficient vehicle routes is an important logistics problem which has been studied for several decades. Metaheuristic algorithms offer some solutions for that problem. This paper deals with GPU implementation of the ant colony optimization algorithm (ACO), which can be used to find the best vehicle route between designated points. The algorithm is applied on finding the shortest path in several oriented graphs. It is embarrassingly parallel, since each ant constructs a possible problem solution independently. Results of sequential and parallelized implementation of the algorithm are presented. A discussion focused on implementing ACO using OpenMP and CUDA provides a basis for analysis of different results achieved on those two platforms.