A GPU implementation of local search operators for symmetric travelling salesman problem

Fosin, Juraj; Davidović, Davor; Carić, Tonči (2013) A GPU implementation of local search operators for symmetric travelling salesman problem. Promet - Traffic & Transportation, 25 (3). pp. 225-234. ISSN 0353-5320

Preview

PDF - Published Version Available under License Creative Commons Attribution. Download (865kB) | Preview

Abstract

The Travelling Salesman Problem (TSP) is one of the most studied combinatorial optimization problem which is significant in many practical applications in transportation field. The TSP is an NP-hard problem and requires large computational power to be optimally solved by exact algorithms. In the past few years, fast development of general-purpose Graphics Processing Units (GPUs) has brought huge improvement in decreasing the algorithms execution time. In this paper, we implement 2-opt and 3-opt local search operators for solving the TSP on the GPU using its respective application programming interface. The novelty presented in this paper is a new parallel iterated local search implementation 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 show that our GPU implementation can be up to 27 times faster than CPU implementation without losing solution quality for TSPlib problems as well as for our CRO TSP problem.

Item Type:	Article
Uncontrolled Keywords:	travelling salesman problem; local search operator; 3-opt; parallel iterated local search; graphics processing units; CUDA
Subjects:	TECHNICAL SCIENCES > Computing TECHNICAL SCIENCES > Traffic and Transport Technology
Divisions:	Center for Informatics and Computing
Depositing User:	Davor Davidović
Date Deposited:	23 Sep 2013 14:28
URI:	http://fulir.irb.hr/id/eprint/633
DOI:	10.7307/ptt.v25i3.300

Actions (login required)

View Item