A Parallel GPU Version of the Traveling Salesman Problem

Molly A. O’Neil, Dan Tamir, Martin Burtscher
Department of Computer Science, Texas State University, San Marcos, TX
International Conference on Parallel and Distributed Processing Techniques and Applications (PDPTA’11), pp. 348-353, 2011


   title={A Parallel GPU Version of the Traveling Salesman Problem},

   author={O’Neil, M.A. and Tamir, D. and Burtscher, M.},



Download Download (PDF)   View View   Source Source   Source codes Source codes




This paper describes and evaluates an implementation of iterative hill climbing with random restart for determining high-quality solutions to the traveling salesman problem. With 100,000 restarts, this algorithm finds the optimal solution for four out of five 100-city TSPLIB inputs and yields a tour that is only 0.07% longer than the optimum on the fifth input. The presented implementation is highly parallel and optimized for GPU-based execution. Running on a single GPU, it evaluates over 20 billion tour modifications per second. It takes 32 CPUs with 8 cores each (256 cores total) to match this performance.
No votes yet.
Please wait...

* * *

* * *

HGPU group © 2010-2021 hgpu.org

All rights belong to the respective authors

Contact us: