Local search is another type of heuristic algorithms for the TSP. One of the simplest local search approaches might be the \(k\) -opt method ([1]} [1]}), which replaces \(k\)  edges of the current tour at each search step. Traditional \(k\) -opt approach needs to determine the value of \(k\) , and the computation time increases rapidly as \(k\)  increases. To handle this issue, Lin and Kernighan ([3]}) propose a variable-depth search method called Lin-Kernighan (LK) algorithm, where the \(k\) -opt is partially searched with a smart pruning strategy, thus LK relieves the limitation of fixing \(k\)  in the \(k\) -opt. Moreover, LK defines the candidate sets to reduce the search scope of \(k\) -opt and improve the efficiency. In LK, each city has its own candidate set recording five (default value) other nearest cities. And the edges to be added in \(k\) -opt process must be selected from the candidate sets since LK believes that the edges with shorter distance are more likely to appear in the optimal solution. Due to the above advantages of LK heuristic, LK had been known as the most effective TSP heuristic approach since proposed in 1973 until 1990.
