Lin-Kernighan

Solving large-scale traveling salesman problem by the “common edges” method

Existing heuristic algorithms for solving traveling salesman problem, such as Nearest Neighbor, 2-Opt, 3-Opt, Lin-Kernighan and LKH have been investigated in this work. Mentioned algorithms have been compared in terms of calculation time and quality of found solution. Decomposition approach, based on using common edges in multiple solutions, has been proposed.