LKH is a successful improvement of LK proposed by [1]} ([1]}), which uses an \(\alpha \) -value defined based on the minimum spanning tree ([3]} [3]}) to replace the distance used in LK as a metric in selecting and sorting cities in the candidate set. Due to the better performance of \(\alpha \) -value than distance in determining the candidate cities (or evaluating the quality of the edges), LKH significantly improves the LK heuristic. The LKH algorithm has been further improved by ([5]} [5]}, [7]} [7]}, [9]} [9]}) and ([11]} [11]}, [13]} [13]}). Current version of LKH is available at http://akira.ruc.dk/%7Ekeld/research/LKH/. LKH and its implementations provide best-known solutions on many benchmark instances.
