{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,30]],"date-time":"2026-03-30T15:05:55Z","timestamp":1774883155358,"version":"3.50.1"},"reference-count":55,"publisher":"Elsevier BV","license":[{"start":{"date-parts":[[2026,7,1]],"date-time":"2026-07-01T00:00:00Z","timestamp":1782864000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2026,7,1]],"date-time":"2026-07-01T00:00:00Z","timestamp":1782864000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/legal\/tdmrep-license"},{"start":{"date-parts":[[2026,7,1]],"date-time":"2026-07-01T00:00:00Z","timestamp":1782864000000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-017"},{"start":{"date-parts":[[2026,7,1]],"date-time":"2026-07-01T00:00:00Z","timestamp":1782864000000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-037"},{"start":{"date-parts":[[2026,7,1]],"date-time":"2026-07-01T00:00:00Z","timestamp":1782864000000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-012"},{"start":{"date-parts":[[2026,7,1]],"date-time":"2026-07-01T00:00:00Z","timestamp":1782864000000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-029"},{"start":{"date-parts":[[2026,7,1]],"date-time":"2026-07-01T00:00:00Z","timestamp":1782864000000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-004"}],"content-domain":{"domain":["elsevier.com","sciencedirect.com"],"crossmark-restriction":true},"short-container-title":["Computers & Operations Research"],"published-print":{"date-parts":[[2026,7]]},"DOI":"10.1016\/j.cor.2026.107443","type":"journal-article","created":{"date-parts":[[2026,3,9]],"date-time":"2026-03-09T16:45:37Z","timestamp":1773074737000},"page":"107443","update-policy":"https:\/\/doi.org\/10.1016\/elsevier_cm_policy","source":"Crossref","is-referenced-by-count":0,"special_numbering":"C","title":["A speed-up for Helsgaun\u2019s TSP heuristic by relaxing the positive gain criterion"],"prefix":"10.1016","volume":"191","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-4061-8943","authenticated-orcid":false,"given":"Sabrina C.L.","family":"Ammann","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0009-0009-1368-090X","authenticated-orcid":false,"given":"Birte","family":"Ostermann","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8792-4390","authenticated-orcid":false,"given":"Sebastian","family":"Stiller","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0883-1389","authenticated-orcid":false,"given":"Timo","family":"de Wolff","sequence":"additional","affiliation":[]}],"member":"78","reference":[{"key":"10.1016\/j.cor.2026.107443_b1","unstructured":"Applegate, D., Bixby, R., Chvatal, V., Cook, W., 1999. Finding tours in the TSP. Technical Report."},{"key":"10.1016\/j.cor.2026.107443_b2","series-title":"Concorde TSP solver","author":"Applegate","year":"2015"},{"issue":"1","key":"10.1016\/j.cor.2026.107443_b3","doi-asserted-by":"crossref","first-page":"82","DOI":"10.1287\/ijoc.15.1.82.15157","article-title":"Chained lin-kernighan for large traveling salesman problems","volume":"15","author":"Applegate","year":"2003","journal-title":"Informs J. Comput."},{"key":"10.1016\/j.cor.2026.107443_b4","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":"2","key":"10.1016\/j.cor.2026.107443_b5","doi-asserted-by":"crossref","first-page":"405","DOI":"10.1016\/j.ejor.2020.07.063","article-title":"Machine learning for combinatorial optimization: a methodological tour d\u2019horizon","volume":"290","author":"Bengio","year":"2021","journal-title":"European J. Oper. Res."},{"issue":"1","key":"10.1016\/j.cor.2026.107443_b6","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1007\/BF00940812","article-title":"Thermodynamical approach to the traveling salesman problem: An efficient simulation algorithm","volume":"45","author":"\u010cern\u00fd","year":"1985","journal-title":"J. Optim. Theory Appl."},{"issue":"4","key":"10.1016\/j.cor.2026.107443_b7","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":"10.1016\/j.cor.2026.107443_b8","series-title":"[Dataset]national travelling salesman problems","author":"Cook","year":"2001"},{"key":"10.1016\/j.cor.2026.107443_b9","series-title":"The traveling salesman problem: a computational study","author":"Cook","year":"2011"},{"issue":"6","key":"10.1016\/j.cor.2026.107443_b10","doi-asserted-by":"crossref","first-page":"791","DOI":"10.1287\/opre.6.6.791","article-title":"A method for solving traveling-salesman problems","volume":"6","author":"Croes","year":"1958","journal-title":"Oper. Res."},{"issue":"1","key":"10.1016\/j.cor.2026.107443_b11","doi-asserted-by":"crossref","first-page":"29","DOI":"10.1109\/3477.484436","article-title":"Ant system: optimization by a colony of cooperating agents","volume":"26","author":"Dorigo","year":"1996","journal-title":"IEEE Trans. Syst. Man Cybern. B"},{"key":"10.1016\/j.cor.2026.107443_b12","series-title":"Swarm intelligence","author":"Eberhart","year":"2001"},{"key":"10.1016\/j.cor.2026.107443_b13","series-title":"A hierarchical destroy and repair approach for solving very large-scale travelling salesman problem","author":"Fu","year":"2023"},{"key":"10.1016\/j.cor.2026.107443_b14","series-title":"Parallel Problem Solving from Nature - PPSN XII","first-page":"388","article-title":"Improving lin-kernighan-helsgaun with crossover on clustered instances of the TSP","author":"Hains","year":"2012"},{"key":"10.1016\/j.cor.2026.107443_b15","series-title":"An effective implementation of the lin-kernighan traveling salesman heuristic","author":"Helsgaun","year":"1998"},{"issue":"1","key":"10.1016\/j.cor.2026.107443_b16","doi-asserted-by":"crossref","first-page":"106","DOI":"10.1016\/S0377-2217(99)00284-2","article-title":"An effective implementation of the Lin\u2013Kernighan traveling salesman heuristic","volume":"126","author":"Helsgaun","year":"2000","journal-title":"European J. Oper. Res."},{"key":"10.1016\/j.cor.2026.107443_b17","series-title":"An effective implementation of K-opt moves for the lin-kernighan TSP heuristic","author":"Helsgaun","year":"2006"},{"key":"10.1016\/j.cor.2026.107443_b18","doi-asserted-by":"crossref","first-page":"119","DOI":"10.1007\/s12532-009-0004-6","article-title":"General k-opt submoves for the Lin\u2013Kernighan TSP heuristic","volume":"1","author":"Helsgaun","year":"2009","journal-title":"Math. Program. Comput."},{"key":"10.1016\/j.cor.2026.107443_b19","doi-asserted-by":"crossref","first-page":"269","DOI":"10.1007\/s12532-015-0080-8","article-title":"Solving the equality generalized traveling salesman problem using the Lin\u2013Kernighan\u2013Helsgaun algorithm","volume":"7","author":"Helsgaun","year":"2015","journal-title":"Math. Program. Comput."},{"key":"10.1016\/j.cor.2026.107443_b20","unstructured":"Helsgaun, K., 2017. An extension of the Lin-Kernighan-Helsgaun TSP solver for Constrained Traveling Salesman and Vehicle Routing Problems. Technical Report, 12."},{"key":"10.1016\/j.cor.2026.107443_b21","series-title":"Best LKH solutions for Tnm instances","author":"Helsgaun","year":"2018"},{"key":"10.1016\/j.cor.2026.107443_b22","series-title":"[Dataset]tnm_instances","author":"Helsgaun","year":"2022"},{"key":"10.1016\/j.cor.2026.107443_b23","series-title":"[software]LKH","author":"Helsgaun","year":"2023"},{"issue":"1","key":"10.1016\/j.cor.2026.107443_b24","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":"2020","journal-title":"Math. Program. Comput."},{"key":"10.1016\/j.cor.2026.107443_b25","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":"J\u00e4ger","year":"2014","journal-title":"J. Heuristics"},{"issue":"1","key":"10.1016\/j.cor.2026.107443_b26","first-page":"215","article-title":"The traveling salesman problem: A case study in local optimization","volume":"1","author":"Johnson","year":"1997","journal-title":"Local Search Comb. Optim."},{"key":"10.1016\/j.cor.2026.107443_b27","series-title":"[Dataset]experimental analysis of heuristics for the STSP","first-page":"369","author":"Johnson","year":"2007"},{"key":"10.1016\/j.cor.2026.107443_b28","first-page":"85","article-title":"Reducibility among combinatorial problems","author":"Karp","year":"1972"},{"issue":"4598","key":"10.1016\/j.cor.2026.107443_b29","doi-asserted-by":"crossref","first-page":"671","DOI":"10.1126\/science.220.4598.671","article-title":"Optimization by simulated annealing","volume":"220","author":"Kirkpatrick","year":"1983","journal-title":"Science"},{"key":"10.1016\/j.cor.2026.107443_b30","series-title":"Learning and Intelligent Optimization: 9th International Conference, LION 9, Lille, France, January 12-15, 2015. Revised Selected Papers 9","first-page":"202","article-title":"Improving the state of the art in inexact TSP solving using per-instance algorithm selection","author":"Kotthoff","year":"2015"},{"issue":"10","key":"10.1016\/j.cor.2026.107443_b31","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."},{"issue":"2","key":"10.1016\/j.cor.2026.107443_b32","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.cor.2026.107443_b33","doi-asserted-by":"crossref","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":"10.1016\/j.cor.2026.107443_b34","unstructured":"Nagata, Y., 1997. Edge assembly crossover: A high-power genetic algorithm for the traveling salesman problem. In: Proceedings of the 7th Internatinal Conferencenon Genetic Algorithms. pp. 450\u2013457."},{"issue":"2","key":"10.1016\/j.cor.2026.107443_b35","doi-asserted-by":"crossref","first-page":"346","DOI":"10.1287\/ijoc.1120.0506","article-title":"A powerful genetic algorithm using edge assembly crossover for the traveling salesman problem","volume":"25","author":"Nagata","year":"2013","journal-title":"INFORMS J. Comput."},{"key":"10.1016\/j.cor.2026.107443_b36","series-title":"Efficient cluster compensation for Lin- Kernighan heuristics","author":"Neto","year":"1999"},{"issue":"1","key":"10.1016\/j.cor.2026.107443_b37","doi-asserted-by":"crossref","first-page":"92","DOI":"10.1109\/TSMCB.2006.880136","article-title":"Implementation of an effective hybrid GA for large-scale traveling salesman problems","volume":"37","author":"Nguyen","year":"2007","journal-title":"IEEE Trans. Syst. Man Cybern. B"},{"key":"10.1016\/j.cor.2026.107443_b38","series-title":"Grover type speedups and traveling salesman problem","author":"Ostermann","year":"2023"},{"issue":"3","key":"10.1016\/j.cor.2026.107443_b39","doi-asserted-by":"crossref","first-page":"427","DOI":"10.1016\/j.ejor.2010.09.010","article-title":"Traveling salesman problem heuristics: Leading methods, implementations and latest advances","volume":"211","author":"Rego","year":"2011","journal-title":"European J. Oper. Res."},{"issue":"4","key":"10.1016\/j.cor.2026.107443_b40","doi-asserted-by":"crossref","first-page":"376","DOI":"10.1287\/ijoc.3.4.376","article-title":"[Dataset]TSPLIB\u2014A traveling salesman problem library","volume":"3","author":"Reinelt","year":"1991","journal-title":"ORSA J. Comput."},{"key":"10.1016\/j.cor.2026.107443_b41","series-title":"Combinatorial and Algorithmic Aspects of Networking: 4th Workshop, CAAN 2007, Halifax, Canada, August 14, 2007. Revised Papers 4","first-page":"99","article-title":"Improving the efficiency of helsgaun\u2019s lin-kernighan heuristic for the symmetric TSP","author":"Richter","year":"2007"},{"key":"10.1016\/j.cor.2026.107443_b42","series-title":"[Dataset]VLSI data sets","author":"Rohe","year":"2002"},{"key":"10.1016\/j.cor.2026.107443_b43","series-title":"Basic and Advanced Statistical Tests: Writing Results Sections and Creating Tables and Figures","first-page":"9","article-title":"One-sample T-test","author":"Ross","year":"2017"},{"key":"10.1016\/j.cor.2026.107443_b44","doi-asserted-by":"crossref","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":"10.1016\/j.cor.2026.107443_b45","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."},{"issue":"2","key":"10.1016\/j.cor.2026.107443_b46","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":"European J. Oper. Res."},{"issue":"8","key":"10.1016\/j.cor.2026.107443_b47","doi-asserted-by":"crossref","DOI":"10.1016\/j.jksuci.2023.101723","article-title":"Discovering lin-kernighan-helsgaun heuristic for routing optimization using self-supervised reinforcement learning","volume":"35","author":"Wang","year":"2023","journal-title":"J. King Saud Univ.-Computer Inf. Sci."},{"key":"10.1016\/j.cor.2026.107443_b48","doi-asserted-by":"crossref","unstructured":"Whitley, D., Hains, D., Howe, A., 2009. Tunneling between optima: partition crossover for the traveling salesman problem. In: Proceedings of the 11th Annual Conference on Genetic and Evolutionary Computation. pp. 915\u2013922.","DOI":"10.1145\/1569901.1570026"},{"issue":"6","key":"10.1016\/j.cor.2026.107443_b49","doi-asserted-by":"crossref","first-page":"80","DOI":"10.2307\/3001968","article-title":"Individual comparisons by ranking methods","volume":"1","author":"Wilcoxon","year":"1945","journal-title":"Biom. Bull."},{"issue":"2","key":"10.1016\/j.cor.2026.107443_b50","first-page":"489","article-title":"Multiagent optimization system for solving the traveling salesman problem (TSP)","volume":"39","author":"Xie","year":"2008","journal-title":"IEEE Trans. Syst. Man Cybern. B"},{"key":"10.1016\/j.cor.2026.107443_b51","first-page":"7472","article-title":"NeuroLKH: Combining deep learning model with Lin-Kernighan-Helsgaun heuristic for solving the traveling salesman problem","volume":"34","author":"Xin","year":"2021","journal-title":"Adv. Neural Inf. Process. Syst."},{"issue":"1","key":"10.1016\/j.cor.2026.107443_b52","article-title":"List-based simulated annealing algorithm for traveling salesman problem","volume":"2016","author":"Zhan","year":"2016","journal-title":"Comput. Intell. Neurosci."},{"key":"10.1016\/j.cor.2026.107443_b53","first-page":"343","article-title":"A novel local search algorithm for the traveling salesman problem that exploits backbones","volume":"vol. 5","author":"Zhang","year":"2005"},{"key":"10.1016\/j.cor.2026.107443_b54","first-page":"12445","article-title":"Combining reinforcement learning with lin-kernighan-helsgaun algorithm for the traveling salesman problem","volume":"vol. 35","author":"Zheng","year":"2021"},{"key":"10.1016\/j.cor.2026.107443_b55","doi-asserted-by":"crossref","DOI":"10.1016\/j.knosys.2022.110144","article-title":"Reinforced lin\u2013Kernighan\u2013helsgaun algorithms for the traveling salesman problems","volume":"260","author":"Zheng","year":"2023","journal-title":"Knowl.-Based Syst."}],"container-title":["Computers & Operations Research"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0305054826000614?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0305054826000614?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2026,3,30]],"date-time":"2026-03-30T14:32:14Z","timestamp":1774881134000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0305054826000614"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,7]]},"references-count":55,"alternative-id":["S0305054826000614"],"URL":"https:\/\/doi.org\/10.1016\/j.cor.2026.107443","relation":{},"ISSN":["0305-0548"],"issn-type":[{"value":"0305-0548","type":"print"}],"subject":[],"published":{"date-parts":[[2026,7]]},"assertion":[{"value":"Elsevier","name":"publisher","label":"This article is maintained by"},{"value":"A speed-up for Helsgaun\u2019s TSP heuristic by relaxing the positive gain criterion","name":"articletitle","label":"Article Title"},{"value":"Computers & Operations Research","name":"journaltitle","label":"Journal Title"},{"value":"https:\/\/doi.org\/10.1016\/j.cor.2026.107443","name":"articlelink","label":"CrossRef DOI link to publisher maintained version"},{"value":"article","name":"content_type","label":"Content Type"},{"value":"\u00a9 2026 Published by Elsevier Ltd.","name":"copyright","label":"Copyright"}],"article-number":"107443"}}