{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,3]],"date-time":"2026-03-03T05:19:36Z","timestamp":1772515176012,"version":"3.50.1"},"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]]},"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":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5270-6094","authenticated-orcid":false,"given":"Bruce","family":"Golden","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2146-8318","authenticated-orcid":false,"given":"Shuhan","family":"Kou","sequence":"additional","affiliation":[]}],"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,3,3]],"date-time":"2026-03-03T04:00:57Z","timestamp":1772510457000},"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"}}]}}