{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,30]],"date-time":"2025-10-30T07:16:25Z","timestamp":1761808585672,"version":"build-2065373602"},"reference-count":60,"publisher":"MDPI AG","issue":"2","license":[{"start":{"date-parts":[[2023,2,7]],"date-time":"2023-02-07T00:00:00Z","timestamp":1675728000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>This paper investigates the systematic and complete usage of k-opt permutations with k=2\u20266 in application to local optimization of symmetric two-dimensional instances up to 107 points. The proposed method utilizes several techniques for accelerating the processing, such that good tours can be achieved in limited time: candidates selection based on Delaunay triangulation, precomputation of a sparse distance matrix, two-level data structure, and parallel processing based on multithreading. The proposed approach finds good tours (excess of 0.72\u20138.68% over best-known tour) in a single run within 30 min for instances with more than 105 points and specifically 3.37% for the largest examined tour containing 107 points. The new method proves to be competitive with a state-of-the-art approach based on the Lin\u2013Kernigham\u2013Helsgaun method (LKH) when applied to clustered instances.<\/jats:p>","DOI":"10.3390\/a16020091","type":"journal-article","created":{"date-parts":[[2023,2,8]],"date-time":"2023-02-08T05:37:31Z","timestamp":1675834651000},"page":"91","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Redesigning the Wheel for Systematic Travelling Salesmen"],"prefix":"10.3390","volume":"16","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-5063-6515","authenticated-orcid":false,"given":"Tilo","family":"Strutz","sequence":"first","affiliation":[{"name":"Department of Electrical Engineering and Computer <tt>Sc<\/tt>ience, Coburg University, 96450 Coburg, Germany"}]}],"member":"1968","published-online":{"date-parts":[[2023,2,7]]},"reference":[{"key":"ref_1","unstructured":"(1832). Der Handlungsreisende wie er Seyn Soll und Was er zu Thun Hat, um Auftr\u00e4ge zu Erhalten und Eines Gl\u00fccklichen Erfolgs in Seinen Gesch\u00e4ften Gewi\u00df zu Seyn, Voigt."},{"key":"ref_2","unstructured":"Dierker, E., and Siegmund, K. (1998). Ergebnisse Eines Mathematischen Kolloquiums, Springer."},{"key":"ref_3","unstructured":"Applegate, D.L., Bixby, R.E., Chv\u00e1tal, V., and Cook, W.J. (2007). The Traveling Salesman Problem: A Computational Study, Princeton University Press."},{"key":"ref_4","doi-asserted-by":"crossref","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":"ref_5","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":"ref_6","doi-asserted-by":"crossref","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. Program. Comput."},{"key":"ref_7","unstructured":"Christofides, N. (1976). Worst-Case Analysis of a New Heuristic for the Travelling Salesman Problem, Graduate School of Industrial Administration, Carnegie-Mellon University. Technical Report 388."},{"key":"ref_8","doi-asserted-by":"crossref","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":"Slugina","year":"2020","journal-title":"Hist. Math."},{"key":"ref_9","unstructured":"Arora, S. (1996, January 14\u201316). Polynomial-time approximation schemes for Euclidean TSP and other geometric problems. Proceedings of the 37th Annual IEEE Symposium on Foundations of Computer Science, Burlington, VT, USA."},{"key":"ref_10","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":"ref_11","unstructured":"Gutin, G., and Punnen, A.P. (2002). Traveling Salesman Problem and Its Variations, Springer."},{"key":"ref_12","doi-asserted-by":"crossref","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":"ref_13","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."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"511","DOI":"10.1057\/jors.1972.79","article-title":"Algorithms for Large-scale Travelling Salesman Problems","volume":"23","author":"Christofides","year":"1972","journal-title":"J. Oper. Res. Soc."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"35","DOI":"10.1057\/jors.2009.76","article-title":"A concise guide to the Traveling Salesman Problem","volume":"61","author":"Laporte","year":"2010","journal-title":"J. Oper. Res. Soc."},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"209","DOI":"10.1016\/j.omega.2004.10.004","article-title":"The multiple traveling salesman problem: An overview of formulations and solution procedures","volume":"34","author":"Bektas","year":"2006","journal-title":"Omega"},{"key":"ref_17","doi-asserted-by":"crossref","unstructured":"Ochelska-Mierzejewska, J., Poniszewska-Mara\u0144da, A., and Mara\u0144da, W. (2021). Selected Genetic Algorithms for Vehicle Routing Problem Solving. Electronics, 10.","DOI":"10.3390\/electronics10243147"},{"key":"ref_18","unstructured":"De Jaegere, N., Defraeye, M., and Van Nieuwenhuyse, I. (2014). The Vehicle Routing Problem: State of the Art Classification and Review, KU Leuven\u2014Faculty of Economics and Business. Technical Report Research Report KBI-1415."},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"27","DOI":"10.1007\/s12532-012-0047-y","article-title":"The time dependent traveling salesman problem: Polyhedra and algorithm","volume":"5","author":"Abeledo","year":"2013","journal-title":"Math. Program. Comput."},{"key":"ref_20","doi-asserted-by":"crossref","unstructured":"Hansknecht, C., Joormann, I., and Stiller, S. (2021). Dynamic Shortest Paths Methods for the Time-Dependent TSP. Algorithms, 14.","DOI":"10.3390\/a14010021"},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"47","DOI":"10.1007\/s11047-009-9111-6","article-title":"A memetic algorithm for the generalized traveling salesman problem","volume":"9","author":"Gutin","year":"2010","journal-title":"Nat. Comput."},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"972","DOI":"10.1057\/palgrave.jors.2601420","article-title":"Some applications of the clustered travelling salesman problem","volume":"53","author":"Laporte","year":"2002","journal-title":"J. Oper. Res. Soc."},{"key":"ref_23","unstructured":"Isoart, N., and R\u00e9gin, J.C. (2021, January 25\u201329). A k-Opt Based Constraint for the TSP. Proceedings of the 27th International Conference on Principles and Practice of Constraint Programming (CP 2021), Montpellier, France."},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"55","DOI":"10.1007\/s12532-013-0059-2","article-title":"Deterministic \u201cSnakes and Ladders\u201d Heuristic for the Hamiltonian cycle problem","volume":"6","author":"Baniasadi","year":"2014","journal-title":"Math. Program. Comput."},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"656","DOI":"10.4149\/cai_2018_3_656","article-title":"Breakout Local Search for the Travelling Salesman Problem","volume":"37","author":"Krari","year":"2018","journal-title":"Comput. Inform."},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"107","DOI":"10.1007\/s10732-013-9233-y","article-title":"A backbone based TSP heuristic for large instances","volume":"20","author":"Dong","year":"2014","journal-title":"J. Heuristics"},{"key":"ref_27","doi-asserted-by":"crossref","unstructured":"Tin\u00f3s, R., Helsgaun, K., and Whitley, D. (2018, January 8\u201312). Efficient Recombination in the Lin-Kernighan-Helsgaun Traveling Salesman Heuristic. Proceedings of the Parallel Problem Solving from Nature\u2014PPSN XV\u201415th International Conference on Parallel Problem Solving from Nature, Coimbra, Portugal.","DOI":"10.1007\/978-3-319-99253-2_8"},{"key":"ref_28","doi-asserted-by":"crossref","unstructured":"Liefooghe, A., and Paquete, L. (2019). Evolutionary Computation in Combinatorial Optimization, Springer.","DOI":"10.1007\/978-3-030-16711-0"},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"108653","DOI":"10.1016\/j.asoc.2022.108653","article-title":"Improving Ant Colony Optimization efficiency for solving large TSP instances","volume":"120","author":"Skinderowicz","year":"2022","journal-title":"Appl. Soft Comput."},{"key":"ref_30","doi-asserted-by":"crossref","first-page":"663","DOI":"10.3390\/a7040663","article-title":"COOBBO: A Novel Opposition-Based Soft Computing Algorithm for TSP Problems","volume":"7","author":"Xu","year":"2014","journal-title":"Algorithms"},{"key":"ref_31","doi-asserted-by":"crossref","first-page":"229","DOI":"10.3390\/a7020229","article-title":"Application of Imperialist Competitive Algorithm on Solving the Traveling Salesman Problem","volume":"7","author":"Xu","year":"2014","journal-title":"Algorithms"},{"key":"ref_32","doi-asserted-by":"crossref","unstructured":"Dahan, F., El Hindi, K., Mathkour, H., and AlSalman, H. (2019). Dynamic Flying Ant Colony Optimization (DFACO) for Solving the Traveling Salesman Problem. Sensors, 19.","DOI":"10.3390\/s19081837"},{"key":"ref_33","doi-asserted-by":"crossref","unstructured":"Jedrzejowicz, P., and Wierzbowska, I. (2020). Parallelized Swarm Intelligence Approach for Solving TSP and JSSP Problems. Algorithms, 13.","DOI":"10.3390\/a13060142"},{"key":"ref_34","doi-asserted-by":"crossref","unstructured":"Pacheco-Valencia, V., Hern\u00e1ndez, J.A., Sigarreta, J.M., and Vakhania, N. (2020). Simple Constructive, Insertion, and Improvement Heuristics Based on the Girding Polygon for the Euclidean Traveling Salesman Problem. Algorithms, 13.","DOI":"10.3390\/a13010005"},{"key":"ref_35","doi-asserted-by":"crossref","unstructured":"Zhang, Z., Xu, Z., Luan, S., Li, X., and Sun, Y. (2020). Opposition-Based Ant Colony Optimization Algorithm for the Traveling Salesman Problem. Mathematics, 8.","DOI":"10.3390\/math8101650"},{"key":"ref_36","doi-asserted-by":"crossref","unstructured":"Mele, U.J., Gambardella, L.M., and Montemanni, R. (2021). A New Constructive Heuristic Driven by Machine Learning for the Traveling Salesman Problem. Algorithms, 14.","DOI":"10.3390\/a14090267"},{"key":"ref_37","doi-asserted-by":"crossref","unstructured":"Qamar, M.S., Tu, S., Ali, F., Armghan, A., Munir, M.F., Alenezi, F., Muhammad, F., Ali, A., and Alnaim, N. (2021). Improvement of Traveling Salesman Problem Solution Using Hybrid Algorithm Based on Best-Worst Ant System and Particle Swarm Optimization. Appl. Sci., 11.","DOI":"10.3390\/app11114780"},{"key":"ref_38","doi-asserted-by":"crossref","unstructured":"Sharma, S., and Chou, J. (2022). Accelerate Incremental TSP Algorithms on Time Evolving Graphs with Partitioning Methods. Algorithms, 15.","DOI":"10.3390\/a15020064"},{"key":"ref_39","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":"Eur. J. Oper. Res."},{"key":"ref_40","doi-asserted-by":"crossref","unstructured":"Zhang, J., Hong, L., and Liu, Q. (2021). An Improved Whale Optimization Algorithm for the Traveling Salesman Problem. Symmetry, 13.","DOI":"10.3390\/sym13010048"},{"key":"ref_41","doi-asserted-by":"crossref","unstructured":"Fischer, T., and Merz, P. (2007, January 11\u201313). Reducing the size of traveling salesman problem instances by fixing edges. Proceedings of the 7th European Conference on Evolutionary Computation in Combinatorial Optimization, Valencia, Spain.","DOI":"10.1007\/978-3-540-71615-0_7"},{"key":"ref_42","doi-asserted-by":"crossref","first-page":"652417","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. Robot. AI"},{"key":"ref_43","doi-asserted-by":"crossref","unstructured":"Yelmewad, P., and Talawar, B. (2018, January 16\u201317). Near Optimal Solution for Traveling Salesman Problem using GPU. Proceedings of the 2018 IEEE International Conference on Electronics, Computing and Communication Technologies (CONECCT), Bangalore, India.","DOI":"10.1109\/CONECCT.2018.8482363"},{"key":"ref_44","first-page":"793","article-title":"Sur la sph\u00e8re vide","volume":"6","author":"Delaunay","year":"1934","journal-title":"Bull. l\u2019Acad\u00e9mie Sci. l\u2019URSS"},{"key":"ref_45","doi-asserted-by":"crossref","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":"ref_46","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":"Eur. J. Oper. Res."},{"key":"ref_47","unstructured":"Helsgaun, K. (2006). An Effective Implementation of K-Opt Moves for the Lin-Kernighan TSP Heuristic, Computer Science, Roskilde University. Technical report."},{"key":"ref_48","unstructured":"Johnson, D. (1990, January 16\u201320). Local optimization and the Traveling Salesman Problem. Proceedings of the International Colloquium on Automata, Languages, and Programming, ICALP 1990, England, UK."},{"key":"ref_49","unstructured":"Reinelt, G. (1994). The Traveling Salesman: Computational Solutions for TSP Applications, Springer."},{"key":"ref_50","doi-asserted-by":"crossref","first-page":"1583","DOI":"10.1109\/TITS.2020.2972389","article-title":"Delaunay-Triangulation-Based Variable Neighborhood Search to Solve Large-Scale General Colored Traveling Salesman Problems","volume":"22","author":"Xu","year":"2021","journal-title":"IEEE Trans. Intell. Transp. Syst."},{"key":"ref_51","doi-asserted-by":"crossref","first-page":"152","DOI":"10.1007\/BF01840357","article-title":"A sweepline algorithm for Voronoi diagrams","volume":"2","author":"Fortune","year":"1987","journal-title":"Algorithmica"},{"key":"ref_52","doi-asserted-by":"crossref","first-page":"1131","DOI":"10.1057\/jors.1994.183","article-title":"On the Significance of the Initial Solution in Travelling Salesman Heuristics","volume":"45","author":"Perttunen","year":"1994","journal-title":"J. Oper. Res. Soc."},{"key":"ref_53","first-page":"177","article-title":"Converting MST to TSP path by branch elimination","volume":"11","author":"Nenonen","year":"2021","journal-title":"Appl. Sci."},{"key":"ref_54","doi-asserted-by":"crossref","first-page":"432","DOI":"10.1006\/jagm.1995.1018","article-title":"Data Structures for Traveling Salesmen","volume":"18","author":"Fredman","year":"1995","journal-title":"J. Algorithms"},{"key":"ref_55","unstructured":"Strutz, T. (2022, December 07). Sys2to6 Optimization: Source Code and TSP Instances. Available online: https:\/\/www.hs-coburg.de\/fileadmin\/fdm\/tilo.strutz\/Sys2to6-resources.zip."},{"key":"ref_56","unstructured":"Helsgaun, K. (2022, December 07). LKH-3 Version 3.0.6 (May 2019). Available online: http:\/\/webhotel4.ruc.dk\/~keld\/research\/LKH-3\/."},{"key":"ref_57","unstructured":"Helsgaun, K. Private communication."},{"key":"ref_58","doi-asserted-by":"crossref","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":"ref_59","unstructured":"University of Waterloo (2022, December 07). VLSI Data Sets. Available online: https:\/\/www.math.uwaterloo.ca\/tsp\/vlsi\/."},{"key":"ref_60","unstructured":"Helsgaun, K. (2022, December 07). Lin-Kernighan Heuristic Software. Available online: http:\/\/webhotel4.ruc.dk\/~keld\/research\/LKH\/LKH-2.0.10.tgz."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/16\/2\/91\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T18:27:15Z","timestamp":1760120835000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/16\/2\/91"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,2,7]]},"references-count":60,"journal-issue":{"issue":"2","published-online":{"date-parts":[[2023,2]]}},"alternative-id":["a16020091"],"URL":"https:\/\/doi.org\/10.3390\/a16020091","relation":{},"ISSN":["1999-4893"],"issn-type":[{"type":"electronic","value":"1999-4893"}],"subject":[],"published":{"date-parts":[[2023,2,7]]}}}