A parallel 2-opt algorithm for the traveling salesman problem

We present a scalable parallel local search algorithm based on data parallelism. The concept of distributed neighborhood structures is introduced, and applied to the Traveling Salesman Problem (TSP). Our parallel local search algorithm finds the same quality solutions as the classical 2-opt algorithm and has a good speed-up. The algorithm is implemented on a Parsytec GCel, consisting of 512 transputers. Its performance is empirically analyzed for TSP instances with several thousands of cities. Author Keywords: Local search; Traveling Salesman Problem; Data parallelis