Chained Lin-Kernighan for Large Traveling Salesman Problems

References

• Applegate D., Bixby R., Chvátal V., Cook W. On the solution of traveling salesman problems. Documenta Mathematica Journal der Deutschen Mathematiker-Vereinigung, International Congress of Mathematicians (1998) 645–656Google Scholar
• Applegate D., Bixby R., Chvátal V., Cook W. Finding tours in the TSP. (1999) . Report Number 99885, Research Institute for Discrete Mathematics, Universität Bonn, Bonn, GermanyGoogle Scholar
• Applegate D., Bixby R., Chvátal V., Cook W., Jünger M., Naddef D. TSP cuts which do not conform to the template paradigm. Computational Combinatorial Optimization (2001) (Springer, Heidelberg, Germany) 261–304Crossref, Google Scholar
• Applegate D., Chvátal V., Cook W. Lower bounds for the travelling salesman problem. TSP '90 (1990) . Technical report CRPCTR90547, Center for Research in Parallel Computing, Rice University, Houston, TXGoogle Scholar
• Beardwood J., Halton J. H., Hammersley J. M. The shortest path through many points. Proceedings of the Cambridge Philosophical Society (1959) 55:299–327Crossref, Google Scholar
• Bentley J. L. Fast algorithms for geometric traveling salesman problems. ORSA Journal on Computing (1992) 4:387–411Link, Google Scholar
• Bland R. G., Shallcross D. F. Large traveling salesman problems arising from experiments in X-ray crystallography: A preliminary report on computation. Operations Research Letters (1989) 8:125–128Crossref, Google Scholar
• Borůvka O. On a certain minimal problem (in Czech). Práce Moravské Přírodovědecké Společcnosti (1926) 3:37–58Google Scholar
• Cerf N. J., Boutet de Monvel J., Bohigas O., Martin O. C., Percus A. G. The random link approximation for the Euclidean traveling salesman problem. Journal de Physique I (1997) 7:117–136Crossref, Google Scholar
• Christofides N. Worst-case analysis of a new heuristic for the travelling salesman problem. (1976) . Report 388, Graduate School of Industrial Administration, Carnegie Mellon University, Pittsburgh, PAGoogle Scholar
• Chrobak M., Szymacha T., Krawczyk A. A data structure useful for finding Hamiltonian cycles. Theoretical Computer Science (1990) 71:419–424Crossref, Google Scholar
• Codenotti B., Manzini G., Margara L., Resta G. Perturbation: an efficient technique for the solution of very large instances of the Euclidean TSP. INFORMS Journal on Computing (1996) 8:125–133Link, Google Scholar
• Cook W., Seymour P. D. An algorithm for the ring-routing problem. (1993) . Technical Memorandum, Bellcore, Morristown, NJGoogle Scholar
• Fortune S. J. A sweepline algorithm for Voronoi diagrams. Algorithmica (1987) 2:153–174Crossref, Google Scholar
• Fortune S. J. weep2. Computer code (in the C programming language). (1994) . www.netlib.org/voronoi/sweep2Google Scholar
• Fredman M. L., Johnson D. S., McGeoch L. A., Ostheimer G. Data structures for traveling salesmen. Journal of Algorithms (1995) 18:432–479Crossref, Google Scholar
• Held M., Karp R. M. The traveling-salesman problem and minimum spanning trees: part II. Mathematical Programming (1971) 1:6–25Crossref, Google Scholar
• Helsgaun K. An effective implementation of the Lin-Kernighan traveling salesman heuristic. European Journal of Operational Research (2000) 126:106–130The LKH code is available at http://www.dat.ruc.dk/~keld/research/LKH/Crossref, Google Scholar
• Hong I., Kahng A. B., Moon B. Improved large-step markov chain variants for the symmetric TSP. Journal of Heuristics (1997) 3:63–81Crossref, Google Scholar
• Johnson D. S. Local optimization and the traveling salesman problem. Proceedings 17th Colloquium of Automata, Languages, and Programming, Lecture Notes in Computer Science (1990) (Springer-Verlag, Berlin, Germany) 446–461No. 443Crossref, Google Scholar
• Johnson D. S., McGeoch L. A., Aarts E. H. L., Lenstra J. K. The traveling salesman problem: a case study in local optimization. Local Search in Combinatorial Optimization (1997) (Wiley, New York) 215–310Google Scholar
• Johnson D. S., McGeoch L. A., Rothberg E. E. Asymptotic experimental analysis for the Held-Karp traveling salesman bound. Proceedings of the Seventh Annual ACM-SIAM Symposium on Discrete Algorithms (1996) (Association for Computing Machinery, New York) 341–350Google Scholar
• Johnson D. S., Papadimitriou C. H., Lawler E. L., Lenstra J. K., Rinnooy Kan A. H. G., Shmoys D. B. Performance guarantees for heuristics. The Traveling Salesman Problem (1985) (Wiley, Chichester, U.K.) 145–180Google Scholar
• Jünger M., Reinelt G., Rinaldi G., Ball M., Magnanti T., Monma C. L., Nemhauser G. The traveling salesman problem. Handbook on Operations Research and Management Sciences: Networks (1995) (North-Holland, Amsterdam, The Netherlands) 225–330Google Scholar
• Karp R. M., Steele J. M., Lawler E. L., Lenstra J. K., Rinnooy Kan A. H. G., Shmoys D. B. Probabilistic analysis of heuristics. The Traveling Salesman Problem (1985) (Wiley, Chichester, U.K.) 181–205Google Scholar
• Lawler E. L., Lenstra J. K., Rinnooy Kan A. H. G., Shmoys D. B.The Traveling Salesman Problem (1985) (Wiley, Chichester, U.K) Google Scholar
• Lin S., Kernighan B. W. An effective heuristic algorithm for the traveling-salesman problem. Operations Research (1973) 21:498–516Link, Google Scholar
• Mak K.-T., Morton A. J. A modified Lin-Kernighan traveling salesman heuristic. Operations Research Letters (1993) 13:127–132Crossref, Google Scholar
• Martin O. C., Otto S. W. Combining simulated annealing with local search heuristics. Annals of Operations Research (1996) 63:57–75Crossref, Google Scholar
• Martin O., Otto S. W., Felten E. W. Large-step Markov chains for the traveling salesman problem. Complex Systems (1991) 5:299–326Google Scholar
• Martin O., Otto S. W., Felten E. W. Large-step Markov chains for the TSP incorporating local search heuristics. Operations Research Letters (1992) 11:219–224Crossref, Google Scholar
• Miller D. L., Pekny J. F. A staged primal-dual algorithm for perfect b-matching with edge capacities. ORSA Journal on Computing (1995) 7:298–320Link, Google Scholar
• Neto D.Efficient Cluster Compensation for Lin-Kernighan Heuristics (1999) (Ph.D. thesis, Department of Computer Science, University of Toronto, Toronto, Ontario, Canada) Google Scholar
• Percus A. G., Martin O. C. Finite size and dimensional dependence in the Euclidean traveling salesman problem. Physical Review Letters (1996) 76:1188–1191Crossref, Google Scholar
• Perttunen J. On the significance of the initial solution in travelling salesman heuristics. Journal of the Operational Research Society (1994) 45:1131–1140Crossref, Google Scholar
• Reinelt G. TSPLIB—A traveling salesman library. ORSA Journal on Computing (1991) 3:376–384Link, Google Scholar
• Reinelt G.The Traveling Salesman: Computational Solutions for TSP Applications (1994) (Springer-Verlag, Berlin, Germany) Google Scholar
• Reinelt G. TSPLIB 95. (1995) . Research Report, Institut für Angewandte Mathematik, Universität Heidelberg, Heidelberg, Germany. Updated results available at http://www.iwr.uni-heidelberg.de/groups/comopt/software/TSPLIB95/Google Scholar
• Rohe A.Parallele Heuristiken für sehr grosse Traveling Salesman Probleme (1997) (Diplomarbeit, Research Institute for Discrete Mathematics, Universität Bonn, Bonn, Germany) Google Scholar
• Schäfer M.Effiziente Algorithmen für sehr grosse Traveling Salesman Probleme (1994) (Diplomarbeit, Research Institute for Discrete Mathematics, Universität Bonn, Bonn, Germany) Google Scholar
• Verhoeven M. G. A., Aarts E. H. L., van de Sluis E., Vaessens R. J. M., Männer R., Manderick B. Parallel local search and the travelling salesman problem. Parallel Problem Solving from Nature 2 (1995) (North-Holland, Amsterdam, The Netherlands)543–552Google Scholar