{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,11]],"date-time":"2025-09-11T19:23:13Z","timestamp":1757618593179,"version":"3.44.0"},"reference-count":215,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2025,7,1]],"date-time":"2025-07-01T00:00:00Z","timestamp":1751328000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2025,7,1]],"date-time":"2025-07-01T00:00:00Z","timestamp":1751328000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"Max Planck Institute for Informatics"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Ann Oper Res"],"published-print":{"date-parts":[[2025,8]]},"abstract":"<jats:sec>\n            <jats:title>Abstract<\/jats:title>\n            <jats:p>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.,\u00a0engineering, 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 \u201cstandard\u201d, 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\u00a0, which we propose as a uniform, easy-to-use and extensible means for the formal and precise definition of TSP variants. Applying TSP-T3CO\u00a0to 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\u00a0definitions. 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.<\/jats:p>\n          <\/jats:sec>\n          <jats:sec>\n            <jats:title>Graphical abstract<\/jats:title>\n          <\/jats:sec>","DOI":"10.1007\/s10479-025-06641-5","type":"journal-article","created":{"date-parts":[[2025,7,1]],"date-time":"2025-07-01T07:37:34Z","timestamp":1751355454000},"page":"2129-2190","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["A survey on approximability of traveling salesman problems using the TSP-T3CO definition scheme"],"prefix":"10.1007","volume":"351","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-4817-8601","authenticated-orcid":false,"given":"Sophia","family":"Saller","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9000-9188","authenticated-orcid":false,"given":"Jana","family":"Koehler","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6129-3220","authenticated-orcid":false,"given":"Andreas","family":"Karrenbauer","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2025,7,1]]},"reference":[{"issue":"5","key":"6641_CR1","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/2818310","volume":"62","author":"H-C An","year":"2015","unstructured":"An, H.-C., Kleinberg, R., & Shmoys, D. B. (2015). Improving Christofides\u2019 algorithm for the s-t Path TSP. Journal of the ACM, 62(5), 1\u201328.","journal-title":"Journal of the ACM"},{"issue":"4","key":"6641_CR2","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3478537","volume":"17","author":"H-C An","year":"2021","unstructured":"An, H.-C., Kleinberg, R., & Shmoys, D. B. (2021). Approximation algorithms for the bottleneck asymmetric traveling salesman problem. ACM Transactions on Algorithms, 17(4), 1\u201312.","journal-title":"ACM Transactions on Algorithms"},{"issue":"1\u20132","key":"6641_CR3","doi-asserted-by":"publisher","first-page":"29","DOI":"10.1016\/S0167-6377(98)00046-7","volume":"24","author":"S Anily","year":"1999","unstructured":"Anily, S., Bramel, J., & Hertz, A. (1999). A 5\/3-approximation algorithm for the clustered traveling salesman tour and path problems. Operations Research Letters, 24(1\u20132), 29\u201335.","journal-title":"Operations Research Letters"},{"key":"6641_CR4","volume-title":"The Traveling Salesman Problem","author":"DL Applegate","year":"2011","unstructured":"Applegate, D. L., Bixby, R. E., Chv\u00e1tal, V., & Cook, W. J. (2011). The Traveling Salesman Problem. Princeton: Princeton University Press."},{"issue":"2","key":"6641_CR5","doi-asserted-by":"publisher","first-page":"309","DOI":"10.1137\/090771429","volume":"40","author":"A Archer","year":"2011","unstructured":"Archer, A., Bateni, M., Hajiaghayi, M., & Karloff, H. (2011). Improved approximation algorithms for prize-collecting Steiner tree and TSP. SIAM Journal on Computing, 40(2), 309\u2013332.","journal-title":"SIAM Journal on Computing"},{"key":"6641_CR6","doi-asserted-by":"crossref","unstructured":"Arkin, E.M., Mitchell, J.S., & Narasimhan, G. (1998). Resource-constrained geometric network optimization. In: Proc. 14th Annual Symposium on Computational Geometry, pp. 307\u2013316. ACM, New York.","DOI":"10.1145\/276884.276919"},{"issue":"2","key":"6641_CR7","doi-asserted-by":"publisher","first-page":"515","DOI":"10.1137\/S0097539797320281","volume":"29","author":"EM Arkin","year":"1999","unstructured":"Arkin, E. M., Chiang, Y.-J., Mitchell, J. S. B., Skiena, S. S., & Yang, T.-C. (1999). On the maximum scatter traveling salesperson problem. SIAM Journal of Computing, 29(2), 515\u2013544.","journal-title":"SIAM Journal of Computing"},{"key":"6641_CR8","doi-asserted-by":"crossref","unstructured":"Arora, S. (1996). Polynomial time approximation schemes for Euclidean TSP and other geometric problems. In: Proc. 37th Conference on Foundations of Computer Science, pp. 2\u201311. IEEE","DOI":"10.1109\/SFCS.1996.548458"},{"issue":"3","key":"6641_CR9","doi-asserted-by":"publisher","first-page":"475","DOI":"10.1007\/PL00011432","volume":"90","author":"N Ascheuer","year":"2001","unstructured":"Ascheuer, N., Fischetti, M., & Gr\u00f6tschel, M. (2001). Solving the asymmetric travelling salesman problem with time windows by branch-and-cut. Mathematical Programming, 90(3), 475\u2013506.","journal-title":"Mathematical Programming"},{"issue":"2\u20133","key":"6641_CR10","doi-asserted-by":"publisher","first-page":"147","DOI":"10.1016\/j.tcs.2004.05.013","volume":"324","author":"JE Augustine","year":"2004","unstructured":"Augustine, J. E., & Seiden, S. (2004). Linear time approximation schemes for vehicle scheduling problems. Theoretical Computer Science, 324(2\u20133), 147\u2013160.","journal-title":"Theoretical Computer Science"},{"key":"6641_CR11","first-page":"611","volume-title":"Handbook of Approximation Algorithms and Metaheuristics, Volume 1: Methologies and Traditional Applications","author":"G Ausiello","year":"2018","unstructured":"Ausiello, G., Bonifaci, V., Leonardi, S., & Marchetti-Spaccamela, A. (2018). Prize collecting traveling salesman and related problems. In T. F. Gonzalez (Ed.), Handbook of Approximation Algorithms and Metaheuristics, Volume 1: Methologies and Traditional Applications (pp. 611\u2013628). Boca Raton: Chapman and Hall\/CRC."},{"issue":"1","key":"6641_CR12","doi-asserted-by":"publisher","first-page":"254","DOI":"10.1137\/S009753979528826X","volume":"28","author":"B Awerbuch","year":"1998","unstructured":"Awerbuch, B., Azar, Y., Blum, A., & Vempala, S. (1998). New approximation guarantees for minimum-weight k-trees and prize-collecting salesmen. SIAM Journal on Computing, 28(1), 254\u2013262.","journal-title":"SIAM Journal on Computing"},{"key":"6641_CR13","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511711787","volume-title":"The Description Logic Handbook: Theory, Implementation, and Applications","author":"F Baader","year":"2007","unstructured":"Baader, F., McGuinness, D. L., Nardi, D., & Patel-Schneider, P. F. (2007). The Description Logic Handbook: Theory, Implementation, and Applications. Cambridge: Cambridge University Press."},{"key":"6641_CR14","doi-asserted-by":"publisher","DOI":"10.1017\/9781139025355","volume-title":"An Introduction to Description Logic","author":"F Baader","year":"2017","unstructured":"Baader, F., Horrocks, I., Lutz, C., & Sattler, U. (2017). An Introduction to Description Logic. Cambridge: Cambridge University Press."},{"issue":"4","key":"6641_CR15","doi-asserted-by":"publisher","first-page":"625","DOI":"10.1111\/j.1467-8640.1995.tb00052.x","volume":"11","author":"C B\u00e4ckstr\u00f6m","year":"1995","unstructured":"B\u00e4ckstr\u00f6m, C., & Nebel, B. (1995). Complexity results for SAS+ planning. Computational Intelligence, 11(4), 625\u2013655.","journal-title":"Computational Intelligence"},{"key":"6641_CR16","volume-title":"Principes of Sequencing and Scheduling","author":"KR Baker","year":"1974","unstructured":"Baker, K. R., & Trietsch, D. (1974). Principes of Sequencing and Scheduling. Hoboken: Wiley."},{"issue":"4","key":"6641_CR17","doi-asserted-by":"publisher","first-page":"247","DOI":"10.1287\/mnsc.16.4.B247","volume":"16","author":"MS Bakshi","year":"1969","unstructured":"Bakshi, M. S., & Arora, S. R. (1969). The sequencing problem. Management Science, 16(4), 247\u2013263.","journal-title":"Management Science"},{"issue":"6","key":"6641_CR18","doi-asserted-by":"publisher","first-page":"621","DOI":"10.1002\/net.3230190602","volume":"19","author":"E Balas","year":"1989","unstructured":"Balas, E. (1989). The prize collecting traveling salesman problem. Networks, 19(6), 621\u2013636.","journal-title":"Networks"},{"issue":"1","key":"6641_CR19","doi-asserted-by":"publisher","first-page":"241","DOI":"10.1007\/BF01585767","volume":"68","author":"E Balas","year":"1995","unstructured":"Balas, E., Fischetti, M., & Pulleyblank, W. R. (1995). The precedence-constrained asymmetric traveling salesman polytope. Mathematical Programming, 68(1), 241\u2013265.","journal-title":"Mathematical Programming"},{"issue":"2","key":"6641_CR20","doi-asserted-by":"publisher","first-page":"444","DOI":"10.1016\/j.ejor.2020.01.053","volume":"285","author":"P Baniasadi","year":"2020","unstructured":"Baniasadi, P., Foumani, M., Smith-Miles, K., & Ejov, V. (2020). A transformation technique for the clustered generalized traveling salesman problem with applications to logistics. European Journal of Operational Research, 285(2), 444\u2013457.","journal-title":"European Journal of Operational Research"},{"key":"6641_CR21","doi-asserted-by":"crossref","unstructured":"Bansal, N., Blum, A., Chawla, S., & Meyerson, A. (2004). Approximation algorithms for deadline-TSP and vehicle routing with time-windows. In: Proc. 36th Annual ACM Symposium on Theory of Computing, pp. 166\u2013174. ACM, New York.","DOI":"10.1145\/1007352.1007385"},{"key":"6641_CR22","doi-asserted-by":"publisher","first-page":"54","DOI":"10.1016\/j.ipl.2017.07.003","volume":"127","author":"X Bao","year":"2017","unstructured":"Bao, X., Liu, Z., Yu, W., & Li, G. (2017). A note on approximation algorithms of the clustered traveling salesman problem. Information Processing Letters, 127, 54\u201357.","journal-title":"Information Processing Letters"},{"issue":"1","key":"6641_CR23","doi-asserted-by":"publisher","first-page":"76","DOI":"10.1016\/j.jalgor.2003.11.002","volume":"55","author":"R Bar-Yehuda","year":"2005","unstructured":"Bar-Yehuda, R., Even, G., & Shahar, S. M. (2005). On approximating a geometric prize-collecting traveling salesman problem with time windows. Journal of Algorithms, 55(1), 76\u201392.","journal-title":"Journal of Algorithms"},{"key":"6641_CR24","doi-asserted-by":"crossref","unstructured":"Bateni, M.H., Chekuri, C., Ene, A., Hajiaghayi, M.T., Korula, N., & Marx, D. (2011). Prize-collecting Steiner Problems on Planar Graphs, pp. 1028\u20131049. ACM, New York.","DOI":"10.1137\/1.9781611973082.79"},{"issue":"8","key":"6641_CR25","doi-asserted-by":"publisher","first-page":"2103","DOI":"10.1016\/j.cor.2013.02.007","volume":"40","author":"M Batista-Galv\u00e1n","year":"2013","unstructured":"Batista-Galv\u00e1n, M., Riera-Ledesma, J., & Salazar-Gonz\u00e1lez, J. J. (2013). The traveling purchaser problem, with multiple stacks and deliveries: A branch-and-cut approach. Computers & operations research, 40(8), 2103\u20132115.","journal-title":"Computers & operations research"},{"issue":"3","key":"6641_CR26","doi-asserted-by":"publisher","first-page":"500","DOI":"10.1145\/321832.321847","volume":"21","author":"M Bellmore","year":"1974","unstructured":"Bellmore, M., & Hong, S. (1974). Transformation of multisalesman problem to the standard traveling salesman problem. Journal of the ACM, 21(3), 500\u2013504.","journal-title":"Journal of the ACM"},{"issue":"4","key":"6641_CR27","doi-asserted-by":"publisher","first-page":"2995","DOI":"10.1137\/22M1483414","volume":"36","author":"K B\u00e9rczi","year":"2022","unstructured":"B\u00e9rczi, K., Mnich, M., & Vincze, R. (2022). A 3\/2-approximation for the Metric Many-Visits Path TSP. SIAM Journal on Discrete Mathematics, 36(4), 2995\u20133030.","journal-title":"SIAM Journal on Discrete Mathematics"},{"key":"6641_CR28","first-page":"296","volume-title":"Approximation Algorithms for NP-hard Problems","author":"M Bern","year":"1996","unstructured":"Bern, M., & Eppstein, D. (1996). Approximation algorithms for geometric problems. In D. S. Hochbaum (Ed.), Approximation Algorithms for NP-hard Problems (pp. 296\u2013345). Worcester: PWS Publishing Co."},{"issue":"5","key":"6641_CR29","doi-asserted-by":"publisher","first-page":"34","DOI":"10.1038\/scientificamerican0501-34","volume":"284","author":"T Berners-Lee","year":"2001","unstructured":"Berners-Lee, T., Hendler, J. A., & Lassila, O. (2001). The Semantic Web. Scientific American, 284(5), 34\u201343.","journal-title":"Scientific American"},{"issue":"1","key":"6641_CR30","doi-asserted-by":"publisher","first-page":"56","DOI":"10.1002\/net.20307","volume":"54","author":"J-F B\u00e9rub\u00e9","year":"2009","unstructured":"B\u00e9rub\u00e9, J.-F., Gendreau, M., & Potvin, J.-Y. (2009). A branch-and-cut algorithm for the undirected prize collecting traveling salesman problem. Networks: An Int. Journal, 54(1), 56\u201367.","journal-title":"Networks: An Int. Journal"},{"key":"6641_CR31","doi-asserted-by":"crossref","unstructured":"Bhattacharya, B., \u0106usti\u0107, A., Rafiey, A., Rafiey, A., & Sokol, V. (2015). Approximation algorithms for generalized MST and TSP in grid clusters. In: Proc. 9th Int. Conf. on Combinatorial Optimization and Applications, pp. 110\u2013125. Springer","DOI":"10.1007\/978-3-319-26626-8_9"},{"issue":"1","key":"6641_CR32","doi-asserted-by":"publisher","first-page":"413","DOI":"10.1007\/BF01581256","volume":"59","author":"D Bienstock","year":"1993","unstructured":"Bienstock, D., Goemans, M. X., Simchi-Levi, D., & Williamson, D. (1993). A note on the prize collecting traveling salesman problem. Mathematical programming, 59(1), 413\u2013420.","journal-title":"Mathematical programming"},{"issue":"4","key":"6641_CR33","doi-asserted-by":"publisher","first-page":"685","DOI":"10.1016\/j.disopt.2008.04.001","volume":"5","author":"L-P Bigras","year":"2008","unstructured":"Bigras, L.-P., Gamache, M., & Savard, G. (2008). The time-dependent traveling salesman problem and single machine scheduling problems with sequence dependent setup times. Discrete Optimization, 5(4), 685\u2013699.","journal-title":"Discrete Optimization"},{"key":"6641_CR34","doi-asserted-by":"crossref","unstructured":"Blauth, J., Klein, N., & N\u00e4gele, M. (2024). A better-than-1.6-approximation for Prize-Collecting TSP. In: Vygen, J., Byrka, J. (eds.) Integer Programming and Combinatorial Optimization, pp. 28\u201342. Springer, Cham.","DOI":"10.1007\/978-3-031-59835-7_3"},{"key":"6641_CR35","volume-title":"Handbook on Scheduling: From Theory to Practice","author":"J Blazewicz","year":"2019","unstructured":"Blazewicz, J., Ecker, K. H., Pesch, E., Schmidt, G., Sterna, M., & Weglarz, J. (2019). Handbook on Scheduling: From Theory to Practice. Cham: Springer."},{"issue":"2","key":"6641_CR36","doi-asserted-by":"publisher","first-page":"653","DOI":"10.1137\/050645464","volume":"37","author":"A Blum","year":"2007","unstructured":"Blum, A., Chawla, S., Karger, D. R., Lane, T., Meyerson, A., & Minkoff, M. (2007). Approximation algorithms for orienteering and discounted-reward TSP. SIAM Journal on Computing, 37(2), 653\u2013670.","journal-title":"SIAM Journal on Computing"},{"issue":"3","key":"6641_CR37","doi-asserted-by":"publisher","first-page":"431","DOI":"10.1007\/s00224-007-1347-x","volume":"41","author":"H-J Bockenhauer","year":"2007","unstructured":"Bockenhauer, H.-J., Hromkovic, J., Kneis, J., & Kupke, J. (2007). The parameterized approximability of TSP with deadlines. Theory of Computing Systems, 41(3), 431\u2013444.","journal-title":"Theory of Computing Systems"},{"issue":"21\u201323","key":"6641_CR38","doi-asserted-by":"publisher","first-page":"2241","DOI":"10.1016\/j.tcs.2009.02.016","volume":"410","author":"H-J B\u00f6ckenhauer","year":"2009","unstructured":"B\u00f6ckenhauer, H.-J., Kneis, J., & Kupke, J. (2009). Approximation hardness of deadline-tsp reoptimization. Theoretical Computer Science, 410(21\u201323), 2241\u20132249.","journal-title":"Theoretical Computer Science"},{"key":"6641_CR39","doi-asserted-by":"publisher","first-page":"11","DOI":"10.1016\/0305-7097(75)90003-4","volume":"1","author":"LD Bodin","year":"1975","unstructured":"Bodin, L. D. (1975). A taxonomic structure for vehicle routing and scheduling problems. Computers and Urban Society, 1, 11\u201329.","journal-title":"Computers and Urban Society"},{"key":"6641_CR40","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1002\/net.3230110204","volume":"11","author":"LD Bodin","year":"1981","unstructured":"Bodin, L. D., & Golden, B. (1981). Classification in vehicle routing and scheduling. Networks, 11, 97\u2013108.","journal-title":"Networks"},{"issue":"2","key":"6641_CR41","doi-asserted-by":"publisher","first-page":"628","DOI":"10.1016\/j.cor.2006.03.023","volume":"35","author":"B Bontoux","year":"2008","unstructured":"Bontoux, B., & Feillet, D. (2008). Ant colony optimization for the traveling purchaser problem. Computers & Operations Research, 35(2), 628\u2013637.","journal-title":"Computers & Operations Research"},{"key":"6641_CR42","doi-asserted-by":"publisher","first-page":"300","DOI":"10.1016\/j.cie.2015.12.007","volume":"99","author":"K Braekers","year":"2016","unstructured":"Braekers, K., Ramaekers, K., & Van Nieuwenhuyse, I. (2016). The vehicle routing problem: State of the art classification and review. Computers & Industrial Engineering, 99, 300\u2013313.","journal-title":"Computers & Industrial Engineering"},{"issue":"4","key":"6641_CR43","doi-asserted-by":"publisher","first-page":"299","DOI":"10.1007\/s00453-004-1088-z","volume":"39","author":"B Brod\u00e9n","year":"2004","unstructured":"Brod\u00e9n, B., Hammar, M., & Nilsson, B. J. (2004). Online and offline algorithms for the time-dependent TSP with time zones. Algorithmica, 39(4), 299\u2013319.","journal-title":"Algorithmica"},{"key":"6641_CR44","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-03088-2","volume-title":"Scheduling Algorithms","author":"P Brucker","year":"1995","unstructured":"Brucker, P. (1995). Scheduling Algorithms. Heidelberg: Springer."},{"issue":"3","key":"6641_CR45","doi-asserted-by":"publisher","first-page":"496","DOI":"10.1137\/S0036144596297514","volume":"40","author":"RE Burkard","year":"1998","unstructured":"Burkard, R. E., Deineko, V. G., Dal, R., Veen, J. A. A., & Woeginger, G. J. (1998). Well-solvable special cases of the traveling salesman problem: A survey. SIAM Review, 40(3), 496\u2013546.","journal-title":"SIAM Review"},{"key":"6641_CR46","doi-asserted-by":"publisher","first-page":"291","DOI":"10.1057\/jors.1966.56","volume":"17","author":"RM Burstall","year":"1966","unstructured":"Burstall, R. M. (1966). A heuristic method for a job-scheduling problem. Journal of the Operational Research Society, 17, 291\u2013304.","journal-title":"Journal of the Operational Research Society"},{"key":"6641_CR47","first-page":"274","volume":"10","author":"T Bylander","year":"1991","unstructured":"Bylander, T. (1991). Complexity results for planning. In: Proc. 12th Int. Joint Conference on Artificial Intelligence, 10, 274\u2013279.","journal-title":"In: Proc. 12th Int. Joint Conference on Artificial Intelligence"},{"key":"6641_CR48","doi-asserted-by":"crossref","unstructured":"Chan, C.-l., & Young, G.H. (1995). Single-vehicle scheduling problem on a straight line with time window constraints. In: Proc. 1st Int. Computing and Combinatorics Conference, pp. 617\u2013626. Springer.","DOI":"10.1007\/BFb0030884"},{"key":"6641_CR49","doi-asserted-by":"publisher","DOI":"10.1016\/j.cosrev.2021.100369","volume":"40","author":"O Cheikhrouhou","year":"2021","unstructured":"Cheikhrouhou, O., & Khoufi, I. (2021). A comprehensive survey on the multiple traveling salesman problem: Applications, approaches and taxonomy. Computer Science Review, 40, Article 100369.","journal-title":"Computer Science Review"},{"key":"6641_CR50","doi-asserted-by":"crossref","unstructured":"Chekuri, C., & Kumar, A. (2004). Maximum coverage problem with group budget constraints and applications. Randomization, and Combinatorial Optimization - Algorithms and TechniquesApproximation (pp. 72\u201383). Berlin, Heidelberg: Springer.","DOI":"10.1007\/978-3-540-27821-4_7"},{"key":"6641_CR51","doi-asserted-by":"crossref","unstructured":"Chekuri, C., & Pal, M. (2005). A recursive greedy algorithm for walks in directed graphs. In: 46th Annual IEEE Symposium on Foundations of Computer Science, pp. 245\u2013253. IEEE","DOI":"10.1109\/SFCS.2005.9"},{"issue":"3","key":"6641_CR52","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/2229163.2229167","volume":"8","author":"C Chekuri","year":"2012","unstructured":"Chekuri, C., Korula, N., & P\u00e1l, M. (2012). Improved algorithms for orienteering and related problems. ACM Transactions on Algorithms, 8(3), 1\u201327.","journal-title":"ACM Transactions on Algorithms"},{"key":"6641_CR53","doi-asserted-by":"crossref","unstructured":"Chen, Y. (2023). Approximation schemes for capacity vehicle routing problems: A survey. arXiv preprint arXiv:2306.01826.","DOI":"10.1109\/ICCMSO59960.2023.00059"},{"issue":"1","key":"6641_CR54","doi-asserted-by":"publisher","first-page":"385","DOI":"10.1137\/060667839","volume":"38","author":"K Chen","year":"2008","unstructured":"Chen, K., & Har-Peled, S. (2008). The Euclidean orienteering problem revisited. SIAM Journal on Computing, 38(1), 385\u2013397.","journal-title":"SIAM Journal on Computing"},{"issue":"4","key":"6641_CR55","doi-asserted-by":"publisher","first-page":"309","DOI":"10.1007\/s00453-004-1124-z","volume":"41","author":"Y-J Chiang","year":"2005","unstructured":"Chiang, Y.-J. (2005). New approximation results for the maximum scatter TSP. Algorithmica, 41(4), 309\u2013341.","journal-title":"Algorithmica"},{"issue":"2","key":"6641_CR56","doi-asserted-by":"publisher","first-page":"145","DOI":"10.1002\/net.3230110207","volume":"11","author":"N Christofides","year":"1981","unstructured":"Christofides, N., Mingozzi, A., & Toth, P. (1981). State-space relaxation procedures for the computation of bounds to routing problems. Networks, 11(2), 145\u2013164.","journal-title":"Networks"},{"key":"6641_CR57","volume-title":"Computer and Job-Shop Scheduling Theory","author":"EG Coffman","year":"1976","unstructured":"Coffman, E. G. (1976). Computer and Job-Shop Scheduling Theory. Hoboken: Wiley."},{"key":"6641_CR58","volume-title":"Theory of Scheduling","author":"RW Conway","year":"1967","unstructured":"Conway, R. W., Maxwell, W. L., & Miller, L. W. (1967). Theory of Scheduling. Boston, MA: Addison Wesley."},{"key":"6641_CR59","doi-asserted-by":"crossref","unstructured":"Cosma, O., Pop, P.C., & Cosma, L. (2023). A hybrid based genetic algorithm for solving the clustered generalized traveling salesman problem. In: International Conference on Hybrid Artificial Intelligence Systems, pp. 352\u2013362. Springer.","DOI":"10.1007\/978-3-031-40725-3_30"},{"issue":"4","key":"6641_CR60","doi-asserted-by":"publisher","first-page":"576","DOI":"10.1093\/jigpal\/jzae019","volume":"32","author":"O Cosma","year":"2024","unstructured":"Cosma, O., Pop, P. C., & Cosma, L. (2024). A novel memetic algorithm for solving the generalized traveling salesman problem. Logic Journal of the IGPL, 32(4), 576\u2013588.","journal-title":"Logic Journal of the IGPL"},{"issue":"1","key":"6641_CR61","doi-asserted-by":"publisher","first-page":"4","DOI":"10.1016\/0377-2217(93)90140-I","volume":"65","author":"J Current","year":"1993","unstructured":"Current, J., & Marsh, M. (1993). Multiobjective transportation network design and routing problems: Taxonomy and annotation. European Journal of Operational Research, 65(1), 4\u201319.","journal-title":"European Journal of Operational Research"},{"issue":"2","key":"6641_CR62","doi-asserted-by":"publisher","first-page":"187","DOI":"10.1016\/0377-2217(86)90180-3","volume":"26","author":"J Current","year":"1986","unstructured":"Current, J., & Min, H. (1986). Multiobjective design of transportation networks: Taxonomy and annotation. European Journal of Operational Research, 26(2), 187\u2013201.","journal-title":"European Journal of Operational Research"},{"issue":"1","key":"6641_CR63","doi-asserted-by":"publisher","first-page":"80","DOI":"10.1287\/mnsc.6.1.80","volume":"6","author":"GB Dantzig","year":"1959","unstructured":"Dantzig, G. B., & Ramser, J. H. (1959). The truck dispatching problem. Management Science, 6(1), 80\u201391.","journal-title":"Management Science"},{"issue":"4","key":"6641_CR64","doi-asserted-by":"publisher","first-page":"393","DOI":"10.1287\/opre.2.4.393","volume":"2","author":"G Dantzig","year":"1954","unstructured":"Dantzig, G., Fulkerson, R., & Johnson, S. (1954). Solution of a large-scale traveling-salesman problem. Journal of the Operations Research Society of America, 2(4), 393\u2013410.","journal-title":"Journal of the Operations Research Society of America"},{"issue":"5","key":"6641_CR65","doi-asserted-by":"publisher","first-page":"387","DOI":"10.1007\/s10951-005-2861-9","volume":"8","author":"M Dawande","year":"2005","unstructured":"Dawande, M., Geismar, H. N., Sethi, S. P., & Sriskandarajah, C. (2005). Sequencing and scheduling in robotic cells: Recent developments. Journal of Scheduling, 8(5), 387\u2013426.","journal-title":"Journal of Scheduling"},{"key":"6641_CR66","doi-asserted-by":"publisher","first-page":"147","DOI":"10.1016\/j.disopt.2014.09.003","volume":"14","author":"VG Deineko","year":"2014","unstructured":"Deineko, V. G., Klinz, B., Tiskin, A., & Woeginger, G. J. (2014). Four-point conditions for the TSP: The complete complexity classification. Discrete optimization, 14, 147\u2013159.","journal-title":"Discrete optimization"},{"issue":"3","key":"6641_CR67","first-page":"297","volume":"2","author":"M Dell\u2019Amico","year":"1995","unstructured":"Dell\u2019Amico, M., Maffioli, F., & V\u00e4rbrand, P. (1995). On prize-collecting tours and the asymmetric travelling salesman problem. Int. Transactions in Operational Research, 2(3), 297\u2013308.","journal-title":"Int. Transactions in Operational Research"},{"key":"6641_CR68","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-45308-4","volume-title":"Modeling and Optimization in Green Logistics","author":"H Derbel","year":"2020","unstructured":"Derbel, H., Jarboui, B., & Siarry, P. (2020). Modeling and Optimization in Green Logistics. Cham: Springer."},{"key":"6641_CR69","volume-title":"Vehicle Routing: Methods and Studies","author":"M Desrochers","year":"1988","unstructured":"Desrochers, M., Lenstra, J. K., Savelsbergh, M. W., & Soumis, F. (1988). Vehicle routing with time windows: optimization and approximation. In B. L. Golden & A. A. Assad (Eds.), Vehicle Routing: Methods and Studies. Amsterdam: Elsevier."},{"issue":"3","key":"6641_CR70","doi-asserted-by":"publisher","first-page":"322","DOI":"10.1016\/0377-2217(90)90007-X","volume":"46","author":"M Desrochers","year":"1990","unstructured":"Desrochers, M., Lenstra, J. K., & Savelsbergh, M. W. P. (1990). A classification scheme for vehicle routing and scheduling problems. European Journal of Operational Research, 46(3), 322\u2013332.","journal-title":"European Journal of Operational Research"},{"issue":"2","key":"6641_CR71","doi-asserted-by":"publisher","first-page":"342","DOI":"10.1287\/opre.40.2.342","volume":"40","author":"M Desrochers","year":"1992","unstructured":"Desrochers, M., Desrosiers, J., & Solomon, M. M. (1992). A new optimization algorithm for the vehicle routing problem with time windows. Operations Research, 40(2), 342\u2013354.","journal-title":"Operations Research"},{"issue":"4","key":"6641_CR72","doi-asserted-by":"publisher","first-page":"459","DOI":"10.1016\/S1007-0214(07)70068-8","volume":"12","author":"C Ding","year":"2007","unstructured":"Ding, C., Cheng, Y., & He, M. (2007). Two-level genetic algorithm for clustered traveling salesman problem with application in large-scale TSPs. Tsinghua Science & Technology, 12(4), 459\u2013465.","journal-title":"Tsinghua Science & Technology"},{"key":"6641_CR73","unstructured":"Djang, L.P. (1993). The wandering salesman problem. PhD thesis, The University of Texas at Arlington."},{"issue":"1","key":"6641_CR74","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1016\/S0196-6774(03)00047-6","volume":"48","author":"A Dumitrescu","year":"2003","unstructured":"Dumitrescu, A., & Mitchell, J. S. (2003). Approximation algorithms for TSP with neighborhoods in the plane. Journal of Algorithms, 48(1), 135\u2013159.","journal-title":"Journal of Algorithms"},{"key":"6641_CR75","doi-asserted-by":"publisher","first-page":"1472","DOI":"10.1016\/j.cie.2009.05.009","volume":"57","author":"B Eksioglu","year":"2009","unstructured":"Eksioglu, B., Vural, A., & Reisman, A. (2009). The vehicle routing problem: A taxonomic review. Computers and Industrial Engineering, 57, 1472\u20131483.","journal-title":"Computers and Industrial Engineering"},{"key":"6641_CR76","doi-asserted-by":"crossref","unstructured":"Fakcharoenphol, J., Rao, S., & Talwar, K. (2003). A tight bound on approximating arbitrary metrics by tree metrics. In: Proc. 35th Annual ACM Symposium on Theory of Computing, pp. 448\u2013455.","DOI":"10.1145\/780542.780608"},{"key":"6641_CR77","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1016\/j.tcs.2018.11.016","volume":"771","author":"B Farbstein","year":"2019","unstructured":"Farbstein, B., & Levin, A. (2019). Deadline TSP. Theoretical Computer Science, 771, 83\u201392.","journal-title":"Theoretical Computer Science"},{"key":"6641_CR78","doi-asserted-by":"crossref","unstructured":"Feige, U., & Singh, M. (2007). Improved approximation ratios for traveling salesperson tours and paths in directed graphs. In: Int. Workshop on Approximation Algorithms for Combinatorial Optimization, pp. 104\u2013118. Springer","DOI":"10.1007\/978-3-540-74208-1_8"},{"issue":"2","key":"6641_CR79","doi-asserted-by":"publisher","first-page":"188","DOI":"10.1287\/trsc.1030.0079","volume":"39","author":"D Feillet","year":"2005","unstructured":"Feillet, D., Dejax, P., & Gendreau, M. (2005). Traveling salesman problems with profits. Transportation Science, 39(2), 188\u2013205.","journal-title":"Transportation Science"},{"issue":"1","key":"6641_CR80","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1007\/s10107-012-0568-1","volume":"142","author":"A Fischer","year":"2013","unstructured":"Fischer, A., & Helmberg, C. (2013). The symmetric quadratic traveling salesman problem. Mathematical Programming, 142(1), 205\u2013254.","journal-title":"Mathematical Programming"},{"issue":"3","key":"6641_CR81","doi-asserted-by":"publisher","first-page":"378","DOI":"10.1287\/opre.45.3.378","volume":"45","author":"M Fischetti","year":"1997","unstructured":"Fischetti, M., Salazar Gonz\u00e1lez, J. J., & Toth, P. (1997). A branch-and-cut algorithm for the symmetric generalized traveling salesman problem. Operations Research, 45(3), 378\u2013394.","journal-title":"Operations Research"},{"issue":"2","key":"6641_CR82","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1016\/S0020-0190(01)00313-1","volume":"83","author":"FV Fomin","year":"2002","unstructured":"Fomin, F. V., & Lingas, A. (2002). Approximation algorithms for time-dependent orienteering. Information Processing Letters, 83(2), 57\u201362.","journal-title":"Information Processing Letters"},{"key":"6641_CR83","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1613\/jair.1129","volume":"20","author":"M Fox","year":"2003","unstructured":"Fox, M., & Long, D. (2003). PDDL2. 1-An extension to PDDL for expressing temporal planning domains. Journal of Artificial Intelligence Research, 20, 61\u2013124.","journal-title":"Journal of Artificial Intelligence Research"},{"issue":"3","key":"6641_CR84","doi-asserted-by":"publisher","first-page":"1198","DOI":"10.1007\/s00453-011-9515-4","volume":"62","author":"GN Frederickson","year":"2012","unstructured":"Frederickson, G. N., & Wittman, B. (2012). Approximation algorithms for the traveling repairman and speeding deliveryman problems. Algorithmica, 62(3), 1198\u20131221.","journal-title":"Algorithmica"},{"key":"6641_CR85","doi-asserted-by":"crossref","unstructured":"Friggstad, Z., & Swamy, C. (2017). Compact, provably-good LPs for orienteering and regret-bounded vehicle routing. In: Proc. 19th Int. Conference on Integer Programming and Combinatorial Optimization, pp. 199\u2013211. Springer","DOI":"10.1007\/978-3-319-59250-3_17"},{"key":"6641_CR86","unstructured":"Friggstad, Z., & Swamy, C. (2021). Constant-factor approximation to deadline TSP and related problems in (almost) quasi-polytime. In: 48th Int. Colloquium on Automata, Languages, and Programming. Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik"},{"key":"6641_CR87","doi-asserted-by":"crossref","unstructured":"Gao, J., Jia, S., Mitchell, J.S., & Zhao, L. (2020). Approximation algorithms for time-window TSP and prize collecting TSP problems. In: Algorithmic Foundations of Robotics XII, pp. 560\u2013575. Springer, Cham.","DOI":"10.1007\/978-3-030-43089-4_36"},{"issue":"3","key":"6641_CR88","doi-asserted-by":"publisher","first-page":"435","DOI":"10.1145\/322077.322086","volume":"25","author":"RS Garfinkel","year":"1978","unstructured":"Garfinkel, R. S., & Gilbert, K. C. (1978). The bottleneck traveling salesman problem: Algorithms and probabilistic analysis. Journal of the ACM (JACM), 25(3), 435\u2013448.","journal-title":"Journal of the ACM (JACM)"},{"key":"6641_CR89","doi-asserted-by":"crossref","unstructured":"Garg, N. (2005). Saving an epsilon: a 2-approximation for the k-MST problem in graphs. In: Proc. of the 37th Annual ACM Symposium on Theory of Computing, pp. 396\u2013402.","DOI":"10.1145\/1060590.1060650"},{"issue":"1","key":"6641_CR90","doi-asserted-by":"publisher","first-page":"66","DOI":"10.1006\/jagm.2000.1096","volume":"37","author":"N Garg","year":"2000","unstructured":"Garg, N., Konjevod, G., & Ravi, R. (2000). A polylogarithmic approximation algorithm for the group Steiner tree problem. Journal of Algorithms, 37(1), 66\u201384.","journal-title":"Journal of Algorithms"},{"issue":"3","key":"6641_CR91","doi-asserted-by":"publisher","first-page":"330","DOI":"10.1287\/opre.46.3.330","volume":"46","author":"M Gendreau","year":"1998","unstructured":"Gendreau, M., Hertz, A., Laporte, G., & Stan, M. (1998). A generalized insertion heuristic for the traveling salesman problem with time windows. Operations Research, 46(3), 330\u2013335.","journal-title":"Operations Research"},{"key":"6641_CR92","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1016\/j.cor.2015.06.001","volume":"64","author":"M Gendreau","year":"2015","unstructured":"Gendreau, M., Ghiani, G., & Guerriero, E. (2015). Time-dependent routing problems: A review. Computers & operations research, 64, 189\u2013197.","journal-title":"Computers & operations research"},{"key":"6641_CR93","unstructured":"Glebov, A.N. (2017). A 5\/6-approximation algorithm for the pseudo-metric TSP-max in an incomplete graph. In: Proc. 17th Int. Baikal Seminar on Optimization Methods and Applications."},{"issue":"2","key":"6641_CR94","doi-asserted-by":"publisher","first-page":"296","DOI":"10.1137\/S0097539793242618","volume":"24","author":"MX Goemans","year":"1995","unstructured":"Goemans, M. X., & Williamson, D. P. (1995). A general approximation technique for constrained forest problems. SIAM Journal on Computing, 24(2), 296\u2013317.","journal-title":"SIAM Journal on Computing"},{"issue":"3","key":"6641_CR95","doi-asserted-by":"publisher","first-page":"307","DOI":"10.1002\/1520-6750(198706)34:3<307::AID-NAV3220340302>3.0.CO;2-D","volume":"34","author":"BL Golden","year":"1987","unstructured":"Golden, B. L., Levy, L., & Vohra, R. (1987). The orienteering problem. Naval Research Logistics, 34(3), 307\u2013318.","journal-title":"Naval Research Logistics"},{"key":"6641_CR96","doi-asserted-by":"publisher","DOI":"10.1007\/978-0-387-77778-8","volume-title":"The Vehicle Routing Problem: Latest Advances and New Challenges","author":"BL Golden","year":"2008","unstructured":"Golden, B. L., Raghavan, S., & Wasil, E. A. (2008). The Vehicle Routing Problem: Latest Advances and New Challenges (Vol. 43). New York: Springer."},{"issue":"1","key":"6641_CR97","doi-asserted-by":"publisher","first-page":"69","DOI":"10.1016\/0377-2217(93)E0238-S","volume":"83","author":"L Gouveia","year":"1995","unstructured":"Gouveia, L., & Vo\u00df, S. (1995). A classification of formulations for the (time-dependent) traveling salesman problem. European Journal of Operational Research, 83(1), 69\u201382.","journal-title":"European Journal of Operational Research"},{"key":"6641_CR98","doi-asserted-by":"crossref","unstructured":"Graham, R.L., Lawler, E.L., Lenstra, J.K., & Kan, A.R. (1979). Optimization and approximation in deterministic sequencing and scheduling: a survey. In: Annals of Discrete Mathematics vol. 5, pp. 287\u2013326. Elsevier, Amsterdam.","DOI":"10.1016\/S0167-5060(08)70356-X"},{"issue":"4","key":"6641_CR99","doi-asserted-by":"publisher","first-page":"374","DOI":"10.1007\/PL00009201","volume":"20","author":"S Guha","year":"1998","unstructured":"Guha, S., & Khuller, S. (1998). Approximation algorithms for connected dominating sets. Algorithmica, 20(4), 374\u2013387.","journal-title":"Algorithmica"},{"key":"6641_CR100","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1016\/j.tcs.2022.06.007","volume":"928","author":"X Guo","year":"2022","unstructured":"Guo, X., Luo, K., Tang, Z. G., & Zhang, Y. (2022). The online food delivery problem on stars. Theoretical Computer Science, 928, 13\u201326.","journal-title":"Theoretical Computer Science"},{"key":"6641_CR101","volume-title":"The Traveling Salesman Problem and Its Variations","author":"G Gutin","year":"2006","unstructured":"Gutin, G., & Punnen, A. P. (2006). The Traveling Salesman Problem and Its Variations (Vol. 12). New York: Springer."},{"issue":"4","key":"6641_CR102","doi-asserted-by":"publisher","first-page":"555","DOI":"10.7155\/jgaa.00478","volume":"22","author":"N Guttmann-Beck","year":"2018","unstructured":"Guttmann-Beck, N., Knaan, E., & Stern, M. (2018). Approximation algorithms for not necessarily disjoint clustered TSP. Journal of Graph Algorithms and Applications, 22(4), 555\u2013575.","journal-title":"Journal of Graph Algorithms and Applications"},{"issue":"4","key":"6641_CR103","doi-asserted-by":"publisher","first-page":"527","DOI":"10.1287\/moor.10.4.527","volume":"10","author":"M Haimovich","year":"1985","unstructured":"Haimovich, M., & Rinnooy Kan, A. H. (1985). Bounds and heuristics for capacitated routing problems. Mathematics of Operations Research, 10(4), 527\u2013542.","journal-title":"Mathematics of Operations Research"},{"key":"6641_CR104","doi-asserted-by":"publisher","first-page":"635","DOI":"10.1007\/s00454-001-0081-4","volume":"27","author":"M Hammar","year":"2002","unstructured":"Hammar, M., & Nilsson, B. J. (2002). Approximation results for kinetic variants of TSP. Discrete & Computational Geometry, 27, 635\u2013651.","journal-title":"Discrete & Computational Geometry"},{"issue":"1","key":"6641_CR105","doi-asserted-by":"publisher","first-page":"21","DOI":"10.3390\/a14010021","volume":"14","author":"C Hansknecht","year":"2021","unstructured":"Hansknecht, C., Joormann, I., & Stiller, S. (2021). Dynamic shortest paths methods for the time-dependent TSP. Algorithms, 14(1), 21\u201344.","journal-title":"Algorithms"},{"key":"6641_CR106","doi-asserted-by":"crossref","unstructured":"Helvig, C.S., Robins, G., & Zelikovsky, A. (1998). Moving-target TSP and related problems. In: European Symposium on Algorithms, pp. 453\u2013464. Springer","DOI":"10.1007\/3-540-68530-8_38"},{"issue":"1","key":"6641_CR107","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1016\/S0196-6774(03)00075-0","volume":"49","author":"CS Helvig","year":"2003","unstructured":"Helvig, C. S., Robins, G., & Zelikovsky, A. (2003). The moving-target traveling salesman problem. Journal of Algorithms, 49(1), 153\u2013174.","journal-title":"Journal of Algorithms"},{"key":"6641_CR108","doi-asserted-by":"crossref","unstructured":"Hoffmann, I., Kurz, S., & Rambau, J. (2017). The maximum scatter TSP on a regular grid. In: Selected Papers of the Int. Conference of the German, Austrian and Swiss Operations Research Societies, pp. 63\u201370. Springer","DOI":"10.1007\/978-3-319-42902-1_9"},{"key":"6641_CR109","doi-asserted-by":"crossref","unstructured":"Irnich, S., Toth, P., & Vigo, D. (2014). Chapter 1: The family of vehicle routing problems. Methods, and ApplicationsVehicle Routing: Problems (pp. 1\u201333). Philadelphia: SIAM.","DOI":"10.1137\/1.9781611973594.ch1"},{"issue":"1","key":"6641_CR110","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/321992.321993","volume":"24","author":"DB Johnson","year":"1977","unstructured":"Johnson, D. B. (1977). Efficient algorithms for shortest paths in sparse networks. J. ACM, 24(1), 1\u201313.","journal-title":"J. ACM"},{"issue":"3","key":"6641_CR111","doi-asserted-by":"publisher","first-page":"315","DOI":"10.1016\/j.jda.2008.11.007","volume":"7","author":"M-Y Kao","year":"2009","unstructured":"Kao, M.-Y., & Sanghi, M. (2009). An approximation algorithm for a bottleneck traveling salesman problem. Journal of Discrete Algorithms, 7(3), 315\u2013326.","journal-title":"Journal of Discrete Algorithms"},{"key":"6641_CR112","doi-asserted-by":"publisher","first-page":"849","DOI":"10.1016\/S2212-5671(16)30252-0","volume":"39","author":"I Kara","year":"2016","unstructured":"Kara, I., Bicakci, P. S., & Derya, T. (2016). New formulations for the orienteering problem. Procedia Economics and Finance, 39, 849\u2013854.","journal-title":"Procedia Economics and Finance"},{"key":"6641_CR113","doi-asserted-by":"crossref","unstructured":"Karlin, A.R., Klein, N., & Gharan, S.O. (2021). A (slightly) improved approximation algorithm for metric TSP. In: Proc. 53rd Annual ACM SIGACT Symposium on Theory of Computing, pp. 32\u201345.","DOI":"10.1145\/3406325.3451009"},{"key":"6641_CR114","doi-asserted-by":"crossref","unstructured":"Karp, R.M. (1972). Reducibility among combinatorial problems. In: Miller, R.E., Thatcher, J.W., Bohlinger, J.D. (eds.) Proc. Symposium on the Complexity of Computer Computations, pp. 85\u2013103. Springer, Boston.","DOI":"10.1007\/978-1-4684-2001-2_9"},{"issue":"8","key":"6641_CR115","doi-asserted-by":"publisher","first-page":"1665","DOI":"10.1016\/j.jcss.2015.06.003","volume":"81","author":"M Karpinski","year":"2015","unstructured":"Karpinski, M., Lampis, M., & Schmied, R. (2015). New inapproximability bounds for TSP. Journal of Computer and System Sciences, 81(8), 1665\u20131677.","journal-title":"Journal of Computer and System Sciences"},{"key":"6641_CR116","unstructured":"Karuno, Y., Nagamochi, H., & Ibaraki, T. (1998). A 1.5-approximation for single-vehicle scheduling problem on a line with release and handling times. In: Japan-USA Symposium on Flexible Automation, pp. 1363\u20131366. ISCIE\/ASME, New York."},{"key":"6641_CR117","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1023\/A:1018928911513","volume":"69","author":"Y Karuno","year":"1997","unstructured":"Karuno, Y., Nagamochi, H., & Ibaraki, T. (1997). Vehicle scheduling on a tree with release and handling times. Annals of Operations Research, 69, 193\u2013207.","journal-title":"Annals of Operations Research"},{"issue":"4","key":"6641_CR118","doi-asserted-by":"publisher","first-page":"203","DOI":"10.1002\/net.10028","volume":"39","author":"Y Karuno","year":"2002","unstructured":"Karuno, Y., Nagamochi, H., & Ibaraki, T. (2002). Better approximation ratios for the single-vehicle scheduling problems on line-shaped networks. Networks, 39(4), 203\u2013209.","journal-title":"Networks"},{"issue":"4","key":"6641_CR119","doi-asserted-by":"publisher","first-page":"515","DOI":"10.15807\/jorsj.31.515","volume":"31","author":"S Kataoka","year":"1988","unstructured":"Kataoka, S., & Morito, S. (1988). An algorithm for single constraint maximum collection problem. Journal of the Operations Research Society of Japan, 31(4), 515\u2013531.","journal-title":"Journal of the Operations Research Society of Japan"},{"issue":"2","key":"6641_CR120","doi-asserted-by":"publisher","first-page":"60","DOI":"10.15807\/jorsj.63.60","volume":"63","author":"M Kawasaki","year":"2020","unstructured":"Kawasaki, M., & Takazawa, K. (2020). Improving approximation rations for the clustered traveling salesman problem. Journal of the Operations Research Society of Japan, 63(2), 60\u201370.","journal-title":"Journal of the Operations Research Society of Japan"},{"key":"6641_CR121","doi-asserted-by":"crossref","unstructured":"Khachay, M., & Dubinin, R. (2016). PTAS for the euclidean capacitated vehicle routing problem. In: Proc. 9th Int. Conference on Discrete Optimization and Operations Research, pp. 193\u2013205. Springer.","DOI":"10.1007\/978-3-319-44914-2_16"},{"key":"6641_CR122","doi-asserted-by":"crossref","unstructured":"Khachay, M., & Ogorodnikov, Y. (2018). Improved polynomial time approximation scheme for capacitated vehicle routing problem with time windows. In: Proc. 4th Int. Conference on Optimization and Applications, pp. 155\u2013169. Springer","DOI":"10.1007\/978-3-030-10934-9_12"},{"key":"6641_CR123","doi-asserted-by":"crossref","unstructured":"Khachay, M., & Ogorodnikov, Y. (2019). Approximation scheme for the capacitated vehicle routing problem with time windows and non-uniform demand. In: Proc. 18th Int. Conference on Mathematical Optimization Theory and Operations Research, pp. 309\u2013327. Springer.","DOI":"10.1007\/978-3-030-22629-9_22"},{"key":"6641_CR124","doi-asserted-by":"crossref","unstructured":"Khachay, M., Neznakhina, E.D., & Ryzhenko, K.V. (2022). Constant-factor approximation algorithms for a series of combinatorial routing problems based on the reduction to the asymmetric traveling salesman problem. Proc. of the Steklov Institute of Mathematics 319(Suppl 1), 140\u2013155","DOI":"10.1134\/S0081543822060128"},{"issue":"1","key":"6641_CR125","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1007\/s10472-019-09626-w","volume":"88","author":"M Khachay","year":"2020","unstructured":"Khachay, M., & Neznakhina, K. (2020). Complexity and approximability of the euclidean generalized traveling salesman problem in grid clusters. Annals of Mathematics and Artificial Intelligence, 88(1), 53\u201369.","journal-title":"Annals of Mathematics and Artificial Intelligence"},{"key":"6641_CR126","doi-asserted-by":"crossref","unstructured":"Klein, P.N. (2005). A linear-time approximation scheme for planar weighted TSP. In: 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS\u201905), pp. 647\u2013656.","DOI":"10.1109\/SFCS.2005.7"},{"key":"6641_CR127","doi-asserted-by":"crossref","unstructured":"Klein, P.N. (2006). A subset spanner for planar graphs, with application to subset tsp. In: Proceedings of the Thirty-Eighth Annual ACM Symposium on Theory of Computing. STOC \u201906, pp. 749\u2013756. Association for Computing Machinery, New York, NY, USA.","DOI":"10.1145\/1132516.1132620"},{"key":"6641_CR128","doi-asserted-by":"crossref","unstructured":"Koehler, J., B\u00fcrgler, J., Fontana, U., Fux, E., Herzog, F., Pouly, M., Saller, S., Salyaeva, A., Scheiblechner, P., & Waelti, K. (2021). Cable tree wiring-benchmarking solvers on a real-world scheduling problem with a variety of precedence constraints. Constraints, 1\u201351","DOI":"10.1007\/s10601-021-09321-w"},{"issue":"1\u20132","key":"6641_CR129","doi-asserted-by":"publisher","first-page":"379","DOI":"10.1007\/s10107-019-01450-8","volume":"183","author":"A K\u00f6hne","year":"2020","unstructured":"K\u00f6hne, A., Traub, V., & Vygen, J. (2020). The asymmetric traveling salesman path LP has constant integrality ratio. Mathematical Programming, 183(1\u20132), 379\u2013395.","journal-title":"Mathematical Programming"},{"issue":"89","key":"6641_CR130","first-page":"79","volume":"27","author":"W Kongkaew","year":"2014","unstructured":"Kongkaew, W., & Pichitlamken, J. (2014). A survey of approximate methods for the traveling salesman problem. Kasetsart Engineering Journal, 27(89), 79\u201387.","journal-title":"Kasetsart Engineering Journal"},{"key":"6641_CR131","volume-title":"Approximation Algorithms for Network Design and Orienteering","author":"NJ Korula","year":"2010","unstructured":"Korula, N. J. (2010). Approximation Algorithms for Network Design and Orienteering. Urbana-Champaign: University of Illinois."},{"key":"6641_CR132","unstructured":"Kozma, L., & M\u00f6mke, T. (2015). A PTAS for euclidean maximum scatter TSP. In: Proc. 32nd European Workshop on Computational Geometry, pp. 1512\u201302963. CoRR, Lugano."},{"issue":"1","key":"6641_CR133","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.ejor.2014.07.048","volume":"241","author":"R Lahyani","year":"2015","unstructured":"Lahyani, R., Khemakhem, M., & Semet, F. (2015). Rich vehicle routing problems: From a taxonomy to a definition. European Journal of Operational Research, 241(1), 1\u201314.","journal-title":"European Journal of Operational Research"},{"issue":"2","key":"6641_CR134","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1016\/0167-6377(90)90052-7","volume":"9","author":"A Langevin","year":"1990","unstructured":"Langevin, A., Soumis, F., & Desrosiers, J. (1990). Classification of travelling salesman problem formulations. Operations Research Letters, 9(2), 127\u2013132.","journal-title":"Operations Research Letters"},{"issue":"2","key":"6641_CR135","doi-asserted-by":"publisher","first-page":"231","DOI":"10.1016\/0377-2217(92)90138-Y","volume":"59","author":"G Laporte","year":"1992","unstructured":"Laporte, G. (1992). The traveling salesman problem: An overview of exact and approximate algorithms. European Journal of Operational Research, 59(2), 231\u2013247.","journal-title":"European Journal of Operational Research"},{"issue":"2\u20133","key":"6641_CR136","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1016\/0166-218X(90)90100-Q","volume":"26","author":"G Laporte","year":"1990","unstructured":"Laporte, G., & Martello, S. (1990). The selective travelling salesman problem. Discrete Applied Mathematics, 26(2\u20133), 193\u2013207.","journal-title":"Discrete Applied Mathematics"},{"issue":"1","key":"6641_CR137","doi-asserted-by":"publisher","first-page":"227","DOI":"10.1007\/BF02098290","volume":"61","author":"G Laporte","year":"1995","unstructured":"Laporte, G., & Osman, I. H. (1995). Routing problems: A bibliography. Annals of operations research, 61(1), 227\u2013262.","journal-title":"Annals of operations research"},{"issue":"9","key":"6641_CR138","doi-asserted-by":"publisher","first-page":"972","DOI":"10.1057\/palgrave.jors.2601420","volume":"53","author":"G Laporte","year":"2002","unstructured":"Laporte, G., & Palekar, U. (2002). Some applications of the clustered travelling salesman problem. Journal of the Operational Research Society, 53(9), 972\u2013976.","journal-title":"Journal of the Operational Research Society"},{"issue":"3","key":"6641_CR139","doi-asserted-by":"publisher","first-page":"187","DOI":"10.1007\/BF00127356","volume":"2","author":"G Laporte","year":"1997","unstructured":"Laporte, G., Potvin, J.-Y., & Quilleret, F. (1997). A tabu search heuristic using genetic diversification for the clustered traveling salesman problem. Journal of Heuristics, 2(3), 187\u2013200.","journal-title":"Journal of Heuristics"},{"issue":"6","key":"6641_CR140","doi-asserted-by":"publisher","first-page":"940","DOI":"10.1287\/opre.51.6.940.24921","volume":"51","author":"G Laporte","year":"2003","unstructured":"Laporte, G., Riera-Ledesma, J., & Salazar-Gonz\u00e1lez, J.-J. (2003). A branch-and-cut algorithm for the undirected traveling purchaser problem. Operations Research, 51(6), 940\u2013951.","journal-title":"Operations Research"},{"key":"6641_CR141","doi-asserted-by":"publisher","first-page":"20","DOI":"10.1016\/j.cor.2013.08.005","volume":"43","author":"J LaRusic","year":"2014","unstructured":"LaRusic, J., & Punnen, A. P. (2014). The asymmetric bottleneck traveling salesman problem: algorithms, complexity and empirical analysis. Computers & Operations Research, 43, 20\u201335.","journal-title":"Computers & Operations Research"},{"key":"6641_CR142","doi-asserted-by":"publisher","first-page":"445","DOI":"10.1016\/S0927-0507(05)80189-6","volume":"4","author":"EL Lawler","year":"1993","unstructured":"Lawler, E. L., Lenstra, J. K., Kan, A. H. R., & Shmoys, D. B. (1993). Sequencing and scheduling: Algorithms and complexity. Handbooks in Operations Research and Management Science, 4, 445\u2013522.","journal-title":"Handbooks in Operations Research and Management Science"},{"key":"6641_CR143","unstructured":"Le\u00a0Digabel, S., & Wild, S.M. (2015). A taxonomy of constraints in simulation-based optimization. arXiv preprint arXiv:1505.07881"},{"issue":"3","key":"6641_CR144","doi-asserted-by":"publisher","first-page":"517","DOI":"10.1016\/0377-2217(94)90247-X","volume":"73","author":"AC Leifer","year":"1994","unstructured":"Leifer, A. C., & Rosenwein, M. B. (1994). Strong linear programming relaxations for the orienteering problem. European Journal of Operational Research, 73(3), 517\u2013523.","journal-title":"European Journal of Operational Research"},{"issue":"1\u20132","key":"6641_CR145","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1016\/0020-0255(93)90133-7","volume":"74","author":"Y-N Lien","year":"1993","unstructured":"Lien, Y.-N., Ma, E., & Wah, B. W. S. (1993). Transformation of the generalized traveling-salesman problem into the standard traveling-salesman problem. Information Sciences, 74(1\u20132), 177\u2013189.","journal-title":"Information Sciences"},{"issue":"4","key":"6641_CR146","doi-asserted-by":"publisher","first-page":"1118","DOI":"10.1016\/j.eswa.2013.07.107","volume":"41","author":"C Lin","year":"2014","unstructured":"Lin, C., Choy, K. L., Ho, G. T., Chung, S. H., & Lam, H. (2014). Survey of green vehicle routing problem: past and future trends. Expert Systems with Applications, 41(4), 1118\u20131138.","journal-title":"Expert Systems with Applications"},{"issue":"1","key":"6641_CR147","doi-asserted-by":"publisher","first-page":"45","DOI":"10.1016\/0377-2217(94)00299-1","volume":"90","author":"C Malandraki","year":"1996","unstructured":"Malandraki, C., & Dial, R. B. (1996). A restricted dynamic programming heuristic algorithm for the time dependent traveling salesman problem. European Journal of Operational Research, 90(1), 45\u201355.","journal-title":"European Journal of Operational Research"},{"issue":"1","key":"6641_CR148","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.ejor.2016.12.017","volume":"259","author":"D Manerba","year":"2017","unstructured":"Manerba, D., Mansini, R., & Riera-Ledesma, J. (2017). The traveling purchaser problem and its variants. European Journal of Operational Research, 259(1), 1\u201318.","journal-title":"European Journal of Operational Research"},{"key":"6641_CR149","doi-asserted-by":"crossref","unstructured":"Marques, T.S., Cezario, S.F., Goldbarg, E.F., Goldbarg, M.C., & Maia, S.M. (2019). Quota traveling salesman with passengers and collection time. In: 28th Brazilian Conference on Intelligent Systems, pp. 299\u2013304. IEEE","DOI":"10.1109\/BRACIS.2019.00060"},{"issue":"9","key":"6641_CR150","doi-asserted-by":"publisher","first-page":"2049","DOI":"10.2514\/1.J051895","volume":"51","author":"JR Martins","year":"2013","unstructured":"Martins, J. R., & Lambe, A. B. (2013). Multidisciplinary design optimization: a survey of architectures. AIAA journal, 51(9), 2049\u20132075.","journal-title":"AIAA journal"},{"issue":"2","key":"6641_CR151","first-page":"35","volume":"21","author":"DM McDermott","year":"2000","unstructured":"McDermott, D. M. (2000). The 1998 ai planning systems competition. AI Magazine, 21(2), 35\u201355.","journal-title":"AI Magazine"},{"key":"6641_CR152","doi-asserted-by":"publisher","first-page":"145","DOI":"10.1613\/jair.1996","volume":"20","author":"DM McDermott","year":"2003","unstructured":"McDermott, D. M. (2003). PDDL2. 1-The art of the possible? Commentary on Fox and Long. Journal of Artificial Intelligence Research, 20, 145\u2013148.","journal-title":"Journal of Artificial Intelligence Research"},{"issue":"4","key":"6641_CR153","first-page":"11","volume":"2","author":"K Menger","year":"1932","unstructured":"Menger, K. (1932). Das Botenproblem. Ergebnisse eines mathematischen Kolloquiums, 2(4), 11\u201312.","journal-title":"Das Botenproblem. Ergebnisse eines mathematischen Kolloquiums"},{"issue":"4","key":"6641_CR154","doi-asserted-by":"publisher","first-page":"326","DOI":"10.1145\/321043.321046","volume":"7","author":"CE Miller","year":"1960","unstructured":"Miller, C. E., Tucker, A. W., & Zemlin, R. A. (1960). Integer programming formulation of traveling salesman problems. Journal of the ACM, 7(4), 326\u2013329.","journal-title":"Journal of the ACM"},{"issue":"1","key":"6641_CR155","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/S0377-2217(97)00172-0","volume":"108","author":"H Min","year":"1998","unstructured":"Min, H., Jayaraman, V., & Srivastava, R. (1998). Combined location-routing problems: A synthesis and future research directions. European Journal of Operational Research, 108(1), 1\u201315.","journal-title":"European Journal of Operational Research"},{"issue":"4","key":"6641_CR156","doi-asserted-by":"publisher","first-page":"1298","DOI":"10.1137\/S0097539796309764","volume":"28","author":"JSB Mitchell","year":"1999","unstructured":"Mitchell, J. S. B. (1999). Guillotine subdivisions approximate polygonal subdivisions: A simple polynomial-time approximation scheme for geometric TSP, k-MST, and related problems. SIAM Journal on Computing, 28(4), 1298\u20131309.","journal-title":"SIAM Journal on Computing"},{"key":"6641_CR157","doi-asserted-by":"crossref","unstructured":"M\u00f6mke, T., & Svensson, O. (2011). Approximating graphic TSP by matchings. In: 52nd Annual IEEE Symposium on Foundations of Computer Science, pp. 560\u2013569. IEEE","DOI":"10.1109\/FOCS.2011.56"},{"issue":"1","key":"6641_CR158","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/2739008","volume":"63","author":"T M\u00f6mke","year":"2016","unstructured":"M\u00f6mke, T., & Svensson, O. (2016). Removing and adding edges for the traveling salesman problem. Journal of the ACM, 63(1), 1\u201328.","journal-title":"Journal of the ACM"},{"key":"6641_CR159","doi-asserted-by":"publisher","first-page":"115","DOI":"10.1016\/j.cie.2014.10.029","volume":"79","author":"JR Montoya-Torres","year":"2015","unstructured":"Montoya-Torres, J. R., Franco, J. L., Isaza, S. N., Jim\u00e9nez, H. F., & Herazo-Padilla, N. (2015). A literature review on the vehicle routing problem with multiple depots. Computers & Industrial Engineering, 79, 115\u2013129.","journal-title":"Computers & Industrial Engineering"},{"issue":"4","key":"6641_CR160","doi-asserted-by":"publisher","first-page":"640","DOI":"10.1007\/s00224-012-9439-7","volume":"55","author":"M Mucha","year":"2014","unstructured":"Mucha, M. (2014). approximation for graphic TSP. Theory of Computing Systems, 55(4), 640\u2013657.","journal-title":"Theory of Computing Systems"},{"issue":"4","key":"6641_CR161","doi-asserted-by":"publisher","first-page":"256","DOI":"10.1080\/03155986.1997.11732334","volume":"35","author":"H Nagamochi","year":"1997","unstructured":"Nagamochi, H., Mochizuki, K., & Ibaraki, T. (1997). Complexity of the single vehicle scheduling problem on graphs. Information Systems and Operational Research, 35(4), 256\u2013276.","journal-title":"Information Systems and Operational Research"},{"issue":"4","key":"6641_CR162","doi-asserted-by":"publisher","first-page":"1017","DOI":"10.1007\/s00453-011-9509-2","volume":"60","author":"V Nagarajan","year":"2011","unstructured":"Nagarajan, V., & Ravi, R. (2011). The directed orienteering problem. Algorithmica, 60(4), 1017\u20131030.","journal-title":"Algorithmica"},{"issue":"1","key":"6641_CR163","doi-asserted-by":"publisher","first-page":"43","DOI":"10.1145\/200836.200848","volume":"42","author":"B Nebel","year":"1995","unstructured":"Nebel, B., & B\u00fcrckert, H.-J. (1995). Reasoning about temporal relations: A maximal tractable subclass of Allen\u2019s interval algebra. Journal of the ACM, 42(1), 43\u201366.","journal-title":"Journal of the ACM"},{"issue":"3","key":"6641_CR164","doi-asserted-by":"publisher","first-page":"294","DOI":"10.1504\/IJMOR.2012.046689","volume":"4","author":"VH Nguyen","year":"2012","unstructured":"Nguyen, V. H., & Nguyen, T. T. (2012). Approximating the asymmetric profitable tour. Int. Journal of Mathematics in Operational Research, 4(3), 294\u2013301.","journal-title":"Int. Journal of Mathematics in Operational Research"},{"key":"6641_CR165","unstructured":"Noon, C.E. (1988). The generalized traveling salesman problem. PhD thesis, University of Michigan"},{"issue":"1","key":"6641_CR166","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1080\/03155986.1993.11732212","volume":"31","author":"CE Noon","year":"1993","unstructured":"Noon, C. E., & Bean, J. C. (1993). An efficient transformation of the generalized traveling salesman problem. Information Systems and Operational Research, 31(1), 39\u201344.","journal-title":"Information Systems and Operational Research"},{"issue":"1","key":"6641_CR167","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1016\/j.cor.2012.05.018","volume":"40","author":"Q-K Pan","year":"2013","unstructured":"Pan, Q.-K., & Ruiz, R. (2013). A comprehensive review and evaluation of permutation flowshop heuristics to minimize flowtime. Computers & Operations Research, 40(1), 117\u2013128.","journal-title":"Computers & Operations Research"},{"issue":"2","key":"6641_CR168","doi-asserted-by":"publisher","first-page":"231","DOI":"10.1016\/0196-6774(84)90029-4","volume":"5","author":"CH Papadimitriou","year":"1984","unstructured":"Papadimitriou, C. H., & Vazirani, U. V. (1984). On two geometric problems related to the travelling salesman problem. Journal of Algorithms, 5(2), 231\u2013246.","journal-title":"Journal of Algorithms"},{"issue":"1","key":"6641_CR169","doi-asserted-by":"publisher","first-page":"101","DOI":"10.1007\/s00493-006-0008-z","volume":"26","author":"CH Papadimitriou","year":"2006","unstructured":"Papadimitriou, C. H., & Vempala, S. (2006). On the approximability of the traveling salesman problem. Combinatorica, 26(1), 101\u2013120.","journal-title":"Combinatorica"},{"issue":"6","key":"6641_CR170","doi-asserted-by":"publisher","first-page":"269","DOI":"10.1016\/0167-6377(84)90077-4","volume":"2","author":"RG Parker","year":"1984","unstructured":"Parker, R. G., & Rardin, R. L. (1984). Guaranteed performance heuristics for the bottleneck travelling salesman problem. Operations Research Letters, 2(6), 269\u2013272.","journal-title":"Operations Research Letters"},{"issue":"1","key":"6641_CR171","doi-asserted-by":"publisher","first-page":"300","DOI":"10.1145\/191033.191155","volume":"26","author":"RE Pattis","year":"1994","unstructured":"Pattis, R. E. (1994). Teaching EBNF first in CS 1. ACM SIGCSE Bulletin, 26(1), 300\u2013303.","journal-title":"ACM SIGCSE Bulletin"},{"key":"6641_CR172","unstructured":"Paul, A., Freund, D., Ferber, A., Shmoys, D.B., & Williamson, D..P. (2017). Prize-collecting TSP with a budget constraint. In: 25th Annual European Symposium on Algorithms. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik"},{"issue":"2","key":"6641_CR173","doi-asserted-by":"publisher","first-page":"576","DOI":"10.1287\/moor.2019.1002","volume":"45","author":"A Paul","year":"2020","unstructured":"Paul, A., Freund, D., Ferber, A., Shmoys, D. B., & Williamson, D. P. (2020). Budgeted prize-collecting traveling salesman and minimum spanning tree problems. Mathematics of Operations Research, 45(2), 576\u2013590.","journal-title":"Mathematics of Operations Research"},{"issue":"3","key":"6641_CR174","doi-asserted-by":"publisher","first-page":"230","DOI":"10.1080\/10170660409509404","volume":"21","author":"M Pfund","year":"2004","unstructured":"Pfund, M., Fowler, J. W., & Gupta, J. N. D. (2004). A survey of algorithms for single and multi-objective unrelated parallel-machine deterministic scheduling problems. Journal of the Chinese Institute of Industrial Engineers, 21(3), 230\u2013241.","journal-title":"Journal of the Chinese Institute of Industrial Engineers"},{"issue":"1","key":"6641_CR175","doi-asserted-by":"publisher","first-page":"86","DOI":"10.1287\/opre.26.1.86","volume":"26","author":"J-C Picard","year":"1978","unstructured":"Picard, J.-C., & Queyranne, M. (1978). The time-dependent traveling salesman problem and its application to the tardiness problem in one-machine scheduling. Operations research, 26(1), 86\u2013110.","journal-title":"Operations research"},{"issue":"1","key":"6641_CR176","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.ejor.2012.08.015","volume":"225","author":"V Pillac","year":"2013","unstructured":"Pillac, V., Gendreau, M., Gu\u00e9ret, C., & Medaglia, A. L. (2013). A review of dynamic vehicle routing problems. European Journal of Operational Research, 225(1), 1\u201311.","journal-title":"European Journal of Operational Research"},{"key":"6641_CR177","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4614-2361-4","volume-title":"Scheduling: Theory, Algorithms, and Systems","author":"M Pinedo","year":"2012","unstructured":"Pinedo, M. (2012). Scheduling: Theory, Algorithms, and Systems (4th ed.). Cham: Springer.","edition":"4"},{"key":"6641_CR178","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-05921-6","volume-title":"Scheduling: Theory, Algorithms, and Systems","author":"M Pinedo","year":"2022","unstructured":"Pinedo, M. (2022). Scheduling: Theory, Algorithms, and Systems (6th ed.). Cham: Springer.","edition":"6"},{"key":"6641_CR179","doi-asserted-by":"crossref","unstructured":"Pop, P.C., Cosma, O., Sabo, C., & Sitar, C.P. (2023). A comprehensive survey on the generalized traveling salesman problem. European Journal of Operational Research.","DOI":"10.1016\/j.ejor.2023.07.022"},{"issue":"1\u20134","key":"6641_CR180","doi-asserted-by":"publisher","first-page":"231","DOI":"10.1023\/A:1013111608059","volume":"104","author":"WB Powell","year":"2001","unstructured":"Powell, W. B., Shapiro, J. A., & Simao, H. P. (2001). A representational paradigm for dynamic resource transformation problems. Annals of Operations Research, 104(1\u20134), 231\u2013279.","journal-title":"Annals of Operations Research"},{"issue":"1","key":"6641_CR181","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1007\/BF02098286","volume":"61","author":"HN Psaraftis","year":"1995","unstructured":"Psaraftis, H. N. (1995). Dynamic vehicle routing: Status and prospects. Annals of Operations Research, 61(1), 143\u2013164.","journal-title":"Annals of Operations Research"},{"issue":"2","key":"6641_CR182","doi-asserted-by":"publisher","first-page":"212","DOI":"10.1287\/mnsc.36.2.212","volume":"36","author":"HN Psaraftis","year":"1990","unstructured":"Psaraftis, H. N., Solomon, M. M., Magnanti, T. L., & Kim, T.-U. (1990). Routing and scheduling on a shoreline with release times. Management Science, 36(2), 212\u2013223.","journal-title":"Management Science"},{"issue":"1","key":"6641_CR183","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1002\/net.21628","volume":"67","author":"HN Psaraftis","year":"2016","unstructured":"Psaraftis, H. N., Wen, M., & Kontovas, C. A. (2016). Dynamic vehicle routing problems: Three decades and counting. Networks, 67(1), 3\u201331.","journal-title":"Networks"},{"issue":"3","key":"6641_CR184","doi-asserted-by":"publisher","first-page":"628","DOI":"10.1287\/opre.28.3.628","volume":"28","author":"MR Rao","year":"1980","unstructured":"Rao, M. R. (1980). A note on the multiple traveling salesmen problem. Operations Research, 28(3), 628\u2013632.","journal-title":"Operations Research"},{"key":"6641_CR185","doi-asserted-by":"crossref","unstructured":"Ravi, R., & Salman, F.S. (1999). Approximation algorithms for the traveling purchaser problem and its variants in network design. In: European Symposium on Algorithms, pp. 29\u201340. Springer.","DOI":"10.1007\/3-540-48481-7_4"},{"issue":"4","key":"6641_CR186","doi-asserted-by":"publisher","first-page":"376","DOI":"10.1287\/ijoc.3.4.376","volume":"3","author":"G Reinelt","year":"1991","unstructured":"Reinelt, G. (1991). TSPLIB - A traveling salesman problem library. ORSA Journal on Computing, 3(4), 376\u2013384.","journal-title":"ORSA Journal on Computing"},{"issue":"1\u20132","key":"6641_CR187","doi-asserted-by":"publisher","first-page":"69","DOI":"10.1016\/S0004-3702(99)00002-8","volume":"108","author":"J Renz","year":"1999","unstructured":"Renz, J., & Nebel, B. (1999). On the complexity of qualitative spatial reasoning: A maximal tractable fragment of the region connection calculus. Artificial Intelligence, 108(1\u20132), 69\u2013123.","journal-title":"Artificial Intelligence"},{"key":"6641_CR188","unstructured":"Ridder, H. N., et al. (2025). Information\u00a0System\u00a0on\u00a0Graph\u00a0Classes\u00a0and\u00a0their\u00a0Inclusions\u00a0(ISGCI). https:\/\/www.graphclasses.org"},{"issue":"3","key":"6641_CR189","doi-asserted-by":"publisher","first-page":"532","DOI":"10.1287\/opre.14.3.532","volume":"14","author":"M Rothkopf","year":"1966","unstructured":"Rothkopf, M. (1966). The traveling salesman problem: On the reduction of certain large problems to smaller ones. Operations Research, 14(3), 532\u2013533.","journal-title":"Operations Research"},{"issue":"2","key":"6641_CR190","doi-asserted-by":"publisher","first-page":"479","DOI":"10.1016\/j.ejor.2004.04.017","volume":"165","author":"R Ruiz","year":"2005","unstructured":"Ruiz, R., & Maroto, C. (2005). A comprehensive review and evaluation of permutation flowshop heuristics. European Journal of Operational Research, 165(2), 479\u2013494.","journal-title":"European Journal of Operational Research"},{"issue":"1","key":"6641_CR191","doi-asserted-by":"publisher","first-page":"285","DOI":"10.1007\/BF02022044","volume":"4","author":"MW Savelsbergh","year":"1985","unstructured":"Savelsbergh, M. W. (1985). Local search in routing problems with time windows. Annals of Operations Research, 4(1), 285\u2013305.","journal-title":"Annals of Operations Research"},{"issue":"1","key":"6641_CR192","doi-asserted-by":"publisher","first-page":"1","DOI":"10.5267\/j.ijiec.2010.01.001","volume":"1","author":"M Sayadi","year":"2010","unstructured":"Sayadi, M., Ramezanian, R., & Ghaffari-Nasab, N. (2010). A discrete firefly meta-heuristic with local search for makespan minimization in permutation flow shop scheduling problems. Int. Journal of Industrial Engineering Computations, 1(1), 1\u201310.","journal-title":"Int. Journal of Industrial Engineering Computations"},{"key":"6641_CR193","volume-title":"Combinatorial Optimization: Polyhedra and Efficiency","author":"A Schrijver","year":"2003","unstructured":"Schrijver, A. (2003). Combinatorial Optimization: Polyhedra and Efficiency. Heidelberg: Springer."},{"key":"6641_CR194","doi-asserted-by":"crossref","unstructured":"Seb\u0151, A. (2013). Eight-fifth approximation for the path TSP. In: Proc. 16th Int. Conference on Integer Programming and Combinatorial Optimization, pp. 362\u2013374. Springer.","DOI":"10.1007\/978-3-642-36694-9_31"},{"key":"6641_CR195","doi-asserted-by":"crossref","unstructured":"Seb\u0151, A., & Van\u00a0Zuylen, A. (2016). The salesman\u2019s improved paths: A 3\/2+ 1\/34 approximation. In: 57th Annual IEEE Symposium on Foundations of Computer Science, pp. 118\u2013127. IEEE","DOI":"10.1109\/FOCS.2016.21"},{"key":"6641_CR196","doi-asserted-by":"crossref","unstructured":"Seb\u0151, A., & Vygen, J. (2014). Shorter tours by nicer ears: 7\/5-approximation for the graph-TSP, 3\/2 for the path version, and 4\/3 for two-edge-connected subgraphs. Combinatorica, 1\u201334.","DOI":"10.1007\/s00493-014-2960-3"},{"issue":"1","key":"6641_CR197","doi-asserted-by":"publisher","first-page":"38","DOI":"10.1016\/j.ejor.2004.09.057","volume":"174","author":"LV Snyder","year":"2006","unstructured":"Snyder, L. V., & Daskin, M. S. (2006). A random-key genetic algorithm for the generalized traveling salesman problem. European Journal of Operational Research, 174(1), 38\u201353.","journal-title":"European Journal of Operational Research"},{"issue":"2","key":"6641_CR198","doi-asserted-by":"publisher","first-page":"254","DOI":"10.1287\/opre.35.2.254","volume":"35","author":"MM Solomon","year":"1987","unstructured":"Solomon, M. M. (1987). Algorithms for the vehicle routing and scheduling problems with time window constraints. Operations Research, 35(2), 254\u2013265.","journal-title":"Operations Research"},{"issue":"6","key":"6641_CR199","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3424306","volume":"67","author":"O Svensson","year":"2020","unstructured":"Svensson, O., Tarnawski, J., & V\u00e9gh, L. A. (2020). A constant-factor approximation algorithm for the asymmetric traveling salesman problem. Journal of the ACM, 67(6), 1\u201353.","journal-title":"Journal of the ACM"},{"issue":"16","key":"6641_CR200","doi-asserted-by":"publisher","first-page":"621","DOI":"10.4064\/am-16-4-621-629","volume":"4","author":"MM Sys\u0142o","year":"1980","unstructured":"Sys\u0142o, M. M. (1980). Generalizations of the standard travelling salesman problem. Applicationes Mathematicae, 4(16), 621\u2013629.","journal-title":"Applicationes Mathematicae"},{"issue":"5","key":"6641_CR201","doi-asserted-by":"publisher","first-page":"503","DOI":"10.1007\/s00158-008-0347-z","volume":"39","author":"S Tosserams","year":"2009","unstructured":"Tosserams, S., Etman, L. F. P., & Rooda, J. E. (2009). A classification of methods for distributed system optimization based on formulation structure. Structural and Multidisciplinary Optimization, 39(5), 503\u2013517.","journal-title":"Structural and Multidisciplinary Optimization"},{"key":"6641_CR202","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898718515","volume-title":"The Vehicle Routing Problem","author":"P Toth","year":"2002","unstructured":"Toth, P., & Vigo, D. (2002). The Vehicle Routing Problem. Philadelphia: SIAM."},{"key":"6641_CR203","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973594","volume-title":"Vehicle Routing: Problems, Methods, and Applications","author":"P Toth","year":"2014","unstructured":"Toth, P., & Vigo, D. (2014). Vehicle Routing: Problems, Methods, and Applications (2nd ed.). Philadelphia: SIAM.","edition":"2"},{"key":"6641_CR204","unstructured":"Traub, V. (2020). Approximation algorithms for traveling salesman problems. PhD thesis, Rheinische Friedrich-Wilhelms-Universit\u00e4t Bonn."},{"key":"6641_CR205","doi-asserted-by":"crossref","unstructured":"Traub, V., & Vygen, J. (2020). An improved approximation algorithm for ATSP. In: Proc. 52nd Annual ACM SIGACT Symposium on Theory of Computing, pp. 1\u201313. ACM, New York.","DOI":"10.1145\/3357713.3384233"},{"key":"6641_CR206","doi-asserted-by":"crossref","unstructured":"Traub, V., & Vygen, J. (2020). Beating the integrality ratio for s-t-tours in graphs. SIAM Journal on Computing. Special Section FOCS 2018","DOI":"10.1109\/FOCS.2018.00078"},{"key":"6641_CR207","doi-asserted-by":"crossref","unstructured":"Traub, V., Vygen, J., & Zenklusen, R. (2020). Reducing Path TSP to TSP. In: Proc. 52nd Annual ACM SIGACT Symposium on Theory of Computing, pp. 14\u201327. ACM, New York.","DOI":"10.1145\/3357713.3384256"},{"issue":"9","key":"6641_CR208","doi-asserted-by":"publisher","first-page":"797","DOI":"10.1057\/jors.1984.162","volume":"35","author":"T Tsiligirides","year":"1984","unstructured":"Tsiligirides, T. (1984). Heuristic methods applied to orienteering. Journal of the Operational Research Society, 35(9), 797\u2013809.","journal-title":"Journal of the Operational Research Society"},{"issue":"3","key":"6641_CR209","doi-asserted-by":"publisher","first-page":"263","DOI":"10.1002\/net.3230220305","volume":"22","author":"JN Tsitsiklis","year":"1992","unstructured":"Tsitsiklis, J. N. (1992). Special cases of traveling salesman and repairman problems with time windows. Networks, 22(3), 263\u2013282.","journal-title":"Networks"},{"issue":"1","key":"6641_CR210","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.ejor.2010.03.045","volume":"209","author":"P Vansteenwegen","year":"2011","unstructured":"Vansteenwegen, P., Souffriau, W., & Van Oudheusden, D. (2011). The orienteering problem: a survey. European Journal of Operational Research, 209(1), 1\u201310.","journal-title":"European Journal of Operational Research"},{"key":"6641_CR211","volume-title":"New approximation algorithms for the TSP","author":"J Vygen","year":"2012","unstructured":"Vygen, J. (2012). New approximation algorithms for the TSP. Uni Bonn: Forschungsinst. f\u00fcr Diskrete Mathematik."},{"key":"6641_CR212","unstructured":"Web Ontology Language (OWL). (2012). https:\/\/www.w3.org\/OWL\/."},{"key":"6641_CR213","doi-asserted-by":"crossref","unstructured":"Xiao, M., Zhang, J., & Lin, W. (2020). Parameterized algorithms and complexity for the traveling purchaser problem and its variants. Journal of Combinatorial Optimization, 1\u201317.","DOI":"10.1007\/s10878-020-00608-x"},{"issue":"4","key":"6641_CR214","doi-asserted-by":"publisher","first-page":"175","DOI":"10.1002\/(SICI)1099-1425(199907\/08)2:4<175::AID-JOS24>3.0.CO;2-S","volume":"2","author":"GH Young","year":"1999","unstructured":"Young, G. H., & Chan, C.-L. (1999). Single-vehicle scheduling with time window constraints. Journal of Scheduling, 2(4), 175\u2013187.","journal-title":"Journal of Scheduling"},{"key":"6641_CR215","doi-asserted-by":"crossref","unstructured":"Zenklusen, R. (2019). A 1.5-approximation for path TSP. In: Proc. 13th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1539\u20131549. SIAM.","DOI":"10.1137\/1.9781611975482.93"}],"container-title":["Annals of Operations Research"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10479-025-06641-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10479-025-06641-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10479-025-06641-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,9,7]],"date-time":"2025-09-07T01:18:41Z","timestamp":1757207921000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10479-025-06641-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,7,1]]},"references-count":215,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2025,8]]}},"alternative-id":["6641"],"URL":"https:\/\/doi.org\/10.1007\/s10479-025-06641-5","relation":{},"ISSN":["0254-5330","1572-9338"],"issn-type":[{"type":"print","value":"0254-5330"},{"type":"electronic","value":"1572-9338"}],"subject":[],"published":{"date-parts":[[2025,7,1]]},"assertion":[{"value":"26 May 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"28 April 2025","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"1 July 2025","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"Not applicable.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflicts of Interest"}}]}}