A Distributed Chained Lin-Kernighan Algorithm for TSP Problems

The Chained Lin-Kernighan algorithm (CLK) is one of the best heuristics to solve Traveling Salesman Problems (TSP). In this paper a distributed algorithm is proposed, were nodes in a network locally optimize TSP instances by using the CLK algorithm. We show that the distributed variant finds better tours compared to the original CLK given the same total amount of computation time. Hence, the cooperation of the processes in the distributed algorithm increases the effectiveness of the approach beyond the maximally achievable reduction in computation time due to parallelization. E.g. for TSP instance fl3795, the original CLK got stuck in local optima in each of 10 runs, whereas the distributed algorithm found optimal tours in each run requiring less than 10 CPU minutes per node on average in an 8 node setup.