A Parallel GPU Version of the Traveling Salesman Problem
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
@article{o2011parallel,
title={A Parallel GPU Version of the Traveling Salesman Problem},
author={O’Neil, M.A. and Tamir, D. and Burtscher, M.},
year={2011}
}
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.
December 16, 2011 by hgpu
