9487

Parallelization of the Ant Colony Optimization for the Shortest Path Problem using OpenMP and CUDA

Maida Arnautovic, Maida Curic, Emina Dolamic, Novica Nosovic
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}

}

Download Download (PDF)   View View   Source Source   

1438

views

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.
No votes yet.
Please wait...

* * *

* * *

HGPU group © 2010-2017 hgpu.org

All rights belong to the respective authors

Contact us: