Instance Created:  April 26, 2002
Number of Cities:  47608
Status:  OPEN
Best Tour:  125,104
Best Lower Bound:  xxx

History

Date	Gap	Lower Bound	Tour
2.2.03			125137 - Found by Keld Helsgaun, using a variant of LKH.
16.3.03			125133 - Found by Hung Dinh Nguyen using a hybrid genetic algorithm, starting with the above tour.
5.3.03			125132 - Found by Keld Helsgaun, using a variant of LKH.
15.5.07			125124 - Found by Keld Helsgaun, using a variant of LKH.
26.3.08			125120 - Found by Changxing Dong, Gerold Jaeger, Paul Molitor, Dirk Richter by a variant of LKH based an backbone contraction. The running time was 828900 seconds on a AMD Opteron Processor (2.6 GHz).
4.4.08			125119 - Found by Changxing Dong, Gerold Jaeger, Paul Molitor, Dirk Richter by a variant of LKH based an backbone contraction. The running time was 735420 seconds on a AMD Opteron Processor 2220.
7.4.08			125110 - Found by Keld Helsgaun, using a variant of LKH 2.
25.7.08			125109 - Found by Keld Helsgaun, using a variant of LKH 2.
12.12.08			125107 - Found by Changxing Dong, Gerold Jaeger, Paul Molitor, Dirk Richter by a variant of LKH based an backbone contraction.
19.12.08			125106 - Found by Keld Helsgaun, using a variant of LKH 2.
9.2.11			125104 - 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.