A survey on approximability of traveling salesman problems using the TSP-T3CO definition scheme
Annals of Operations Research · 2025-08 · 351 (3) · 2129-2190
DOI: 10.1007/s10479-025-06641-5 ↗Kurz gefasst
Fachartikel in der Zeitschrift Annals of Operations Research, online erschienen am 01.07.2025. Verfasst von Sophia Saller und 2 weiteren Autor:innen. Die Arbeit wurde bisher 5-mal zitiert (Crossref) und nennt 215 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: Max Planck Institute for Informatics.
Abstract (Originalsprache)
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
Förderung
- Max Planck Institute for Informatics
Zitieren
APA
Saller, S., Koehler, J., & Karrenbauer, A. (2025). A survey on approximability of traveling salesman problems using the TSP-T3CO definition scheme. Annals of Operations Research, 351(3), 2129-2190. https://doi.org/10.1007/s10479-025-06641-5
Vancouver
Saller S, Koehler J, Karrenbauer A. A survey on approximability of traveling salesman problems using the TSP-T3CO definition scheme. Annals of Operations Research. 2025;351(3):2129-2190. doi:10.1007/s10479-025-06641-5
BibTeX
@article{Saller2025,
author = {Saller, Sophia and Koehler, Jana and Karrenbauer, Andreas},
title = {A survey on approximability of traveling salesman problems using the TSP-T3CO definition scheme},
journal = {Annals of Operations Research},
year = {2025},
volume = {351},
number = {3},
pages = {2129--2190},
doi = {10.1007/s10479-025-06641-5}
}
EUVIMED