{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,18]],"date-time":"2026-08-18T04:28:37Z","timestamp":1787027317547,"version":"build-2736575974"},"reference-count":23,"publisher":"Frontiers Media SA","license":[{"start":{"date-parts":[[2021,4,12]],"date-time":"2021-04-12T00:00:00Z","timestamp":1618185600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/2.zoppoz.workers.dev:443\/https\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":["frontiersin.org"],"crossmark-restriction":true},"short-container-title":["Front. Robot. AI"],"abstract":"<jats:p>Finding the shortest tour visiting all given points at least ones belongs to the most famous optimization problems until today [travelling salesman problem (TSP)]. Optimal solutions exist for many problems up to several ten thousand points. The major difficulty in solving larger problems is the required computational complexity. This shifts the research from finding the optimum with no time limitation to approaches that find good but sub-optimal solutions in pre-defined limited time. This paper proposes a new approach for two-dimensional symmetric problems with more than a million coordinates that is able to create good initial tours within few minutes. It is based on a hierarchical clustering strategy and supports parallel processing. In addition, a method is proposed that can correct unfavorable paths with moderate computational complexity. The new approach is superior to state-of-the-art methods when applied to TSP instances with non-uniformly distributed coordinates.<\/jats:p>","DOI":"10.3389\/frobt.2021.652417","type":"journal-article","created":{"date-parts":[[2021,4,12]],"date-time":"2021-04-12T03:24:12Z","timestamp":1618197852000},"update-policy":"https:\/\/2.zoppoz.workers.dev:443\/https\/doi.org\/10.3389\/crossmark-policy","source":"Crossref","is-referenced-by-count":9,"title":["Travelling Santa Problem: Optimization of a Million-Households Tour Within One Hour"],"prefix":"10.3389","volume":"8","author":[{"given":"Tilo","family":"Strutz","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"1965","published-online":{"date-parts":[[2021,4,12]]},"reference":[{"key":"B1","doi-asserted-by":"publisher","first-page":"82","DOI":"10.1287\/ijoc.15.1.82.15157","article-title":"Chained Lin-Kernigham for large traveling salesman problems","volume":"15","author":"Applegate","year":"2003","journal-title":"INFORMS J. Comput"},{"key":"B2","doi-asserted-by":"crossref","DOI":"10.1515\/9781400841103","volume-title":"The Traveling Salesman Problem: A Computational Study","author":"Applegate","year":"2007"},{"key":"B3","first-page":"2","article-title":"Polynomial-time approximation schemes for Euclidean TSP and other geometric problems,","volume-title":"Proceedings of the 37th Annual IEEE Symposium on Foundations of Computer Science","author":"Arora","year":"1996"},{"key":"B4","first-page":"1412","article-title":"Improved filtering for the Euclidean traveling salesperson problem in CLP(FD),","volume-title":"Proceedings of the Thirty-Fourth AAAI Conference on Artificial Intelligence (AAAI-20)","author":"Bertagnon","year":"2020"},{"key":"B5","doi-asserted-by":"publisher","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":"B6","volume-title":"Worst-Case Analysis of a New Heuristic for the Travelling Salesman Problem","author":"Christofides","year":"1976"},{"key":"B7","doi-asserted-by":"publisher","first-page":"791","DOI":"10.1287\/opre.6.6.791","article-title":"A method for solving traveling-salesman problems","volume":"5","author":"Croes","year":"1958","journal-title":"Oper. Res"},{"key":"B8","doi-asserted-by":"publisher","first-page":"119","DOI":"10.1007\/s12532-009-0004-6","article-title":"General k-opt submoves for the Lin-Kernighan TSP heuristic","volume":"1","author":"Helsgaun","year":"2009","journal-title":"Math. Prog. Comput"},{"key":"B9","doi-asserted-by":"publisher","first-page":"269","DOI":"10.1007\/s12532-015-0080-8","article-title":"Solving the equality generalized traveling salesman problem using the Lin-Kernighan-Helsgaun algorithm","volume":"7","author":"Helsgaun","year":"2015","journal-title":"Math. Prog. Comput"},{"key":"B10","unstructured":"HelsgaunK. Lkh-3 Version 3.0.6 (May 2019)2017"},{"key":"B11","first-page":"935","article-title":"Introducing a clustering technique into recurrent neural networks for solving large-scale traveling salesman problems,","volume-title":"Proceedings of the 8th International Conference on Artificial Neural Networks (ICANN1998)","author":"Kobayashi","year":"1998"},{"key":"B12","doi-asserted-by":"publisher","first-page":"2245","DOI":"10.1002\/j.1538-7305.1965.tb04146.x","article-title":"Computer solutions of the traveling- salesman problem","volume":"44","author":"Lin","year":"1965","journal-title":"Bell Syst. Tech. J"},{"key":"B13","doi-asserted-by":"publisher","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"},{"key":"B14","doi-asserted-by":"publisher","first-page":"219","DOI":"10.1016\/0167-6377(92)90028-2","article-title":"Large-step Markov chains for the TSP incorporating local search heuristics","volume":"11","author":"Martin","year":"1992","journal-title":"Oper. Res. Lett"},{"key":"B15","doi-asserted-by":"publisher","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":"B16","doi-asserted-by":"publisher","first-page":"827","DOI":"10.1016\/S0893-6080(03)00130-8","article-title":"Million city traveling salesman problem solution by divide and conquer clustering with adaptive resonance neural networks","volume":"16","author":"Muldera","year":"2003","journal-title":"Neural Netw"},{"key":"B17","doi-asserted-by":"publisher","first-page":"3985","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"},{"key":"B18","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-658-11456-5","volume-title":"Data Fitting and Uncertainty","author":"Strutz","year":"2016"},{"key":"B19","unstructured":"StrutzT. DoLoWire Source Code and TSP Instances2021"},{"key":"B20","doi-asserted-by":"publisher","first-page":"420","DOI":"10.1016\/j.ejor.2018.06.039","article-title":"POPMUSIC for the travelling salesman problem","volume":"272","author":"Taillard","year":"2019","journal-title":"Eur. J. Oper. Res"},{"key":"B21","article-title":"An n log n heuristic for the TSP,","volume-title":"Metaheuristic International Conference (MIC'19) Proceedings","author":"Taillard","year":"2019"},{"key":"B22","unstructured":"VLSI Data Sets2020"},{"key":"B23","doi-asserted-by":"publisher","first-page":"118","DOI":"10.1016\/j.hm.2020.04.003","article-title":"A historical note on the 3\/2-approximation algorithm for the metric traveling salesman problem","volume":"53","author":"van Bevern","year":"2020","journal-title":"Hist. Math"}],"container-title":["Frontiers in Robotics and AI"],"original-title":[],"link":[{"URL":"https:\/\/2.zoppoz.workers.dev:443\/https\/www.frontiersin.org\/articles\/10.3389\/frobt.2021.652417\/full","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,5,1]],"date-time":"2021-05-01T11:59:44Z","timestamp":1619870384000},"score":1,"resource":{"primary":{"URL":"https:\/\/2.zoppoz.workers.dev:443\/https\/www.frontiersin.org\/articles\/10.3389\/frobt.2021.652417\/full"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,4,12]]},"references-count":23,"alternative-id":["10.3389\/frobt.2021.652417"],"URL":"https:\/\/2.zoppoz.workers.dev:443\/https\/doi.org\/10.3389\/frobt.2021.652417","relation":{},"ISSN":["2296-9144"],"issn-type":[{"value":"2296-9144","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,4,12]]},"article-number":"652417"}}