New best tours for TSP-benchmarks

26.08.2009: We have found new best tours, i.e., we have set new world records, for the benchmark instances

• instance (number of cities / tour length / date)
• XIB32892 (32.892 / 96.757 / 26.08.2009)
• FHT47608 (47.608 / 125.107 / 12.12.2008)
• *IRD29514 (29.514 / 80355 / 10.11.2008)
• *SRA104815 (104.815 / 251.346 / 28.10.2008)
• *ARA238035 (238.025 / 578.783 / 20.10.2008)
• *LRB744710 (744710 / 1611386 / 29.09.2008)
• FNA52057 (52057 / 147.789 / 15.08.2008)
• *BNA56769 (56.769 / 158.084 / 14.07.2008)
• *ICS39603 (39.603 / 106.820 / 14.07.2008)
• FYG28534 (28.534 / 78.562 / 14.07.2008)
• BBY34656 (34.656 / 99.159 / 30.06.2008)
• BOA28924 (28.924 / 79.622 / 30.06.2008)
• IDO21215 (21.215 / 63.517 / 23.06.2008)
• PBA38478 (38.478 / 108.318 / 27.05.2008)
• #PJH17845 (17.845 / 48.092 / 05.05.2008)
• FNC19402 (19.402 / 59.287 / 01.04.2008)
• XVB13584 (13.584 / 37.083 / 28.03.2008)
• *FRH19289 (19.289 / 55.799 / 22.10.2006)
• XSC6880 (6.880 / 21.535 / 24.05.2006)

Most of the tours have been found by an approach based on Keld Helgaun`s implementation of the Lin-Kernighan heuristics (LKH) which has been extended by a backbone contraction method and a more efficient partitioning algorithm. The others have been found using a variant of LKH, especially by using other candidate sets. The project is granted by Deutsche Forschungsgemeinscahft (DFG).

(Legend: *: old world record; #: world record tied with an other group)

[ more ... ]