A highly-parallel TSP solver for a GPU computing platform

摘要: The traveling salesman problem (TSP) is probably the most widely studied combinatorial optimization and has become a standard testbed for new algorithmic ideas. Recently use of GPU (Graphics Processing Unit) to accelerate non-graphics computations attracted much attention due its high performance low cost. This paper presents novel method solve TSP with based on CUDA architecture. proposed highly parallelizes serial metaheuristic algorithm which genetic OX (order crossover) operator 2-opt local search. experiments an NVIDIA GeForce GTX285 single core 3.0 GHz Intel Core2 Duo E6850 CPU show that our implementation about up 24.2 times faster than corresponding implementation.