Analysis of the run-time distribution and solution performance distribution of iterated local search for the TSP

The Traveling Salesman Problem (TSP) is one of the most classical problems in combinatorial optimization. Many heuristics, as well as efficient meta-heuristics that followed, have been developed for the TSP. In this paper authors investigate the empirical run-time distributions (RTDs) of Iterated Lin-Kernighan algorithm, one of the state-of-the-art meta-heuristics algorithms for TSP, on a series of scalable TSP instances in TSPLIB. It has been shown that the resulted run-time distributions can be well approximated by Weibull distributions. Moreover, authors propose, for the first time, the solution performance distributions (SPDs) of iterated LK algorithm. By analyzing the characteristics of SPDs, authors obtain some practical conclusions that may give guidance to application design for the TSP