A Speed-up for Helsgaun's TSP Heuristic by Relaxing the Positive Gain Criterion

The Traveling Salesman Problem (TSP) is one of the most extensively researched and widely applied combinatorial optimization problems. It is NP-hard even in the symmetric and metric case. Building upon elaborate research, state-of-the-art exact solvers such as CONCORDE can solve TSP instances with several ten thousand vertices. A key ingredient for these integer programming approaches are fast heuristics to find a good initial solution, in particular the Lin-Kernighan-Helsgaun (LKH) heuristic. For instances with few hundred vertices heuristics like LKH often find an optimal solution. In this work we develop variations of LKH that perform significantly better on large instances. LKH repeatedly improves an initially random tour by exchanging edges along alternating circles. Thereby, it respects several criteria designed to quickly find alternating circles that give a feasible improvement of the tour. Among those criteria, the positive gain criterion stayed mostly untouched in previous research. It requires that, while constructing an alternating circle, the total gain has to be positive after each pair of edges. We relax this criterion carefully leading to improvement steps hitherto undiscovered by LKH. We confirm this improvement experimentally via extensive simulations on various benchmark libraries for TSP. Our computational study shows that for large instances our method is on average 13% faster than the latest version of LKH.