Accelerating 2-opt and 3-opt Local Search Using GPU in the Travelling Salesman Problem

Abstract

We are presenting a high-performance GPU implementation of a 2-opt and 3-opt algorithms used to solve the Traveling Salesman Problem. The main idea behind it is to take a route that crosses over itself and reorder it so that it does not. It is a very important local search technique and using GPU to parallelize the search greatly decreases the time needed to find the best edges to be swapped in a route. Our results show, that at least 90% of the time during an Iterative Local Search is spent on the 2-opt itself. Our result show that by using our algorithm for GPU, the time need to find optimal swaps can be decreased approximately 100 times in case of 2-opt compared to a sequential CPU code and more than 220-fold speedup can be observed in case of 3-opt search achieving more than 430 GFLOPS on a single Tesla C2075 GPU.