The method has been tested on instances with billions of cities. For a lot of problem instances of the literature, a 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 the Lin-Kernighan heuristic (LKH) that is also able to produce rapidly extremely good solutions for non-Euclidean instances. The practical limits of the proposed method are discussed on a new type of problem instances arising in a manufacturing process, especially in 3D extrusion printing.