IDEAS home Printed from https://ideas.repec.org/a/spr/annopr/v351y2025i3d10.1007_s10479-025-06641-5.html
   My bibliography  Save this article

A survey on approximability of traveling salesman problems using the TSP-T3CO definition scheme

Author

Listed:
  • Sophia Saller

    (Deutsches Forschungszentrum für Künstliche Intelligenz)

  • Jana Koehler

    (Lucerne University of Applied Sciences and Arts)

  • Andreas Karrenbauer

    (Max Planck Institute for Informatics)

Abstract

The traveling salesman (or salesperson) problem, short TSP, is of strong interest to many researchers from mathematics, economics, and computer science. Manifold TSP variants occur in nearly every scientific field and application domain: e.g., engineering, physics, biology, life sciences, and manufacturing. Several thousand papers are published every year. This paper provides the first systematic survey on the best currently known approximability and inapproximability results for well-known TSP variants such as the “standard”, Path, Bottleneck, Maximum Scatter, Generalized, Clustered, Quota, Prize-Collecting, Time-dependent TSP, Traveling Purchaser Problem, Profitable Tour Problem, Orienteering Problem, TSP with Time Windows, and Orienteering Problem with Time Windows. The foundation of our survey is the definition scheme TSP-T3CO , which we propose as a uniform, easy-to-use and extensible means for the formal and precise definition of TSP variants. Applying TSP-T3CO to define a TSP variant reveals subtle differences within the same named variant and also brings out the differences between variants more clearly. We achieve the first comprehensive, concise, and compact representation of approximability results by using TSP-T3CO definitions. This makes it easier to understand the approximability landscape and the assumptions under which certain results hold. Open gaps become more evident and results can be compared more easily. Graphical abstract

