Dr. Donald Davendra is Professor and Chair of Computer Science at Central Washington University, USA. He has a PhD in Technical Cybernetics from Tomas Bata University in Zlín, Czech Republic. His research background is in optimization algorithms, intelligent manufacturing systems, high-performance computing, and chaos systems. He has edited three books and numerous journal papers, book chapters, and conference publications in the field of computational intelligence.
The Traveling Salesman Problem (TSP) is widely considered one of the most intensively studied problems in computational mathematics and operations research. Since its inception, it has become the poster child for computational complexity research. A number of problems have been transformed to a TSP problem and its application base now extends into scheduling, manufacturing, routing, and logistics. With the advent of high-performance computing and advanced meta-heuristics such as GPU programming and swarm-based algorithms, the TSP problem is positioned firmly as the go-to problem for the development of the next generation of high-performance intelligent heuristics. This book looks to leverage some of these new paradigms for both students and researchers in this field.
Go to the bookPart of the book: Traveling Salesman Problem
This research involves the development of a compute unified device architecture (CUDA) accelerated 2-opt local search algorithm for the traveling salesman problem (TSP). As one of the fundamental mathematical approaches to solving the TSP problem, the time complexity has generally reduced its efficiency, especially for large problem instances. Graphic processing unit (GPU) programming, especially CUDA has become more mainstream in high-performance computing (HPC) approaches and has made many intractable problems at least reasonably solvable in acceptable time. This chapter describes two CUDA accelerated 2-opt algorithms developed to solve the asymmetric TSP problem. Three separate hardware configurations were used to test the developed algorithms, and the results validate that the execution time decreased significantly, especially for the large problem instances when deployed on the GPU.
Part of the book: Novel Trends in the Traveling Salesman Problem