{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,4]],"date-time":"2026-05-04T14:02:42Z","timestamp":1777903362923,"version":"3.51.4"},"reference-count":37,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2021,12,2]],"date-time":"2021-12-02T00:00:00Z","timestamp":1638403200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,12,2]],"date-time":"2021-12-02T00:00:00Z","timestamp":1638403200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100011033","name":"Agencia Estatal de Investigaci\u00f3n","doi-asserted-by":"publisher","award":["RTI2018-094614-B-I00"],"award-info":[{"award-number":["RTI2018-094614-B-I00"]}],"id":[{"id":"10.13039\/501100011033","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003759","name":"Universidad Polit\u00e9cnica de Madrid","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100003759","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Cent Eur J Oper Res"],"published-print":{"date-parts":[[2022,12]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We define a geometric transformation of Euclidean Travelling Salesman Problem (TSP) tours that leads to a new formulation of the TSP. For every Euclidean TSP n-city tour, it is possible to construct an inscribed n-polygon (Equivalent Cyclic Polygon, ECP) such that the lengths of the edges are equal to the corresponding TSP tour links and follow the same sequence order. The analysis of the ECP elicits the possibility of defining a new objective function in terms of angles instead of distances. This modification opens the way to identify characterizing geometric parameters of the TSP as well as to explore new heuristics based on the inclusion of additional constraints. The experimentation with a set of cases shows promising results compared to the traditional compact formulations. The behavior of the ECP-based TSP formulations is better when the nodes of the TSP are randomly or evenly distributed.<\/jats:p>","DOI":"10.1007\/s10100-021-00784-z","type":"journal-article","created":{"date-parts":[[2021,12,2]],"date-time":"2021-12-02T15:04:48Z","timestamp":1638457488000},"page":"1427-1450","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Equivalent cyclic polygon of a euclidean travelling salesman problem tour and modified formulation"],"prefix":"10.1007","volume":"30","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-4486-6239","authenticated-orcid":false,"given":"A.","family":"Herraiz","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5192-8210","authenticated-orcid":false,"given":"M.","family":"Gutierrez","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3574-2050","authenticated-orcid":false,"given":"M.","family":"Ortega-Mier","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2021,12,2]]},"reference":[{"key":"784_CR1","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/978-3-319-05035-5","volume":"9783319050355","author":"SP Anbuudayasankar","year":"2014","unstructured":"Anbuudayasankar SP, Ganesh K, Mohapatra S (2014) Models for practical routing problems in logistics: Design and practices. Model Pract Routing Probl Logist Des Pract 9783319050355:1\u2013165. https:\/\/doi.org\/10.1007\/978-3-319-05035-5","journal-title":"Model Pract Routing Probl Logist Des Pract"},{"key":"784_CR2","volume-title":"The Traveling Salesman Problem: A Computational Study","author":"DL Applegate","year":"2006","unstructured":"Applegate DL, Bixby RE, Chv\u00e1tal V, Cook WJ (2006) The Traveling Salesman Problem: A Computational Study. Princeton Unversity, Princeton, NJ"},{"key":"784_CR3","doi-asserted-by":"publisher","DOI":"10.1109\/ICMCECS47690.2020.240847","author":"EO Asani","year":"2020","unstructured":"Asani EO, Okeyinka AE, Adebiyi AA (2020) A Construction tour technique for solving the travelling salesman problem based on convex hull and nearest neighbour heuristics. Int Conf Math Comput Eng Comput Sci ICMCECS. https:\/\/doi.org\/10.1109\/ICMCECS47690.2020.240847","journal-title":"Int Conf Math Comput Eng Comput Sci ICMCECS"},{"key":"784_CR4","volume-title":"Graph Theory 1736\u20131936","author":"NL Biggs","year":"1976","unstructured":"Biggs NL, LLoyd EK, Wilson RJ (1976) Graph Theory 1736\u20131936. Clarendon Press, Oxford"},{"key":"784_CR5","doi-asserted-by":"publisher","first-page":"445","DOI":"10.2307\/1937660","volume":"35","author":"PJ Clark","year":"1954","unstructured":"Clark PJ, Evans FC (1954) Distance to nearest neighbor as a measure of spatial relationships in populations. Ecology 35:445\u2013453. https:\/\/doi.org\/10.2307\/1937660","journal-title":"Ecology"},{"key":"784_CR6","doi-asserted-by":"publisher","first-page":"393","DOI":"10.1287\/opre.2.4.393","volume":"2","author":"GB Dantzig","year":"1954","unstructured":"Dantzig GB, Fulkerson DR, Johnson SM (1954) Solution of a large-scale traveling-salesman problem. Oper Res 2:393\u2013410. https:\/\/doi.org\/10.1287\/opre.2.4.393","journal-title":"Oper Res"},{"issue":"1","key":"784_CR7","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 (1991) Improvements and extensions to the Miller-Tucker-Zemlin subtour elimination constraints. Op Res Lett 10(1):27\u201336. https:\/\/doi.org\/10.1016\/0167-6377(91)90083-2","journal-title":"Op Res Lett"},{"key":"784_CR8","doi-asserted-by":"publisher","first-page":"1","DOI":"10.7771\/1932-\u200c6246.1117","volume":"4","author":"M Dry","year":"2012","unstructured":"Dry M, Preiss K, Wagemans J (2012) Clustering, randomness, and regularity: spatial distributions and human performance on the traveling salesperson problem and minimum spanning tree problem. J Problem Solving 4:1\u201317. https:\/\/doi.org\/10.7771\/1932-\u200c6246.1117","journal-title":"J Problem Solving"},{"key":"784_CR9","doi-asserted-by":"publisher","unstructured":"Dubois-Lacoste J, Hoos HH, St\u00fctzle T (2015) On the empirical scaling behaviour of state-of-the-art local search algorithms for the euclidean TSP. GECCO 2015 - Proc 2015 Genet Evol Comput Conf 377\u2013384. https:\/\/doi.org\/10.1145\/2739480.2754747","DOI":"10.1145\/2739480.2754747"},{"key":"784_CR10","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-61568-9","volume-title":"Algorithms in Combinatorial Geometry","author":"H Edelsbrunner","year":"1987","unstructured":"Edelsbrunner H (1987) Algorithms in Combinatorial Geometry. Springer, Berlin Heidelberg"},{"key":"784_CR11","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-05957-0","volume-title":"A Short Course in Computational Geometry and Topology","author":"H Edelsbrunner","year":"2014","unstructured":"Edelsbrunner H (2014) A Short Course in Computational Geometry and Topology. Springer International Publishing, Cham"},{"issue":"4","key":"784_CR12","doi-asserted-by":"publisher","first-page":"1018","DOI":"10.1287\/\u200copre.28.4.1018","volume":"28","author":"KR Fox","year":"1980","unstructured":"Fox KR, Gavish B, Graves SC (1980) An n-constraint formulation of the (time-dependent) traveling salesman problem. Oper Res 28(4):1018\u20131021. https:\/\/doi.org\/10.1287\/\u200copre.28.4.1018","journal-title":"Oper Res"},{"key":"784_CR13","unstructured":"Gavish B, Graves SC (1978) The travelling salesman problem and related problems. Operations Research Center Working Paper OR 078\u201378. http:\/\/hdl.handle.net\/1721.1\/5363"},{"issue":"1\u20133","key":"784_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 JM (2001) The asymmetric travelling salesman problem: on generalizations of disaggregated Miller\u2013Tucker\u2013Zemlin constraints. Discret Appl Math 112(1\u20133):129\u2013145. https:\/\/doi.org\/10.1016\/S0166-218X(00)00313-9","journal-title":"Discret Appl Math"},{"key":"784_CR15","unstructured":"Gurobi Op (2021a) Gurobi optimizer reference Manual. www.gurobi.com. Accessed 30 Jul 2021"},{"key":"784_CR16","unstructured":"Gurobi Op (2021b) MIPGap. https:\/\/www.gurobi.com\/documentation\/9.1\/refman\/mipgap2.html. Accessed 30 Jul 2021"},{"key":"784_CR17","doi-asserted-by":"crossref","unstructured":"Hart WE, Carl DL, Watson JP, Woodruff DL, Hackebeil GA, Nicholson BL, Siirola JD (2017) Pyomo \u2013 Optimization modeling in python. Second Edition. Vol. 67. Springer, 2017.","DOI":"10.1007\/978-3-319-58821-6"},{"key":"784_CR18","first-page":"225","volume-title":"Network models handbooks in operations research and management science","author":"M Junger","year":"1995","unstructured":"Junger M, Reinelt G, Rinaldi G (1995) The traveling salesman problem. In: Ball MO, Magnanti TL, Monma CL, Nemhauser GL (eds) Network models handbooks in operations research and management science, vol 7. North-Holland, Amsterdam, pp 225\u2013330"},{"key":"784_CR19","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. Oper Res Lett 9:127\u2013132","journal-title":"Oper Res Lett"},{"issue":"2","key":"784_CR20","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. Eur J Oper Res 59(2):231\u2013247. https:\/\/doi.org\/10.1016\/0377-2217(92)90138-Y","journal-title":"Eur J Oper Res"},{"key":"784_CR21","volume-title":"The traveling salesman problem. A guided tour of combinatorial optimization","year":"1991","unstructured":"Lawler EL, Lenstra JK, Rinnooy Kan AHG, Shmoys DB (eds) (1991) The traveling salesman problem. A guided tour of combinatorial optimization. John Wiley and Sons, Chichester"},{"issue":"4","key":"784_CR22","doi-asserted-by":"publisher","first-page":"717","DOI":"10.1057\/jors.1975.151","volume":"26","author":"JK Lenstra","year":"1975","unstructured":"Lenstra JK, Kan AHGR (1975) Some simple applications of the travelling salesman problem. J Oper Res Soc 26(4):717\u2013733","journal-title":"J Oper Res Soc"},{"key":"784_CR23","doi-asserted-by":"publisher","first-page":"80","DOI":"10.1007\/3-540-45471-3_9","volume":"2368","author":"C Levcopoulos","year":"2002","unstructured":"Levcopoulos C, Lingas A, Mitchell JSB (2002) Adaptive algorithms for constructing convex hulls and triangulations of polygonal chains. Lect Notes Comput Sci 2368:80\u201389. https:\/\/doi.org\/10.1007\/3-540-45471-3_9","journal-title":"Lect Notes Comput Sci"},{"key":"784_CR24","doi-asserted-by":"publisher","first-page":"22","DOI":"10.2307\/3617929","volume":"65","author":"DS Macnab","year":"1981","unstructured":"Macnab DS (1981) Cyclic polygons and related questions. Math Gaz 65:22\u201328. https:\/\/doi.org\/10.2307\/3617929","journal-title":"Math Gaz"},{"key":"784_CR25","doi-asserted-by":"publisher","first-page":"326","DOI":"10.1145\/321043.321046","volume":"7","author":"CE Miller","year":"1960","unstructured":"Miller CE, Tucker AW, Zemlin RA (1960) Integer programming formulations and traveling salesman problems. J Assoc Comput Mach 7:326\u2013329. https:\/\/doi.org\/10.1145\/321043.321046","journal-title":"J Assoc Comput Mach"},{"issue":"11","key":"784_CR26","doi-asserted-by":"publisher","first-page":"1208","DOI":"10.1287\/mnsc.23.11.1208","volume":"23","author":"JP Norback","year":"1977","unstructured":"Norback JP, Love RF (1977) Geometric approaches to solving the traveling salesman problem. Manage Sci 23(11):1208\u20131223. https:\/\/doi.org\/10.1287\/mnsc.23.11.1208","journal-title":"Manage Sci"},{"issue":"3","key":"784_CR27","doi-asserted-by":"publisher","first-page":"637","DOI":"10.1016\/j.cor.2007.11.008","volume":"36","author":"T \u00d6ncan","year":"2009","unstructured":"\u00d6ncan T, Alt\u0131nel \u0130K, Laporte G (2009) A comparative analysis of several asymmetric traveling salesman problem formulations. Comput Oper Res 36(3):637\u2013654. https:\/\/doi.org\/10.1016\/j.cor.2007.11.008","journal-title":"Comput Oper Res"},{"key":"784_CR28","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-36626-1_5","author":"AJ Orman","year":"2007","unstructured":"Orman AJ, Williams HP (2007) A Survey of Different Integer Programming Formulations of the Travelling Salesman Problem. Optim Econ Financ Anal Adv Comput Manage Sci. https:\/\/doi.org\/10.1007\/3-540-36626-1_5","journal-title":"Optim Econ Financ Anal Adv Comput Manage Sci"},{"issue":"52","key":"784_CR29","doi-asserted-by":"publisher","first-page":"315","DOI":"10.1007\/BF01582894","volume":"521","author":"M Padberg","year":"1991","unstructured":"Padberg M, Sung TY (1991) An analytical comparison of different formulations of the travelling salesman problem. Math Program 521(52):315\u2013357. https:\/\/doi.org\/10.1007\/BF01582894","journal-title":"Math Program"},{"key":"784_CR30","doi-asserted-by":"publisher","first-page":"120","DOI":"10.1134\/S1064562412010401","volume":"85","author":"GY Panina","year":"2012","unstructured":"Panina GY, Khimshiashvili GN (2012) On the area of a polygonal linkage. Dokl Math 85:120\u2013121. https:\/\/doi.org\/10.1134\/S1064562412010401","journal-title":"Dokl Math"},{"key":"784_CR31","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1016\/0304-3975(77)90012-3","volume":"4","author":"CH Papadimitriou","year":"1977","unstructured":"Papadimitriou CH (1977) The Euclidean travelling salesman problem is NP-complete. Theor Comput Sci 4:237\u2013244. https:\/\/doi.org\/10.1016\/0304-3975(77)90012-3","journal-title":"Theor Comput Sci"},{"issue":"82","key":"784_CR32","doi-asserted-by":"publisher","first-page":"156","DOI":"10.1007\/S00022-005-1752-8","volume":"821","author":"I Pinelis","year":"2005","unstructured":"Pinelis I (2005) Cyclic polygons with given edge lengths: Existence and uniqueness. J Geom 821(82):156\u2013171. https:\/\/doi.org\/10.1007\/S00022-005-1752-8","journal-title":"J Geom"},{"key":"784_CR34","unstructured":"R Core Team (2020). R: A language and environment for statistical computing. R Foundation for Statistical Computing, Vienna, Austria.URL https:\/\/www.R-project.org\/."},{"key":"784_CR33","first-page":"423","volume":"8","author":"V Raman","year":"2017","unstructured":"Raman V, Gill NS (2017) Review of different heuristic algorithms for solving Travelling Salesman Problem. Int J Adv Res Comput Sci 8:423\u2013425","journal-title":"Int J Adv Res Comput Sci"},{"key":"784_CR35","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 \u2013 A traveling salesman problem library. ORSA J Comp 3:376\u2013384. https:\/\/doi.org\/10.1287\/ijoc.3.4.376","journal-title":"ORSA J Comp"},{"key":"784_CR36","volume-title":"The traveling salesman: Computational solutions for TSP applications","author":"G Reinelt","year":"1994","unstructured":"Reinelt G (1994) The traveling salesman: Computational solutions for TSP applications. Springer, Berlin Heidelberg"},{"key":"784_CR37","doi-asserted-by":"publisher","first-page":"563","DOI":"10.1137\/0206041","volume":"6","author":"DJ Rosenkrantz","year":"1977","unstructured":"Rosenkrantz DJ, Stearns RE, Lewis PM II (1977) An analysis of several heuristics for the traveling salesman problem. SIAM J Comput 6:563\u2013581. https:\/\/doi.org\/10.1137\/0206041","journal-title":"SIAM J Comput"}],"container-title":["Central European Journal of Operations Research"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10100-021-00784-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10100-021-00784-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10100-021-00784-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,10,17]],"date-time":"2022-10-17T17:16:03Z","timestamp":1666026963000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10100-021-00784-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,12,2]]},"references-count":37,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2022,12]]}},"alternative-id":["784"],"URL":"https:\/\/doi.org\/10.1007\/s10100-021-00784-z","relation":{},"ISSN":["1435-246X","1613-9178"],"issn-type":[{"value":"1435-246X","type":"print"},{"value":"1613-9178","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,12,2]]},"assertion":[{"value":"2 October 2021","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"2 December 2021","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}