New TSP construction heuristics and their relationships to the 2-opt | SpringerLink
Skip to main content
Springer Nature Link
Log in

New TSP construction heuristics and their relationships to the 2-opt

  • Session 5A: Invited Lecture
  • Conference paper
  • First Online:
Algorithms and Data Structures (WADS 1997)

Part of the book series: Lecture Notes in Computer Science ((LNCS,volume 1272))

Included in the following conference series:

  • 158 Accesses

Abstract

Construction heuristics for the traveling salesman problem (TSP), with the 2-Opt applied as a postprocess, are studied with respect to their tour lengths and computation times. In this study, the “2-Opt dependency,” which indicates how the performance of the 2-Opt depends on the initial tours built by the construction heuristics, is analyzed. In accordance with the analysis, we devise a new construction heuristic, the recursive selection with long edge preference (RSL) method, which runs faster and produces shorter tours than the multiple-fragment method.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. E. L. Lawler, J. K. Lenstra, A. H. G. Rinnooy Kan, and D. B. Shimoys, The Traveling Salesman Problem, John Wiley & Sons, New York, 1985.

    Google Scholar 

  2. J. L. Bentley, Fast Algorithms for Geometric Traveling Salesman Problems, ORSA Journal on Computing, Vol. 4, No. 4, pp. 387–411, 1992.

    Google Scholar 

  3. S. Misono and K. Iwano, Experiments on TSP Real Instances, IBM Research Report, RT0153, 1996.

    Google Scholar 

  4. H. Okano, S. Misono and K. Iwano, New TSP Construction Heuristics and Their Relationships to the 2-Opt IBM Research Report, RT0154, 1996.

    Google Scholar 

  5. G. Reinelt, The Traveling Salesman, Computational Solutions for TSP Applications, Springer-Verlag, Heidelberg, 1994.

    Google Scholar 

  6. G. Reinelt, TSPLIB 1.1, Version of December 10, 1990, Institut fuer Mathematik, Universitaet Augsburg, 1990.

    Google Scholar 

  7. J. Perttunen, On the Significance of the Initial Solution in Traveling Salesman Heuristics, Journal of the Operational Research Society, Vol. 45, No. 10, pp. 1131–1140, 1994.

    Google Scholar 

  8. S. Lin and B.W. Kernighan, An Effective Heuristic Algorithm for the Traveling-Salesman Problem, Operations Research, Vol. 21, pp. 498–516, 1973.

    Google Scholar 

  9. J.G. van der Corput, Verteilungstunktionen I, II, Nederal. Akad. Wetensh. Proc. Ser. B, 38, pp. 813–821, 1058–1066, 1935.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. IBM Research, Tokyo Research Laboratory, 1623-14 Shimotsuruma, 242, Yamato, Kanagawa-ken, Japan

    Hiroyuki Okano, Shinji Misono & Kazuo Iwano

Authors
  1. Hiroyuki Okano
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Shinji Misono
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Kazuo Iwano
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Frank Dehne Andrew Rau-Chaplin Jörg-Rüdiger Sack Roberto Tamassia

Rights and permissions

Reprints and permissions

Copyright information

© 1997 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Okano, H., Misono, S., Iwano, K. (1997). New TSP construction heuristics and their relationships to the 2-opt. In: Dehne, F., Rau-Chaplin, A., Sack, JR., Tamassia, R. (eds) Algorithms and Data Structures. WADS 1997. Lecture Notes in Computer Science, vol 1272. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-63307-3_55

Download citation

  • DOI: https://doi.org/10.1007/3-540-63307-3_55

  • Published:

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-63307-5

  • Online ISBN: 978-3-540-69422-9

  • eBook Packages: Springer Book Archive

Publish with us

Policies and ethics