Neue "Weltrekorde" bei TSP-Benchmark-Instanzen

26.08.2009: Im Rahmen des DFG-Projektes "Bessere Methoden zum Lösen des Handelsreisendenproblems" konnten neue beste Touren für die Benchmarkgraphen

• Instanzname (Städte / Tourlänge / Datum)
• XIB32892 (32.892 / 96.760 / 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)

gefunden werden. Die meisten dieser Touren konnten mit einem Ansatz, der die von Keld Helsgaun implementierte Lin-Kernighan Heuristik (LKH) um eine Backbone Kontraktion erweitert bzw. einen verbesserten Partitionierungsalgorithmus verwendet, gefunden werden, die übrigen durch eine geschickte Wahl der Parameter der LKH, inbesondere durch andere Kandidatenmengen.

(Legende: *: alter Weltrekord; #: Weltrekord eingestellt)

[ mehr ... ]