Abstract:

 Initialization construction strategy is an important phase of the LinKernighan algorithm, which is known as one of the most efficient heuristic methods to solve the traveling salesman problem. In most past research, only one construction strategy was adopted, but there was little  research on what strategies could be used in the LinKernighan algorithm and how differently  they perform. 8 construction strategies were analyzed, and 4 of them were found applicable  for LinKernighan initialization. Numerical experiments and computational results with 6 TSPLIP instances showed that  the 4 construction strategies proposed were effective and efficient initialization methods. Additionally, it was proved that the Clark Wright algorithm had the best convergence speed, while the nearest insertion algorithm had the best optimization rate.

Key words: LinKernighan, initial path, heuristic algorithm, the traveling salesman problem, performance evaluation