Instance Created:  July 29, 2001
Number of Cities:  14,473
Status:  OPEN
Best Tour:  177,092
Best Lower Bound:  176,940

History

Date	Gap	Lower Bound	Tour
9.02.01			177,405 - Single run of LKH (n trials, 1,373,210 seconds on a 500 MHz EV6 Alpha).
9.04.01	0.263%	176,940 - Established by Concorde with -C 20 (used 3 nodes in the branch-and-cut tree, 603,360 seconds on a 500 MHz EV6 Alpha).
9.20.01	0.110%		177,134 - Found by Keld Helsgaun using variants of his LKH code. The running time was approximately 2 days on a 400 MHz PowerMac G4.
10.19.01	0.110%		177,132 - Found by morphing and merging the 177,134 tour together with 4 tours found by LKH. The total running time for the 4 LKH runs was 4,157,763 seconds on a 500 MHz EV6 Alpha); the tmorph time was 6.93 sconds and the tmerge time was 22.38 sconds.
16.3.03	0.093%		177,105 - Found by Hung Dinh Nguyen using a hybrid genetic algorithm, starting with the above 177,132 tour. The running time was 37216 seconds on a single processor of a Sun Ultra 80 (450 MHz).
27.3.06	0.086%		177,092 - Found by Yuichi Nagata.

Notes

1. Concorde is our linear-programming based TSP solver.

2. linkern is an implementation of Martin, Otto, and Felten's Chained Lin-Kernighan heuristic. It is included in the Concorde code.

3. LKH is Keld Helsgaun's powerful implementation of the Lin-Kernighan heuristic.

Back to TSP home.