9742

A GPU Implementation of Local Search Operators for Symmetric Travelling Salesman Problem

Juraj Fosin, Davor Davidovic, Tonci Caric
Faculty of Transport and Traffic Sciences, Vukeliceva 4, 10000 Zagreb, Croatia
PROMET – Traffic & Transportation, Vol. 25, No. 3, 225-234, 2013

@article{fosin2013gpu,

   title={A GPU Implementation of Local Search Operators for Symmetric Travelling Salesman Problem},

   author={Fosin, Juraj and Davidovi{‘c}, Davor and Cari{‘c}, Ton{v{c}}i},

   journal={PROMET-Traffic&Transportation},

   volume={25},

   number={3},

   pages={225–234},

   year={2013}

}

Download Download (PDF)   View View   Source Source   

1115

views

The Travelling Salesman Problem (TSP) is one of the most studied combinatorial optimization problem which is significant in many practical applications in transportation problems. The TSP problem is NP-hard problem and requires large computation power to be solved by the exact algorithms. In the past few years, fast development of general-purpose Graphics Processing Units (GPUs) has brought huge improvement in decreasing the applications’ execution time. In this paper, we implement 2-opt and 3-opt local search operators for solving the TSP on the GPU using CUDA. The novelty presented in this paper is a new parallel iterated local search approach with 2-opt and 3-opt operators for symmetric TSP, optimized for the execution on GPUs. With our implementation large TSP problems (up to 85,900 cities) can be solved using the GPU. We will show that our GPU implementation can be up to 20x faster without losing quality for all TSPlib problems as well as for our CRO TSP problem.
No votes yet.
Please wait...

* * *

* * *

HGPU group © 2010-2017 hgpu.org

All rights belong to the respective authors

Contact us: