USA Challenge Results

The winner of the USA TSP Challenge is Xavier Clarist with a tour of length 6,204,999. Keld Helsgaun and Yuichi Nagata also submitted tours of this same length, but Xavier wins the tiebreak since I received his tour earlier than those of the two other tour-finding champions. It is remarkable that the three best tours all have the same length, since I did not reveal to the researchers the lengths of the previously received tours. Could this be the optimal tour for the USA instance? Much work remains to establish a strong lower bound to prove that 6,204,999 cannot be beat!

The three top tours have the same length, but take slightly different routes through the USA. The data sets for the tours, in TSPLIB TOUR format, are given in clarist.tour, helsgaun.tour, and nagata.tour. The tours of Clarist and Helsgaun have 114,672 edges in common, the tours of Clarist and Nagata have 114,637 edges in common, and the tours of Helsgaun and Nagata have 114,563 edges in common. The three tours together span a total of 116,751 edges.

Final Leader Board
Length Team Date
6204999 Xavier Clarist 27.8.2012
6204999 Keld Helsgaun 17.9.2012
6204999 Yuichi Nagata 1.2.2013
6205000 Vladimir Shylo 4.2.2013
6205001 Xavier Clarist 6.8.2012
6205005 Keld Helsgaun 1.8.2012
6205015 Ivan Gradinar 11.4.2013
6205017 Vladimir Shylo 25.1.2013
6205028 Xavier Clarist 30.7.2012
6205064 Keld Helsgaun 16.7.2012
6205118 Roman Bazylevych, Bohdan Kuz, Roman Kutelmakh 3.7.2013
6205251 Mohammad Syarwani 3.7.2013
6205313 Mohammad Syarwani 26.11.2012
6205320 Ashley Wang 4.11.2012
6210923 Mohammad Syarwani 8.10.2012
6211995 Geir Hasle, Torkel Haufmann, Christian Schulz 4.7.2013
6221125 Marco Alves Ganhoto 3.7.2013
6251141 Wenhong Tian 3.7.2013
6424026 David Liu 2.7.2013
6598272 Cyrille Yemeli Tasse 4.3.2013

An important note to these results is that Keld Helsgaun's publicly available LKH code was used as a subroutine in the work of Shylo, Gradinar, Wang, Bazylevych-Kuz-Kutelmakh, and Hasle-Haufmann-Schulz. LKH is a fantastic resource for TSP researchers.