{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,5]],"date-time":"2026-08-05T17:50:35Z","timestamp":1785952235731,"version":"3.56.0"},"reference-count":60,"publisher":"Elsevier BV","license":[{"start":{"date-parts":[[2024,10,1]],"date-time":"2024-10-01T00:00:00Z","timestamp":1727740800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/2.zoppoz.workers.dev:443\/https\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2024,10,1]],"date-time":"2024-10-01T00:00:00Z","timestamp":1727740800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/2.zoppoz.workers.dev:443\/https\/www.elsevier.com\/legal\/tdmrep-license"},{"start":{"date-parts":[[2024,8,16]],"date-time":"2024-08-16T00:00:00Z","timestamp":1723766400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/2.zoppoz.workers.dev:443\/http\/creativecommons.org\/licenses\/by-nc\/4.0\/"}],"content-domain":{"domain":["elsevier.com","sciencedirect.com"],"crossmark-restriction":true},"short-container-title":["Journal of Computational Science"],"published-print":{"date-parts":[[2024,10]]},"DOI":"10.1016\/j.jocs.2024.102424","type":"journal-article","created":{"date-parts":[[2024,8,17]],"date-time":"2024-08-17T15:59:04Z","timestamp":1723910344000},"page":"102424","update-policy":"https:\/\/2.zoppoz.workers.dev:443\/https\/doi.org\/10.1016\/elsevier_cm_policy","source":"Crossref","is-referenced-by-count":2,"special_numbering":"C","title":["Quasi-linear time heuristic to solve the Euclidean traveling salesman problem with low gap"],"prefix":"10.1016","volume":"82","author":[{"ORCID":"https:\/\/2.zoppoz.workers.dev:443\/https\/orcid.org\/0000-0002-4838-845X","authenticated-orcid":false,"given":"Arno","family":"Formella","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"78","reference":[{"key":"10.1016\/j.jocs.2024.102424_b1","series-title":"The Traveling Salesman Problem and Its Variations","year":"2007"},{"key":"10.1016\/j.jocs.2024.102424_b2","series-title":"The Traveling Salesman Problem: A Computational Study","author":"Applegate","year":"2011"},{"issue":"1","key":"10.1016\/j.jocs.2024.102424_b3","doi-asserted-by":"crossref","first-page":"113","DOI":"10.1007\/s13676-012-0010-0","article-title":"Models and algorithms for the asymmetric traveling salesman problem: an experimental comparison","volume":"1","author":"Roberti","year":"2012","journal-title":"EURO J. Transp. Logist."},{"key":"10.1016\/j.jocs.2024.102424_b4","doi-asserted-by":"crossref","first-page":"451","DOI":"10.1002\/net.21765","article-title":"Combining and projecting flow models for the (precedence constrained) asymmetric traveling salesman problem","volume":"71","author":"Gouveia","year":"2018","journal-title":"Networks"},{"issue":"2","key":"10.1016\/j.jocs.2024.102424_b5","doi-asserted-by":"crossref","first-page":"115","DOI":"10.1016\/0305-0548(75)90015-5","article-title":"The clustered traveling salesman problem","volume":"2","author":"Chisman","year":"1975","journal-title":"Comput. Oper. Res."},{"key":"10.1016\/j.jocs.2024.102424_b6","doi-asserted-by":"crossref","first-page":"363","DOI":"10.1002\/net.3230090406","article-title":"The greedy travelling salesman\u2019s problem","volume":"9","author":"Jenkyns","year":"1979","journal-title":"Networks"},{"issue":"2","key":"10.1016\/j.jocs.2024.102424_b7","doi-asserted-by":"crossref","first-page":"367","DOI":"10.1287\/opre.43.2.367","article-title":"An optimal algorithm for the traveling salesman problem with time windows","volume":"43","author":"Dumas","year":"1995","journal-title":"Oper. Res."},{"issue":"1","key":"10.1016\/j.jocs.2024.102424_b8","first-page":"19","article-title":"Exact and heuristic procedures for the traveling salesman problem with precedence constraints, based on dynamic programming","volume":"32","author":"Bianco","year":"1994","journal-title":"INFOR Inf. Syst. Oper. Res."},{"key":"10.1016\/j.jocs.2024.102424_b9","doi-asserted-by":"crossref","first-page":"56","DOI":"10.1016\/j.cor.2015.04.008","article-title":"Load-dependent and precedence-based models for pickup and delivery problems","volume":"63","author":"Gouveia","year":"2015","journal-title":"Comput. Oper. Res."},{"issue":"2","key":"10.1016\/j.jocs.2024.102424_b10","doi-asserted-by":"crossref","first-page":"488","DOI":"10.1016\/j.ejor.2023.01.039","article-title":"Precedence constrained generalized traveling salesman problem: Polyhedral study, formulations, and branch-and-cut algorithm","volume":"309","author":"Khachai","year":"2023","journal-title":"European J. Oper. Res."},{"key":"10.1016\/j.jocs.2024.102424_b11","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.cor.2017.05.010","article-title":"Glns: An effective large neighborhood search heuristic for the generalized traveling salesman problem","volume":"87","author":"Smith","year":"2017","journal-title":"Comput. Oper. Res."},{"key":"10.1016\/j.jocs.2024.102424_b12","series-title":"An Extension of the Lin-Kernighan-Helsgaun Tsp Solver for Constrained Traveling Salesman and Vehicle Routing Problems: Technical Report","author":"Helsgaun","year":"2017"},{"key":"10.1016\/j.jocs.2024.102424_b13","series-title":"Recent Advances on Soft Computing and Data Mining","first-page":"89","article-title":"A performance comparison of genetic algorithm\u2019s mutation operators in n-cities open loop travelling salesman problem","author":"Chieng","year":"2014"},{"key":"10.1016\/j.jocs.2024.102424_b14","doi-asserted-by":"crossref","first-page":"32","DOI":"10.1016\/j.cor.2019.03.006","article-title":"Efficiently solving very large-scale routing problems","volume":"107","author":"Arnold","year":"2019","journal-title":"Comput. Oper. Res."},{"issue":"1","key":"10.1016\/j.jocs.2024.102424_b15","doi-asserted-by":"crossref","first-page":"61","DOI":"10.1145\/321105.321111","article-title":"Dynamic programming treatment of the travelling salesman problem","volume":"9","author":"Bellman","year":"1962","journal-title":"J. ACM"},{"issue":"1","key":"10.1016\/j.jocs.2024.102424_b16","doi-asserted-by":"crossref","first-page":"196","DOI":"10.1137\/0110015","article-title":"A dynamic programming approach to sequencing problems","volume":"10","author":"Held","year":"1962","journal-title":"J. Soc. Ind. Appl. Math."},{"issue":"3","key":"10.1016\/j.jocs.2024.102424_b17","doi-asserted-by":"crossref","first-page":"740","DOI":"10.1137\/22M1469122","article-title":"An ETH-tight exact algorithm for euclidean TSP","volume":"52","author":"de Berg","year":"2023","journal-title":"SIAM J. Comput."},{"key":"10.1016\/j.jocs.2024.102424_b18","series-title":"Concorde TSP solver","author":"Cook","year":"2020"},{"issue":"1","key":"10.1016\/j.jocs.2024.102424_b19","doi-asserted-by":"crossref","first-page":"87","DOI":"10.1016\/j.ejor.2014.03.042","article-title":"On the empirical scaling of run-time for finding optimal solutions to the travelling salesman problem","volume":"238","author":"Hoos","year":"2014","journal-title":"European J. Oper. Res."},{"key":"10.1016\/j.jocs.2024.102424_b20","doi-asserted-by":"crossref","first-page":"51","DOI":"10.1007\/s12532-020-00184-5","article-title":"Hard to solve instances of the euclidean traveling salesman problem","volume":"13","author":"Hougardy","year":"2021","journal-title":"Math. Program. Comput."},{"key":"10.1016\/j.jocs.2024.102424_b21","series-title":"Proceedings of the 2019 Annual ACM-SIAM Symposium on Discrete Algorithms","first-page":"1783","article-title":"Quantum speedups for exponential-time dynamic programming algorithms","author":"Ambainis","year":"2019"},{"issue":"3","key":"10.1016\/j.jocs.2024.102424_b22","first-page":"537","article-title":"Approximation algorithms for the traveling salesman problem","volume":"145","author":"Monnot","year":"2002","journal-title":"Math. Models Oper. Res."},{"issue":"1","key":"10.1016\/j.jocs.2024.102424_b23","doi-asserted-by":"crossref","first-page":"20","DOI":"10.1007\/s43069-021-00101-z","article-title":"Worst-case analysis of a new heuristic for the travelling salesman problem","volume":"3","author":"Christofides","year":"2022","journal-title":"Oper. Res. Forum"},{"key":"10.1016\/j.jocs.2024.102424_b24","series-title":"Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing","first-page":"32","article-title":"A (slightly) improved approximation algorithm for metric TSP","author":"Karlin","year":"2021"},{"issue":"5","key":"10.1016\/j.jocs.2024.102424_b25","doi-asserted-by":"crossref","first-page":"753","DOI":"10.1145\/290179.290180","article-title":"Polynomial time approximation schemes for euclidean traveling salesman and other geometric problems","volume":"45","author":"Arora","year":"1998","journal-title":"J. ACM"},{"issue":"4","key":"10.1016\/j.jocs.2024.102424_b26","doi-asserted-by":"crossref","first-page":"1298","DOI":"10.1137\/S0097539796309764","article-title":"Guillotine subdivisions approximate polygonal subdivisions: A simple polynomial-time approximation scheme for geometric tsp, k-mst, and related problems","volume":"28","author":"Mitchell","year":"1999","journal-title":"SIAM J. Comput."},{"key":"10.1016\/j.jocs.2024.102424_b27","series-title":"Proceedings of the Thirtieth Annual ACM Symposium on Theory of Computing","first-page":"540","article-title":"Approximating geometrical graphs via spanners and banyans","author":"Rao","year":"1998"},{"key":"10.1016\/j.jocs.2024.102424_b28","series-title":"2021 IEEE 62nd Annual Symposium on Foundations of Computer Science","first-page":"351","article-title":"A gap-ETH-tight approximation scheme for euclidean TSP","author":"Kisfaludi-Bak","year":"2022"},{"key":"10.1016\/j.jocs.2024.102424_b29","series-title":"2013 IEEE 54th Annual Symposium on Foundations of Computer Science","first-page":"698","article-title":"A linear time approximation scheme for euclidean TSP","author":"Bartal","year":"2013"},{"issue":"4","key":"10.1016\/j.jocs.2024.102424_b30","doi-asserted-by":"crossref","first-page":"1563","DOI":"10.1137\/130913328","article-title":"The traveling salesman problem: Low-dimensionality implies a polynomial time approximation scheme","volume":"45","author":"Bartal","year":"2016","journal-title":"SIAM J. Comput."},{"issue":"1","key":"10.1016\/j.jocs.2024.102424_b31","doi-asserted-by":"crossref","first-page":"106","DOI":"10.1016\/S0377-2217(99)00284-2","article-title":"An effective implementation of the Lin-Kernighan traveling salesman heuristic","volume":"126","author":"Helsgaun","year":"2000","journal-title":"European J. Oper. Res."},{"key":"10.1016\/j.jocs.2024.102424_b32","series-title":"Using POPMUSIC for Candidate Set Generation in the Lin-Kernighan-Helsgaun TSP Solver","author":"Helsgaun","year":"2018"},{"key":"10.1016\/j.jocs.2024.102424_b33","doi-asserted-by":"crossref","first-page":"498","DOI":"10.1287\/opre.21.2.498","article-title":"An effective heuristic algorithm for the traveling-salesman problem","volume":"21","author":"Lin","year":"1973","journal-title":"Oper. Res."},{"issue":"4","key":"10.1016\/j.jocs.2024.102424_b34","doi-asserted-by":"crossref","first-page":"841","DOI":"10.1137\/21M146199X","article-title":"The approximation ratio of the k-opt heuristic for the euclidean traveling salesman problem","volume":"52","author":"Brodowsky","year":"2023","journal-title":"SIAM J. Comput."},{"issue":"3","key":"10.1016\/j.jocs.2024.102424_b35","doi-asserted-by":"crossref","first-page":"563","DOI":"10.1137\/0206041","article-title":"An analysis of several heuristics for the traveling salesman problem","volume":"6","author":"Rosenkrantz","year":"1977","journal-title":"SIAM J. Comput."},{"key":"10.1016\/j.jocs.2024.102424_b36","doi-asserted-by":"crossref","DOI":"10.1016\/j.jocs.2021.101454","article-title":"Transformation operators based grey wolf optimizer for travelling salesman problem","volume":"55","author":"Panwar","year":"2021","journal-title":"J. Comput. Sci."},{"key":"10.1016\/j.jocs.2024.102424_b37","series-title":"Evolutionary Computation in Combinatorial Optimization","first-page":"99","article-title":"Rigorous performance analysis of state-of-the-art tsp heuristic solvers","author":"McMenemy","year":"2019"},{"key":"10.1016\/j.jocs.2024.102424_b38","doi-asserted-by":"crossref","first-page":"175","DOI":"10.1007\/PL00009340","article-title":"An optimal algorithm for closest-pair maintenance","volume":"19","author":"Bespamyatnikh","year":"1998","journal-title":"Discrete Comput. Geom."},{"key":"10.1016\/j.jocs.2024.102424_b39","doi-asserted-by":"crossref","DOI":"10.1016\/j.comgeo.2022.101976","article-title":"Dynamic data structures for k-nearest neighbor queries","volume":"111","author":"de Berg","year":"2023","journal-title":"Comput. Geom."},{"key":"10.1016\/j.jocs.2024.102424_b40","series-title":"Proceedings of the 1990 ACM SIGMOD International Conference on Management of Data","first-page":"322","article-title":"The R*-tree: An efficient and robust access method for points and rectangles","author":"Beckmann","year":"1990"},{"key":"10.1016\/j.jocs.2024.102424_b41","series-title":"Boost C++ libraries","author":"B. organization","year":"2023"},{"issue":"6","key":"10.1016\/j.jocs.2024.102424_b42","doi-asserted-by":"crossref","first-page":"1138","DOI":"10.1287\/opre.18.6.1138","article-title":"The traveling-salesman problem and minimum spanning trees","volume":"18","author":"Held","year":"1970","journal-title":"Oper. Res."},{"key":"10.1016\/j.jocs.2024.102424_b43","series-title":"Proceedings of the Seventh Annual ACM-SIAM Symposium on Discrete Algorithms","first-page":"341","article-title":"Asymptotic experimental analysis for the held\u2013karp traveling salesman bound","author":"Johnson","year":"1996"},{"issue":"4","key":"10.1016\/j.jocs.2024.102424_b44","doi-asserted-by":"crossref","first-page":"376","DOI":"10.1287\/ijoc.3.4.376","article-title":"TSPLIB\u2013A traveling salesman problem library","volume":"3","author":"Reinelt","year":"1991","journal-title":"ORSA J. Comput."},{"key":"10.1016\/j.jocs.2024.102424_b45","series-title":"Traveling salesman problem","author":"Cook","year":"2023"},{"key":"10.1016\/j.jocs.2024.102424_b46","series-title":"8Th DIMACS implementation challenge: The traveling salesman problem","year":"2023"},{"key":"10.1016\/j.jocs.2024.102424_b47","series-title":"Santa claus TSP challenge","author":"Fr\u00e4nti","year":"2020"},{"key":"10.1016\/j.jocs.2024.102424_b48","doi-asserted-by":"crossref","DOI":"10.3389\/frobt.2021.689908","article-title":"Solving the large-scale TSP problem in 1h: Santa claus challenge 2020","volume":"8","author":"Mariescu-Istodor","year":"2021","journal-title":"Front. Robotics AI"},{"issue":"19","key":"10.1016\/j.jocs.2024.102424_b49","doi-asserted-by":"crossref","first-page":"1","DOI":"10.3390\/app9193985","article-title":"Which local search operator works best for the open-loop TSP?","volume":"9","author":"Sengupta","year":"2019","journal-title":"Appl. Sci."},{"issue":"1","key":"10.1016\/j.jocs.2024.102424_b50","doi-asserted-by":"crossref","DOI":"10.3390\/app11010177","article-title":"Converting MST to TSP path by branch elimination","volume":"11","author":"Fr\u00e4nti","year":"2021","journal-title":"Appl. Sci."},{"key":"10.1016\/j.jocs.2024.102424_b51","series-title":"MOPSI dots 2017","author":"Fr\u00e4nti","year":"2017"},{"issue":"4","key":"10.1016\/j.jocs.2024.102424_b52","doi-asserted-by":"crossref","first-page":"454","DOI":"10.1080\/17445760.2020.1776867","article-title":"A polynomial-time deterministic approach to the travelling salesperson problem","volume":"35","author":"Jazayeri","year":"2020","journal-title":"Int. J. Parallel Emergent Distrib. Syst."},{"issue":"3","key":"10.1016\/j.jocs.2024.102424_b53","first-page":"1505","article-title":"A distance matrix based algorithm for solving the traveling salesman problem","volume":"20","author":"Wang","year":"2020","journal-title":"Oper. Res."},{"issue":"1","key":"10.1016\/j.jocs.2024.102424_b54","first-page":"1","article-title":"Simple constructive, insertion, and improvement heuristics based on the girding polygon for the euclidean traveling salesman problem","volume":"13","author":"Pacheco-Valencia","year":"2020","journal-title":"Algorithms"},{"issue":"2","key":"10.1016\/j.jocs.2024.102424_b55","doi-asserted-by":"crossref","first-page":"442","DOI":"10.1016\/j.ejor.2021.05.034","article-title":"A linearithmic heuristic for the travelling salesman problem","volume":"297","author":"Taillard","year":"2022","journal-title":"European J. Oper. Res."},{"key":"10.1016\/j.jocs.2024.102424_b56","doi-asserted-by":"crossref","first-page":"1","DOI":"10.3389\/frobt.2021.652417","article-title":"Travelling santa problem: Optimization of a million-households tour within one hour","volume":"8","author":"Strutz","year":"2021","journal-title":"Front. Robotics AI"},{"issue":"2","key":"10.1016\/j.jocs.2024.102424_b57","doi-asserted-by":"crossref","first-page":"1","DOI":"10.3390\/a16020091","article-title":"Redesigning the wheel for systematic travelling salesmen","volume":"16","author":"Strutz","year":"2023","journal-title":"Algorithms"},{"issue":"12","key":"10.1016\/j.jocs.2024.102424_b58","doi-asserted-by":"crossref","first-page":"1","DOI":"10.3390\/app13127339","article-title":"An improvement to the 2-opt heuristic algorithm for approximation of optimal TSP tour","volume":"13","author":"Uddin","year":"2023","journal-title":"Appl. Sci."},{"issue":"4","key":"10.1016\/j.jocs.2024.102424_b59","doi-asserted-by":"crossref","first-page":"121","DOI":"10.1016\/0167-6377(82)90012-8","article-title":"An O(nlogn) planar travelling salesman heuristic based on spacefilling curves","volume":"1","author":"Bartholdi","year":"1982","journal-title":"Oper. Res. Lett."},{"key":"10.1016\/j.jocs.2024.102424_b60","series-title":"Local Search in Combinatorial Optimization","first-page":"215","article-title":"The traveling salesman problem: A case study in local optimization","author":"Johnson","year":"1997"}],"container-title":["Journal of Computational Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/2.zoppoz.workers.dev:443\/https\/api.elsevier.com\/content\/article\/PII:S1877750324002175?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/2.zoppoz.workers.dev:443\/https\/api.elsevier.com\/content\/article\/PII:S1877750324002175?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2024,9,15]],"date-time":"2024-09-15T06:23:13Z","timestamp":1726381393000},"score":1,"resource":{"primary":{"URL":"https:\/\/2.zoppoz.workers.dev:443\/https\/linkinghub.elsevier.com\/retrieve\/pii\/S1877750324002175"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,10]]},"references-count":60,"alternative-id":["S1877750324002175"],"URL":"https:\/\/2.zoppoz.workers.dev:443\/https\/doi.org\/10.1016\/j.jocs.2024.102424","relation":{},"ISSN":["1877-7503"],"issn-type":[{"value":"1877-7503","type":"print"}],"subject":[],"published":{"date-parts":[[2024,10]]},"assertion":[{"value":"Elsevier","name":"publisher","label":"This article is maintained by"},{"value":"Quasi-linear time heuristic to solve the Euclidean traveling salesman problem with low gap","name":"articletitle","label":"Article Title"},{"value":"Journal of Computational Science","name":"journaltitle","label":"Journal Title"},{"value":"https:\/\/2.zoppoz.workers.dev:443\/https\/doi.org\/10.1016\/j.jocs.2024.102424","name":"articlelink","label":"CrossRef DOI link to publisher maintained version"},{"value":"article","name":"content_type","label":"Content Type"},{"value":"\u00a9 2024 The Author(s). Published by Elsevier B.V.","name":"copyright","label":"Copyright"}],"article-number":"102424"}}