A GPU Implementation of Local Search Operators for Symmetric Travelling Salesman Problem
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.
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
Authors who publish with this journal agree to the following terms:
- Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
- Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
- Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (See The Effect of Open Access).
