Analysing the Run-Time Behaviour of Iterated Local Search for the Travelling Salesman Problem

Iterated Local Search (ILS) is currently the most successful meta-heuristic for solving large Travelling Salesman Problems (TSPs). In this paper we study the behaviour of ILS algorithms by measuring and analysing run-time distributions. Our analysis shows that currently available ILS algorithms suffer from stagnation behaviour when searching for very high quality solutions. Based on this observation we propose two enhanced ILS algorithms for the TSP which avoid this stagnation behaviour and achieve significantly improved performance. More generally, our study demonstrates how the analysis of runtime distributions can provide the basis for characterising and improving the performance of state-of-the-art metaheuristics, such as Iterated Local Search.