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.
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
Guest Editor: Eleonora Papadimitriou, PhD
Editors: Dario Babić, PhD; Marko Matulin, PhD; Marko Ševrović, PhD.
The mission of our journal is to provide high quality communication of research results, which is crucial for the effectiveness of scientific research, the promotion of scientific information, new ideas, and original research in the field of traffic and transportation engineering.
1848-4069
0353-5320
Proud publisher
Accelerating Discoveries in Traffic Science |
2024 © Promet - Traffic&Transportation journal
