Chained Lin–Kernighan for large traveling salesman problems

We discuss several issues that arise in the implementation of Martin, Otto, and Felten's Chained Lin–Kernighan heuristic for large-scale traveling salesman problems. Computational results are presented for TSPLIB instances ranging in size from 11,489 cities up to 85,900 cities; for each of these instances, solutions within 1% of the optimal value can routinely be found in under one CPU minute on a 300 MHz Pentium II workstation, and solutions within 0.5% of optimal can routinely be found in under ten CPU minutes. We also demonstrate the scalability of the heuristic, presenting results for randomly generated Euclidean instances having up to 25,000,000 cities. For the largest of these random instances, a tour within 1% of an estimate of the optimal value was obtained in under one CPU day on a 64-bit IBM RS6000 workstation.