Parallelization of the Ant Colony Optimization for the Shortest Path Problem using OpenMP and CUDA
Faculty of Electrical Engineering, University of Sarajevo, Sarajevo, Bosnia and Herzegovina
36th International Convention on Information and Communication Technology, Electronics and Microelectronics, 2013
@article{arnautovic2013parallelization,
title={Parallelization of the Ant Colony Optimization for the Shortest Path Problem using OpenMP and CUDA},
author={Arnautovi{‘c}, Maida and Curi{‘c}, Maida and Dolami{‘c}, Emina and Nosovi{‘c}, Novica},
year={2013}
}
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.
May 30, 2013 by hgpu
