The best reported tour for the World TSP was found by by Keld Helsgaun using a variant of his LKH heuristic algorithm. The tour of length 7,515,772,212 was found on May 24, 2013, improving Helsgaun's previous records of 7,515,778,188 (October 25, 2011), 7,515,786,987 (April 4, 2011), 7,515,796,609 (May 4, 2010), 7,515,877,991 (May 12, 2009), 7,515,947,511 (November 27, 2008), and 7,517,285,610 (September 16, 2003). An earlier record tour of length 7,518,425,642 was found by Hung Dinh Nguyen, Ikuo Yoshihara, Kunihito Yamamori, and Moritoshi Yasunaga (June 2, 2003), using a combination of iterated Lin-Kernighan and a parallel hybrid genetic algorithm.
The current best lower bound on the length of a tour for the World TSP is 7,512,218,268. This bound was established by the Concorde TSP code (June 5, 2007), using CPLEX as a linear-programming solver. The bound shows that Keld Helsgaun's tour has length at most 0.0474% greater than the length of an optimal tour.
We will be most happy to report any improved tour or improved lower bound that you may find.
Data  (Gzipped TSPLIB Format, world.tsp.gz, 11.5 mbytes)
Back to TSP home.