%0 Journal Article %A Wen-Bao Qiao and Jean-Charles Créput %D 2017 %J International Journal of Electronics and Communication Engineering %B World Academy of Science, Engineering and Technology %I Open Science Index 123, 2017 %T Parallel 2-Opt Local Search on GPU %U https://publications.waset.org/pdf/10006699 %V 123 %X To accelerate the solution for large scale traveling salesman problems (TSP), a parallel 2-opt local search algorithm with simple implementation based on Graphics Processing Unit (GPU) is presented and tested in this paper. The parallel scheme is based on technique of data decomposition by dynamically assigning multiple K processors on the integral tour to treat K edges’ 2-opt local optimization simultaneously on independent sub-tours, where K can be user-defined or have a function relationship with input size N. We implement this algorithm with doubly linked list on GPU. The implementation only requires O(N) memory. We compare this parallel 2-opt local optimization against sequential exhaustive 2-opt search along integral tour on TSP instances from TSPLIB with more than 10000 cities. %P 313 - 317