The traveling salesman problem (TSP) is an important computer science optimization problem with numerous real-world applications. There is a huge body of literature on TSP solutions. Following are a few GPU and Intel Xeon Phi accelerated solutions.
TSPGPU v2.1 is a GPU-accelerated heuristic solver for the symmetric Traveling Salesman Problem with up to 32767 cities, based on iterative hill climbing with 2-opt local search. It supports much larger problem sizes than v1.0 and is probably the fastest available 2-opt implementation. With 240 climbers, it reaches 60 billion moves per second on a K40 GPU for problem sizes above 10000 cities. The source code can be requested via email from firstname.lastname@example.org.
- GACO: Accelerating solution of the TSP by ant colony simulation.
As a population-based algorithm, Ant Colony Optimization (ACO) is intrinsically massively parallel, and therefore it is expected to be well-suited for implementation on GPUs (Graphics Processing Units). In this paper, we present a novel ant colony optimization algorithm (called GACO), which based on Compute Unified Device Architecture (CUDA) enabled GPU. In GACO algorithm, we utilize some novel optimizations, such as hybrid pheromone matrix update, dynamic nearest neighbor path construction, and multiple ant colony distribution, which result in a higher speedup and a better quality solutions compared to other peer of algorithms. GACO is tested by the Traveling Salesman Problem (TSP) benchmark, and the experimental results show a total speedup up to 40.1× and 35.7× over implementation of Ant Colony System (ACS) and Max-min Ant System (MMAS), respectively.
Abstract—This paper presents a high performance GPU accelerated implementation of 2-opt local search algorithm for the Traveling Salesman Problem (TSP). GPU usage significantly decreases the execution time needed for tour optimization, however it also requires a complicated and well tuned implementation. With the problem size growing, the time spent on local optimization comparing the graph edges grows significantly. According to our results based on the instances from the TSPLIB library, the time needed to perform a simple local search operation can be decreased approximately 5 to 45 times compared to a corresponding parallel CPU code implementation using 6 cores. The code has been implemented in OpenCL and as well as in CUDA and tested on AMD and NVIDIA devices. The experimental studies show that the optimization algorithm using the GPU local search converges from up to 300 times faster compared to the sequential CPU version on average, depending on the problem size. The main contributions of this paper are the problem division scheme exploiting data locality which allows to solve arbitrarily big problem instances using GPU and the parallel implementation of the algorithm itself.
Think optimized delivery of materials and goods:
It it expected this article will evolve as new approaches appear and are pointed out by readers.