Accelerating 2-opt and 3-opt Local Search Using GPU in the Travelling Salesman Problem
Citations Over TimeTop 10% of 2012 papers
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.
Related Papers
- → MAX-MIN Ant System and local search for the traveling salesman problem(2002)825 cited
- → Investigating the Influence of Adding Local Search to Search Algorithms(2017)4 cited
- → A new approach to the traveling salesman problem(2022)1 cited
- Diversified Local Search for the Traveling Salesman Problem(2011)