%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