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.
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.
Info lengkap:
http://www.math.uwaterloo.ca/tsp/data/usa/leaders.html
No comments:
Post a Comment