{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,16]],"date-time":"2026-06-16T12:56:36Z","timestamp":1781614596438,"version":"3.54.5"},"reference-count":23,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2025,10,23]],"date-time":"2025-10-23T00:00:00Z","timestamp":1761177600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2025,10,23]],"date-time":"2025-10-23T00:00:00Z","timestamp":1761177600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Optim Lett"],"published-print":{"date-parts":[[2026,3]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>In the Asymmetric Traveling Salesman Problem (ATSP), an interesting research question is to evaluate the maximum ratio between the cost of a route and the cost of the same route traversed in the opposite direction. This provides a worst-case measure of the tour length asymmetry. Selecting the best between the two routes can be advantageous not only from a theoretical standpoint but also in practical settings: particularly in the presence of factors such as elevation changes, traffic patterns, or operational constraints. We carry out a worst-case analysis to provide the value of the maximum ratio on all instances of the problem, when the classical, the sharpened, and the relaxed triangle inequalities hold. Computational results on benchmark instances show that the value of the ratio is significantly smaller than the worst case bound, on average. Nonetheless, it is still large enough to justify considering both directions of a tour, as selecting the better of the two can lead to a substantially shorter total tour length.<\/jats:p>","DOI":"10.1007\/s11590-025-02242-0","type":"journal-article","created":{"date-parts":[[2025,10,23]],"date-time":"2025-10-23T04:37:59Z","timestamp":1761194279000},"page":"411-425","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Some worst-case results related to the asymmetric traveling salesman problem"],"prefix":"10.1007","volume":"20","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-0227-9135","authenticated-orcid":false,"given":"Luca","family":"Bertazzi","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5270-6094","authenticated-orcid":false,"given":"Bruce","family":"Golden","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2146-8318","authenticated-orcid":false,"given":"Shuhan","family":"Kou","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2025,10,23]]},"reference":[{"issue":"2","key":"2242_CR1","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1002\/net.1024","volume":"38","author":"T Andreae","year":"2001","unstructured":"Andreae, T.: On the traveling salesman problem restricted to inputs satisfying a relaxed triangle inequality. Networks 38(2), 59\u201367 (2001)","journal-title":"Networks"},{"issue":"3","key":"2242_CR2","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1016\/S0020-0190(00)00089-2","volume":"75","author":"H-J B\u00f6ckenhauer","year":"2000","unstructured":"B\u00f6ckenhauer, H.-J., Hromkovi\u010d, J., Klasing, R., Seibert, S., Unger, W.: Approximation algorithms for the TSP with sharpened triangle inequality. Inf. Process. Lett. 75(3), 133\u2013138 (2000)","journal-title":"Inf. Process. Lett."},{"issue":"1","key":"2242_CR3","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1137\/0605004","volume":"5","author":"A Claus","year":"1984","unstructured":"Claus, A.: A new formulation for the travelling salesman problem. SIAM J. Algebr. Discr. Methods 5(1), 21\u201325 (1984)","journal-title":"SIAM J. Algebr. Discr. Methods"},{"issue":"4","key":"2242_CR4","first-page":"393","volume":"2","author":"G Dantzig","year":"1954","unstructured":"Dantzig, G., Fulkerson, R., Johnson, S.: Solution of a large-scale traveling-salesman problem. J. Oper. Res. Soc. Am. 2(4), 393\u2013410 (1954)","journal-title":"J. Oper. Res. Soc. Am."},{"issue":"1","key":"2242_CR5","doi-asserted-by":"publisher","first-page":"27","DOI":"10.1016\/0167-6377(91)90083-2","volume":"10","author":"M Desrochers","year":"1991","unstructured":"Desrochers, M., Laporte, G.: Improvements and extensions to the Miller-Tucker-Zemlin subtour elimination constraints. Oper. Res. Lett. 10(1), 27\u201336 (1991)","journal-title":"Oper. Res. Lett."},{"issue":"4","key":"2242_CR6","doi-asserted-by":"publisher","first-page":"1047","DOI":"10.1016\/j.cor.2012.10.013","volume":"40","author":"B Dussault","year":"2013","unstructured":"Dussault, B., Golden, B., Gro\u00ebr, C., Wasil, E.: Plowing with precedence: A variant of the windy postman problem. Comput. Operat. Res. 40(4), 1047\u20131059 (2013)","journal-title":"Comput. Operat. Res."},{"issue":"10","key":"2242_CR7","doi-asserted-by":"publisher","first-page":"1465","DOI":"10.1057\/jors.2013.83","volume":"65","author":"B Dussault","year":"2014","unstructured":"Dussault, B., Golden, B., Wasil, E.: The downhill plow problem with multiple plows. J. Operat. Res. Soci. 65(10), 1465\u20131474 (2014)","journal-title":"J. Operat. Res. Soci."},{"key":"2242_CR8","doi-asserted-by":"crossref","unstructured":"Fischetti, M., Lodi, A., Toth, P.: Solving real-world ATSP instances by branch-and-cut. In Lecture Notes in Computer Science 2570 Combinatorial Optimization\u2014Eureka, You Shrink!, pp. 64\u201377. Springer (2003)","DOI":"10.1007\/3-540-36478-1_8"},{"issue":"4","key":"2242_CR9","doi-asserted-by":"publisher","first-page":"1018","DOI":"10.1287\/opre.28.4.1018","volume":"28","author":"K Fox","year":"1980","unstructured":"Fox, K., Gavish, B., Graves, S.: An n-constraint formulation of the (time-dependent) traveling salesman problem. Oper. Res. 28(4), 1018\u20131021 (1980)","journal-title":"Oper. Res."},{"issue":"1","key":"2242_CR10","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1002\/net.3230120103","volume":"12","author":"AM Frieze","year":"1982","unstructured":"Frieze, A.M., Galbiati, G., Maffioli, F.: On the worst-case performance of some algorithms for the asymmetric traveling salesman problem. Networks 12(1), 23\u201339 (1982)","journal-title":"Networks"},{"key":"2242_CR11","unstructured":"Gavish, B., Graves, S.: The travelling salesman problem and related problems. Working paper GR-078-78, Operations Research Center, Massachusetts Institute of Technology, Cambridge (1978)"},{"key":"2242_CR12","unstructured":"Godinho, M., Gouveia, L., Pesneau, P.: On a time-dependent formulation and an updated classification of ATSP formulations. Progress in Combinatorial optimization (2011)"},{"issue":"1","key":"2242_CR13","doi-asserted-by":"publisher","first-page":"134","DOI":"10.1016\/S0377-2217(97)00358-5","volume":"112","author":"L Gouveia","year":"1999","unstructured":"Gouveia, L., Pires, J.: The asymmetric travelling salesman problem and a reformulation of the Miller-Tucker-Zemlin constraints. Eur. J. Oper. Res. 112(1), 134\u2013146 (1999)","journal-title":"Eur. J. Oper. Res."},{"issue":"1\u20133","key":"2242_CR14","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1016\/S0166-218X(00)00313-9","volume":"112","author":"L Gouveia","year":"2001","unstructured":"Gouveia, L., Pires, J.: The asymmetric travelling salesman problem: on generalizations of disaggregated Miller-Tucker-Zemlin constraints. Discret. Appl. Math. 112(1\u20133), 129\u2013145 (2001)","journal-title":"Discret. Appl. Math."},{"key":"2242_CR15","unstructured":"Helsgaun, K.: An extension of the Lin-Kernighan-Helsgaun TSP solver for constrained traveling salesman and vehicle routing problems. Roskilde: Roskilde University, 12:966\u2013980 (2017)"},{"key":"2242_CR16","doi-asserted-by":"crossref","unstructured":"Johnson, D., Gutin, G., McGeoch, L., Yeo, A., Zhang, W., Zverovitch, A.: Experimental analysis of heuristics for the ATSP. The traveling salesman problem and its variations, pages 445\u2013487 (2007)","DOI":"10.1007\/0-306-48213-4_10"},{"issue":"4","key":"2242_CR17","doi-asserted-by":"publisher","first-page":"326","DOI":"10.1145\/321043.321046","volume":"7","author":"C Miller","year":"1960","unstructured":"Miller, C., Tucker, A., Zemlin, R.: Integer programming formulation of traveling salesman problems. J. ACM (JACM) 7(4), 326\u2013329 (1960)","journal-title":"J. ACM (JACM)"},{"issue":"1","key":"2242_CR18","doi-asserted-by":"publisher","first-page":"255","DOI":"10.1016\/S0377-2217(02)00794-4","volume":"153","author":"G Righini","year":"2004","unstructured":"Righini, G., Trubian, M.: A note on the approximation of the asymmetric traveling salesman problem. Eur. J. Oper. Res. 153(1), 255\u2013265 (2004)","journal-title":"Eur. J. Oper. Res."},{"issue":"1\u20132","key":"2242_CR19","doi-asserted-by":"publisher","first-page":"113","DOI":"10.1007\/s13676-012-0010-0","volume":"1","author":"R Roberti","year":"2012","unstructured":"Roberti, R., Toth, P.: Models and algorithms for the asymmetric traveling salesman problem: an experimental comparison. EURO J. Transport. Logist. 1(1\u20132), 113\u2013133 (2012)","journal-title":"EURO J. Transport. Logist."},{"issue":"1","key":"2242_CR20","doi-asserted-by":"publisher","first-page":"62","DOI":"10.1016\/j.orl.2004.03.007","volume":"33","author":"S Sarin","year":"2005","unstructured":"Sarin, S., Sherali, H., Bhootra, A.: New tighter polynomial length formulations for the asymmetric traveling salesman problem with and without precedence constraints. Oper. Res. Lett. 33(1), 62\u201370 (2005)","journal-title":"Oper. Res. Lett."},{"issue":"4","key":"2242_CR21","doi-asserted-by":"publisher","first-page":"656","DOI":"10.1287\/opre.50.4.656.2865","volume":"50","author":"H Sherali","year":"2002","unstructured":"Sherali, H., Driscoll, P.: On tightening the relaxations of Miller-Tucker-Zemlin formulations for asymmetric traveling salesman problems. Oper. Res. 50(4), 656\u2013669 (2002)","journal-title":"Oper. Res."},{"issue":"1","key":"2242_CR22","doi-asserted-by":"publisher","first-page":"20","DOI":"10.1016\/j.disopt.2005.10.004","volume":"3","author":"H Sherali","year":"2006","unstructured":"Sherali, H., Sarin, S., Tsai, P.-F.: A class of lifted path and flow-based formulations for the asymmetric traveling salesman problem with and without precedence constraints. Discret. Optim. 3(1), 20\u201332 (2006)","journal-title":"Discret. Optim."},{"key":"2242_CR23","unstructured":"Wong, R.: Integer programming formulations of the traveling salesman problem. In Proceedings of the IEEE international conference of circuits and computers, volume 149, pp. 152. IEEE Press Piscataway NJ (1980)"}],"container-title":["Optimization Letters"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11590-025-02242-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s11590-025-02242-0","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11590-025-02242-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,6,16]],"date-time":"2026-06-16T12:15:12Z","timestamp":1781612112000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s11590-025-02242-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,10,23]]},"references-count":23,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2026,3]]}},"alternative-id":["2242"],"URL":"https:\/\/doi.org\/10.1007\/s11590-025-02242-0","relation":{},"ISSN":["1862-4472","1862-4480"],"issn-type":[{"value":"1862-4472","type":"print"},{"value":"1862-4480","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,10,23]]},"assertion":[{"value":"7 October 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"18 August 2025","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"23 October 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":"The authors declare that they have no conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}