An n log n heuristic for the TSP

An n log n randomized method based on POPMUSIC metaheuristic is proposed for generating reasonably good solutions to the travelling salesman problem. The method improves a previous work which algorithmic complexity was in n1:6. The method has been tested on instances with billions of cities. Few dozens of runs are able to generate a very high proportion of the edges of the best solutions known. This characteristic is exploited in a new release of the Helsgaun’s implementation of Lin-Kernighan heuristic (LKH) that is also able to produce rapidly extremely good solutions for non Euclidean instances