Suggested Citation

  • Sophia Saller & Jana Koehler & Andreas Karrenbauer, 2025. "A survey on approximability of traveling salesman problems using the TSP-T3CO definition scheme," Annals of Operations Research, Springer, vol. 351(3), pages 2129-2190, August.
    • Handle: RePEc:spr:annopr:v:351:y:2025:i:3:d:10.1007_s10479-025-06641-5
    DOI: 10.1007/s10479-025-06641-5
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10479-025-06641-5
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1007/s10479-025-06641-5?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
    ---><---

    As the access to this document is restricted, you may want to

    for a different version of it.

    References listed on IDEAS

    as
    1. Manerba, Daniele & Mansini, Renata & Riera-Ledesma, Jorge, 2017. "The Traveling Purchaser Problem and its variants," European Journal of Operational Research, Elsevier, vol. 259(1), pages 1-18.
    2. Gouveia, Luis & Vo[ss], Stefan, 1995. "A classification of formulations for the (time-dependent) traveling salesman problem," European Journal of Operational Research, Elsevier, vol. 83(1), pages 69-82, May.
    3. Lahyani, Rahma & Khemakhem, Mahdi & Semet, Frédéric, 2015. "Rich vehicle routing problems: From a taxonomy to a definition," European Journal of Operational Research, Elsevier, vol. 241(1), pages 1-14.
    4. Martin Desrochers & Jacques Desrosiers & Marius Solomon, 1992. "A New Optimization Algorithm for the Vehicle Routing Problem with Time Windows," Operations Research, INFORMS, vol. 40(2), pages 342-354, April.
    5. Current, John & Marsh, Michael, 1993. "Multiobjective transportation network design and routing problems: Taxonomy and annotation," European Journal of Operational Research, Elsevier, vol. 65(1), pages 4-19, February.
    6. Michel Gendreau & Alain Hertz & Gilbert Laporte & Mihnea Stan, 1998. "A Generalized Insertion Heuristic for the Traveling Salesman Problem with Time Windows," Operations Research, INFORMS, vol. 46(3), pages 330-335, June.
    7. Ruiz, Ruben & Maroto, Concepcion, 2005. "A comprehensive review and evaluation of permutation flowshop heuristics," European Journal of Operational Research, Elsevier, vol. 165(2), pages 479-494, September.
    8. Mahendra S. Bakshi & Sant Ram Arora, 1969. "The Sequencing Problem," Management Science, INFORMS, vol. 16(4), pages 247-263, December.
    9. M. R. Rao, 1980. "Technical Note—A Note on the Multiple Traveling Salesmen Problem," Operations Research, INFORMS, vol. 28(3-part-i), pages 628-632, June.
    10. Yoshiyuki Karuno & Hiroshi Nagamochi & Toshihide Ibaraki, 1997. "Vehicle scheduling on a tree with release and handling times," Annals of Operations Research, Springer, vol. 69(0), pages 193-207, January.
    11. Gerhard Reinelt, 1991. "TSPLIB—A Traveling Salesman Problem Library," INFORMS Journal on Computing, INFORMS, vol. 3(4), pages 376-384, November.
    12. Mina, Hokey & Jayaraman, Vaidyanathan & Srivastava, Rajesh, 1998. "Combined location-routing problems: A synthesis and future research directions," European Journal of Operational Research, Elsevier, vol. 108(1), pages 1-15, July.
    13. G Laporte & U Palekar, 2002. "Some applications of the clustered travelling salesman problem," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 53(9), pages 972-976, September.
    14. Jean-Claude Picard & Maurice Queyranne, 1978. "The Time-Dependent Traveling Salesman Problem and Its Application to the Tardiness Problem in One-Machine Scheduling," Operations Research, INFORMS, vol. 26(1), pages 86-110, February.
    15. Harilaos N. Psaraftis & Marius M. Solomon & Thomas L. Magnanti & Tai-Up Kim, 1990. "Routing and Scheduling on a Shoreline with Release Times," Management Science, INFORMS, vol. 36(2), pages 212-223, February.
    16. Marius M. Solomon, 1987. "Algorithms for the Vehicle Routing and Scheduling Problems with Time Window Constraints," Operations Research, INFORMS, vol. 35(2), pages 254-265, April.
    17. Michael Rothkopf, 1966. "Letter to the Editor—The Traveling Salesman Problem: On the Reduction of Certain Large Problems to Smaller Ones," Operations Research, INFORMS, vol. 14(3), pages 532-533, June.
    18. Malandraki, Chryssi & Dial, Robert B., 1996. "A restricted dynamic programming heuristic algorithm for the time dependent traveling salesman problem," European Journal of Operational Research, Elsevier, vol. 90(1), pages 45-55, April.
    19. G. Dantzig & R. Fulkerson & S. Johnson, 1954. "Solution of a Large-Scale Traveling-Salesman Problem," Operations Research, INFORMS, vol. 2(4), pages 393-410, November.
    20. Vansteenwegen, Pieter & Souffriau, Wouter & Oudheusden, Dirk Van, 2011. "The orienteering problem: A survey," European Journal of Operational Research, Elsevier, vol. 209(1), pages 1-10, February.
    21. Leifer, Adrienne C. & Rosenwein, Moshe B., 1994. "Strong linear programming relaxations for the orienteering problem," European Journal of Operational Research, Elsevier, vol. 73(3), pages 517-523, March.
    22. Snyder, Lawrence V. & Daskin, Mark S., 2006. "A random-key genetic algorithm for the generalized traveling salesman problem," European Journal of Operational Research, Elsevier, vol. 174(1), pages 38-53, October.
    23. Pillac, Victor & Gendreau, Michel & Guéret, Christelle & Medaglia, Andrés L., 2013. "A review of dynamic vehicle routing problems," European Journal of Operational Research, Elsevier, vol. 225(1), pages 1-11.
    24. G. B. Dantzig & J. H. Ramser, 1959. "The Truck Dispatching Problem," Management Science, INFORMS, vol. 6(1), pages 80-91, October.
    25. Viet Hung Nguyen & Thi Thu Thuy Nguyen, 2012. "Approximating the asymmetric profitable tour," International Journal of Mathematics in Operational Research, Inderscience Enterprises Ltd, vol. 4(3), pages 294-301.
    26. Desrochers, M. & Lenstra, J. K. & Savelsbergh, M. W. P., 1990. "A classification scheme for vehicle routing and scheduling problems," European Journal of Operational Research, Elsevier, vol. 46(3), pages 322-332, June.
    27. Baniasadi, Pouya & Foumani, Mehdi & Smith-Miles, Kate & Ejov, Vladimir, 2020. "A transformation technique for the clustered generalized traveling salesman problem with applications to logistics," European Journal of Operational Research, Elsevier, vol. 285(2), pages 444-457.
    28. M. Haimovich & A. H. G. Rinnooy Kan, 1985. "Bounds and Heuristics for Capacitated Routing Problems," Mathematics of Operations Research, INFORMS, vol. 10(4), pages 527-542, November.
    29. Laporte, Gilbert, 1992. "The traveling salesman problem: An overview of exact and approximate algorithms," European Journal of Operational Research, Elsevier, vol. 59(2), pages 231-247, June.
    30. Current, John & Min, HoKey, 1986. "Multiobjective design of transportation networks: Taxonomy and annotation," European Journal of Operational Research, Elsevier, vol. 26(2), pages 187-201, August.
    31. Gilbert Laporte & Jorge Riera-Ledesma & Juan-José Salazar-González, 2003. "A Branch-and-Cut Algorithm for the Undirected Traveling Purchaser Problem," Operations Research, INFORMS, vol. 51(6), pages 940-951, December.
    32. Bruce L. Golden & Larry Levy & Rakesh Vohra, 1987. "The orienteering problem," Naval Research Logistics (NRL), John Wiley & Sons, vol. 34(3), pages 307-318, June.
    33. Warren Powell & Joel Shapiro & Hugo Simao, 2001. "A Representational Paradigm for Dynamic Resource Transformation Problems," Annals of Operations Research, Springer, vol. 104(1), pages 231-279, April.
    34. Dominique Feillet & Pierre Dejax & Michel Gendreau, 2005. "Traveling Salesman Problems with Profits," Transportation Science, INFORMS, vol. 39(2), pages 188-205, May.
    35. Matteo Fischetti & Juan José Salazar González & Paolo Toth, 1997. "A Branch-and-Cut Algorithm for the Symmetric Generalized Traveling Salesman Problem," Operations Research, INFORMS, vol. 45(3), pages 378-394, June.
    36. Alice Paul & Daniel Freund & Aaron Ferber & David B. Shmoys & David P. Williamson, 2020. "Budgeted Prize-Collecting Traveling Salesman and Minimum Spanning Tree Problems," Mathematics of Operations Research, INFORMS, vol. 45(2), pages 576-590, May.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Dursunoglu, Cagla F. & Arslan, Okan & Demir, Sebnem Manolya & Kara, Bahar Y. & Laporte, Gilbert, 2025. "A unifying framework for selective routing problems," European Journal of Operational Research, Elsevier, vol. 320(1), pages 1-19.
    2. Miranda, Pablo A. & Blazquez, Carola A. & Obreque, Carlos & Maturana-Ross, Javier & Gutierrez-Jarpa, Gabriel, 2018. "The bi-objective insular traveling salesman problem with maritime and ground transportation costs," European Journal of Operational Research, Elsevier, vol. 271(3), pages 1014-1036.
    3. Pop, Petrică C. & Cosma, Ovidiu & Sabo, Cosmin & Sitar, Corina Pop, 2024. "A comprehensive survey on the generalized traveling salesman problem," European Journal of Operational Research, Elsevier, vol. 314(3), pages 819-835.
    4. Bruce Golden & Zahra Naji-Azimi & S. Raghavan & Majid Salari & Paolo Toth, 2012. "The Generalized Covering Salesman Problem," INFORMS Journal on Computing, INFORMS, vol. 24(4), pages 534-553, November.
    5. Lahyani, Rahma & Khemakhem, Mahdi & Semet, Frédéric, 2015. "Rich vehicle routing problems: From a taxonomy to a definition," European Journal of Operational Research, Elsevier, vol. 241(1), pages 1-14.
    6. Afsaneh Amiri & Majid Salari, 2019. "Time-constrained maximal covering routing problem," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 41(2), pages 415-468, June.
    7. Cacchiani, Valentina & Contreras-Bolton, Carlos & Toth, Paolo, 2020. "Models and algorithms for the Traveling Salesman Problem with Time-dependent Service times," European Journal of Operational Research, Elsevier, vol. 283(3), pages 825-843.
    8. Shahin Gelareh & Bernard Gendron & Saïd Hanafi & Rahimeh Neamatian Monemi & Raca Todosijević, 2020. "The selective traveling salesman problem with draft limits," Journal of Heuristics, Springer, vol. 26(3), pages 339-352, June.
    9. Bian, Zheyong & Liu, Xiang, 2018. "A real-time adjustment strategy for the operational level stochastic orienteering problem: A simulation-aided optimization approach," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 115(C), pages 246-266.
    10. Ido Orenstein & Tal Raviv & Elad Sadan, 2019. "Flexible parcel delivery to automated parcel lockers: models, solution methods and analysis," EURO Journal on Transportation and Logistics, Springer;EURO - The Association of European Operational Research Societies, vol. 8(5), pages 683-711, December.
    11. Bernardino, Raquel & Paias, Ana, 2018. "Solving the family traveling salesman problem," European Journal of Operational Research, Elsevier, vol. 267(2), pages 453-466.
    12. Zang, Xiaoning & Jiang, Li & Liang, Changyong & Fang, Xiang, 2023. "Coordinated home and locker deliveries: An exact approach for the urban delivery problem with conflicting time windows," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 177(C).
    13. Furini, Fabio & Persiani, Carlo Alfredo & Toth, Paolo, 2016. "The Time Dependent Traveling Salesman Planning Problem in Controlled Airspace," Transportation Research Part B: Methodological, Elsevier, vol. 90(C), pages 38-55.
    14. Kobeaga, Gorka & Rojas-Delgado, Jairo & Merino, María & Lozano, Jose A., 2024. "A revisited branch-and-cut algorithm for large-scale orienteering problems," European Journal of Operational Research, Elsevier, vol. 313(1), pages 44-68.
    15. Racha El-Hajj & Rym Nesrine Guibadj & Aziz Moukrim & Mehdi Serairi, 2020. "A PSO based algorithm with an efficient optimal split procedure for the multiperiod vehicle routing problem with profit," Annals of Operations Research, Springer, vol. 291(1), pages 281-316, August.
    16. F. Angel-Bello & Y. Cardona-Valdés & A. Álvarez, 2019. "Mixed integer formulations for the multiple minimum latency problem," Operational Research, Springer, vol. 19(2), pages 369-398, June.
    17. Jean-François Cordeau & Gianpaolo Ghiani & Emanuela Guerriero, 2014. "Analysis and Branch-and-Cut Algorithm for the Time-Dependent Travelling Salesman Problem," Transportation Science, INFORMS, vol. 48(1), pages 46-58, February.
    18. Claudio Gambella & Joe Naoum-Sawaya & Bissan Ghaddar, 2018. "The Vehicle Routing Problem with Floating Targets: Formulation and Solution Approaches," INFORMS Journal on Computing, INFORMS, vol. 30(3), pages 554-569, August.
    19. Balcik, Burcu, 2017. "Site selection and vehicle routing for post-disaster rapid needs assessment," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 101(C), pages 30-58.
    20. A. S. Santos & A. M. Madureira & M. L. R. Varela, 2018. "The Influence of Problem Specific Neighborhood Structures in Metaheuristics Performance," Journal of Mathematics, Hindawi, vol. 2018, pages 1-14, July.

    More about this item

    Keywords

    ;
    ;
    ;
    ;

    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:spr:annopr:v:351:y:2025:i:3:d:10.1007_s10479-025-06641-5. 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.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with 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: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    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.