Massive 2-opt and 3-opt Moves with High Performance GPU Local Search to Large-Scale Traveling Salesman Problem

摘要

2-opt, 3-opt or k-opt heuristics are classical local search algorithms for traveling salesman problems (TSP) in combinatorial optimization area. This paper introduces a judicious decision making methodology of offloading which part of the k-opt heuristic works in parallel on Graphics Processing Unit (GPU) while which part remains sequential, called "multiple k-opt evaluation, multiple k-opt moves", in order to simultaneously execute, without interference, massive 2-/3-opt moves that are globally found on the same TSP tour or the same Euclidean space for many edges, as well as keep high performance for GPU massive k-opt evaluation. We prove the methodology is judicious and valuable because of our originally proposed sequential non-interacted 2-/3-exchange set partition algorithm taking linear time complexity and a new TSP tour representation, array of ordered coordinates-index, in order unveil how to use GPU on-chip shared memory to achieve the same goal as using doubly linked list and array of ordered coordinates for parallel A;-opt implementation. We test this methodology on 22 national TSP instances with up to 71009 cities and with brute initial tour solution. Average maximum 997 non-interacted 2-opt moves are found and executed on the same tour of ch71009.tsp instance in one iteration of our proposed method. Experimental comparisons show that our proposed methodology gets huge acceleration over both classical sequential and a possible current fastest state-of-the-art GPU parallel 2-opt implementation.