IDEAS home Printed from https://ideas.repec.org/a/inm/oropre/v28y1980i3-part-iip694-711.html
   My bibliography  Save this article

Approximate Traveling Salesman Algorithms

Author

Listed:
  • B. Golden

    (University of Maryland, College Park, Maryland)

  • L. Bodin

    (University of Maryland, College Park, Maryland)

  • T. Doyle

    (University of Maryland, College Park, Maryland)

  • W. Stewart

    (University of Maryland, College Park, Maryland)

Abstract

There have been a multitude of heuristic algorithms proposed for the solution of large scale traveling salesman problems. Our intent in this paper is to examine some of these well known heuristics, to introduce some new heuristics, and to compare these approximate techniques on the basis of efficiency and accuracy. We emphasize the strengths and weaknesses of each algorithm tested. One of our major conclusions is that it is not difficult to get within 2–3% of optimality using a composite heuristic which requires on the order of n 3 computations where n is the number of nodes in the network.

Suggested Citation

  • B. Golden & L. Bodin & T. Doyle & W. Stewart, 1980. "Approximate Traveling Salesman Algorithms," Operations Research, INFORMS, vol. 28(3-part-ii), pages 694-711, June.
    • Handle: RePEc:inm:oropre:v:28:y:1980:i:3-part-ii:p:694-711
    DOI: 10.1287/opre.28.3.694
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/opre.28.3.694
    Download Restriction: no
    File URL: https://libkey.io/10.1287/opre.28.3.694?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Chatterjee, Sangit & Carrera, Cecilia & Lynch, Lucy A., 1996. "Genetic algorithms and traveling salesman problems," European Journal of Operational Research, Elsevier, vol. 93(3), pages 490-510, September.
    2. Carreras, Miquel & Serra, Daniel, 1999. "On optimal location with threshold requirements," Socio-Economic Planning Sciences, Elsevier, vol. 33(2), pages 91-103, June.
    3. Jian Lin & Xiangfei Zeng & Jianxun Liu & Keqin Li, 2022. "Angular bisector insertion algorithm for solving small-scale symmetric and asymmetric traveling salesman problem," Journal of Combinatorial Optimization, Springer, vol. 43(1), pages 235-252, January.
    4. Ahmed Stohy & Heba-Tullah Abdelhakam & Sayed Ali & Mohammed Elhenawy & Abdallah A Hassan & Mahmoud Masoud & Sebastien Glaser & Andry Rakotonirainy, 2021. "Hybrid pointer networks for traveling salesman problems optimization," PLOS ONE, Public Library of Science, vol. 16(12), pages 1-17, December.
    5. Daniels, Richard L. & Rummel, Jeffrey L. & Schantz, Robert, 1998. "A model for warehouse order picking," European Journal of Operational Research, Elsevier, vol. 105(1), pages 1-17, February.
    6. Brunner, Carlos & Giesen, Ricardo & Klapp, Mathias A. & Flórez-Calderón, Luz, 2021. "Vehicle routing problem with steep roads," Transportation Research Part A: Policy and Practice, Elsevier, vol. 151(C), pages 1-17.
    7. Wang, Yu & Chen, Feng & Chen, Zhi-Long, 2018. "Pickup and delivery of automobiles from warehouses to dealers," Transportation Research Part B: Methodological, Elsevier, vol. 117(PA), pages 412-430.
    8. Tsubakitani, Shigeru & Evans, James R., 1998. "An empirical study of a new metaheuristic for the traveling salesman problem," European Journal of Operational Research, Elsevier, vol. 104(1), pages 113-128, January.
    9. E A Silver, 2004. "An overview of heuristic solution methods," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 55(9), pages 936-956, September.
    10. Joao CARDOSO NETO & Cleibson Aparecido de ALMEIDA & Giovani ROVEROTO & José Danilo Haick TAVARES, 2012. "Applications of Operational Research Techniques in Optimization to Visit Tourist Points of Vina del Mar," Informatica Economica, Academy of Economic Studies - Bucharest, Romania, vol. 16(2), pages 5-13.

    More about this item

    Statistics

    Access and download statistics

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:inm:oropre:v:28:y:1980:i:3-part-ii:p:694-711. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    We have no bibliographic references for this item. You can help adding them by using this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.