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

  • Juraj Fosin
  • Davor Davidović
  • Tonči Carić
Keywords: TSP, Local Search, ILS, GPU, CUDA

Abstract

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.

Author Biography

Juraj Fosin

Intelligent Transportation Systems Department

Head of Chair For Applied Computing

References

Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman, 1979

http://graphics.stanford.edu/projects/brookgpu/, last accessed on June 2012

http://www.nvidia.com/, last accessed on June 2012

http://www.amd.com/us/products/technologies/stream-technology/pages/stream-technology.aspx, last accessed on June 2012

Johnson, D.S., McGeoch, L.A.: The traveling salesman problem: a case study in local optimization, Local Search in Combinatorial Optimization, 1997

Mertz, P., Freisleben, B.: Memetic algorithms for the traveling salesman problem, Complex Systems, 2001

Johnson, D.S., McGeoch, L.A.: Experimental Analysis of Heuristics for the STSP, The Traveling Salesman Problem and Its Variations, volume 12, Springer US, 2004

Hoos, H.H., Stützle, T.: Stochastic Local Search, Morgan Kaufman, 2005

Bentley, J.J.: Fast algorithms for geometric traveling salesman problems, ORSA Journal on Computing, 1992

Croes, G.A.: A method for solving traveling-salesman problems, Operations Research, 1958

Lin, S.: Computer solutions of the traveling salesman problem, Bell System Tech, 1965

Lin, S., Kernighan, B.W.: An effective heuristic algorithm for the traveling salesman problem, Operations Research, 1973

Helsgaun, K.: General k-opt submoves for the Lin- Kernighan TSP heuristic, Mathematical Programming Society, 2009

Zhao, J., Liu, Q., Wang, W., Wei, Z., Shi, P.: A parallel immune algorithm for traveling salesman problem and

its application on cold rolling scheduling, Information Sciences, 2011

Luong, T.V., Melab, N., Talbi, E.G.: GPU-based island model for evolutionary algorithms, Proceedings of the 12th annual conference on Genetic and evolutionary computationGECCO ’10, ACM, 2010

Dorigo, M., Maniezzo, V., Colorni, A.: The ant system:

Optimization by a colony of cooperating agents, IEEE Transactions on Systems, Man, and Cybernetics-Part B, vol. 26, pp.2941, 1996

Bai, H., Yang, D., Li, X., He, L., Yu, H.: Max-min ant system on GPU with CUDA, Fourth International Conference on Innovative Computing, Information and Control, 2009

You, Y.: Parallel ant system for traveling salesman problem on GPUs, Eleventh Annual Conference on Genetic and Evolutionary Computation, 2009

Lin, Y., Cai, H., Xiao, J., Zhang, J.: Pseudo parallel ant colony optimization for continuous functions, International Conference on Natural Computation, 2007

Cecilia, J., Garcia, J., Nisbet, A., Amos, M., Ujaldon, M.: Enhancing data parallelism for ant colony optimisation on GPUs, Journal of Parallel and Distributed Computing ,2012

O’Neil, M.A., Tamir, D., Burtscher, M.: A parallel gpu version of the traveling salesman problem, International Conference on Parallel and Distributed Processing Techniques and Applications, 2011

Luong, T.V., Melab, N., Talbi, E.G.: Parallel local search on GPU, Report 6915, INRIA, 2009

Helsgaun, K.: An Effective Implementation of the LinKernighan Traveling Salesman Heuristic, European Journal of Operational Research, 2000

CUDA C Programming Guide, http://docs.nvidia.com/ cuda/cuda-c-programming-guide/index.html, last accessed on June 2012

Reinelt, G.: TSPLIB – A traveling salesman problem library, ORSA JOURNAL ON COMPUTING 3 (1991) 376–384

URL for Euclidian CRO TSP, http://fulir.irb.hr/504/1/ CRO6857.tsp

Published
2013-06-19
How to Cite
1.
Fosin J, Davidović D, Carić T. A GPU Implementation of Local Search Operators for Symmetric Travelling Salesman Problem. Promet [Internet]. 2013Jun.19 [cited 2024May30];25(3):225-34. Available from: http://traffic.fpz.hr/index.php/PROMTT/article/view/300
Section
Articles