{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,14]],"date-time":"2026-02-14T06:05:49Z","timestamp":1771049149228,"version":"3.50.1"},"reference-count":47,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2026,1,1]],"date-time":"2026-01-01T00:00:00Z","timestamp":1767225600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2026,1,30]],"date-time":"2026-01-30T00:00:00Z","timestamp":1769731200000},"content-version":"vor","delay-in-days":29,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"TED University"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Neural Comput &amp; Applic"],"published-print":{"date-parts":[[2026,1]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>The Close-Enough Traveling Salesman Problem (CETSP) is a complex variant of the classical TSP in which each target is represented by a disk-shaped neighborhood, and a visit is considered valid if any point within that neighborhood is reached. This formulation provides a more realistic model for real-world applications such as surveillance, wireless sensor routing, and Unmanned Aerial Vehicle (UAV) path planning. However, due to its NP-hard nature, solving large-scale CETSP instances efficiently remains a significant challenge. The main objective of this study is to develop scalable and robust Parallel Memetic Algorithms (PMAs) that enhance computational efficiency and solution quality for large CETSP instances. Two complementary strategies are proposed: (i) a Multi-Population PMA that maintains diversity through distributed crossover and parallel local optimization, and (ii) a Single-Population, Multi-Fitness PMA that accelerates convergence via simultaneous parallel fitness evaluations. Extensive experiments conducted on 42 benchmark instances demonstrate that the proposed algorithms outperform state-of-the-art approaches, achieving 21 new best-known solutions and up to a 10\u201315 times reduction in the execution times compared to the sequential MA-CETSP algorithm. The results confirm that the Multi-Population PMA provides superior exploration capabilities for complex instances, while the Single-Population PMA delivers faster convergence with comparable solution quality. Overall, this study establishes new performance benchmarks for the CETSP and demonstrates the effectiveness of parallel memetic algorithms in solving large-scale combinatorial optimization problems.<\/jats:p>","DOI":"10.1007\/s00521-025-11706-4","type":"journal-article","created":{"date-parts":[[2026,1,30]],"date-time":"2026-01-30T03:33:40Z","timestamp":1769744020000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Scalable parallel memetic algorithms for large close-enough traveling salesman problems"],"prefix":"10.1007","volume":"38","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-7606-8701","authenticated-orcid":false,"given":"Deniz","family":"Canturk","sequence":"first","affiliation":[]},{"given":"Tansel","family":"D\u00f6kero\u011flu","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2026,1,30]]},"reference":[{"issue":"10","key":"11706_CR1","doi-asserted-by":"publisher","first-page":"2245","DOI":"10.1002\/j.1538-7305.1965.tb04146.x","volume":"44","author":"S Lin","year":"1965","unstructured":"Lin S (1965) Computer solutions of the traveling salesman problem. Bell Syst Tech J 44(10):2245\u20132269","journal-title":"Bell Syst Tech J"},{"key":"11706_CR2","doi-asserted-by":"crossref","unstructured":"Gutin G, Punnen A P (Eds.) (2006). The traveling salesman problem and its variations (Vol. 12). Springer Science & Business Media","DOI":"10.1007\/b101971"},{"issue":"3","key":"11706_CR3","doi-asserted-by":"publisher","first-page":"974","DOI":"10.1016\/j.ejor.2023.04.010","volume":"310","author":"A Di Placido","year":"2023","unstructured":"Di Placido A, Archetti C, Cerrone C, Golden B (2023) The generalized close enough traveling salesman problem. Eur J Oper Res 310(3):974\u2013991","journal-title":"Eur J Oper Res"},{"key":"11706_CR4","doi-asserted-by":"crossref","unstructured":"Lee Y W, Eun S, Oh S H (2008). Wireless digital water meter with low power consumption for automatic meter reading. In 2008 International Conference on Convergence and Hybrid Information Technology (pp. 639-645). IEEE","DOI":"10.1109\/ICHIT.2008.172"},{"key":"11706_CR5","doi-asserted-by":"publisher","DOI":"10.1016\/j.cor.2022.105831","volume":"145","author":"A Di Placido","year":"2022","unstructured":"Di Placido A, Archetti C, Cerrone C (2022) A genetic algorithm for the close-enough traveling salesman problem with application to solar panels diagnostic reconnaissance. Comput Oper Res 145:105831","journal-title":"Comput Oper Res"},{"issue":"4","key":"11706_CR6","doi-asserted-by":"publisher","first-page":"451","DOI":"10.1109\/TMECH.2008.2000822","volume":"13","author":"GE Jan","year":"2008","unstructured":"Jan GE, Chang KY, Parberry I (2008) Optimal path planning for mobile robot navigation. IEEE\/ASME Trans Mechatron 13(4):451\u2013460","journal-title":"IEEE\/ASME Trans Mechatron"},{"key":"11706_CR7","doi-asserted-by":"publisher","first-page":"293","DOI":"10.1007\/s10479-012-1261-8","volume":"222","author":"L Evers","year":"2014","unstructured":"Evers L, Dollevoet T, Barros AI, Monsuur H (2014) Robust UAV mission planning. Ann Oper Res 222:293\u2013315","journal-title":"Ann Oper Res"},{"key":"11706_CR8","doi-asserted-by":"publisher","first-page":"60","DOI":"10.1016\/j.ins.2012.11.017","volume":"227","author":"F Caraffini","year":"2013","unstructured":"Caraffini F, Neri F, Iacca G, Mol A (2013) Parallel memetic structures. Inf Sci 227:60\u201382","journal-title":"Inf Sci"},{"key":"11706_CR9","doi-asserted-by":"publisher","DOI":"10.1002\/0471739383","volume-title":"Parallel metaheuristics: a new class of algorithms","author":"E Alba","year":"2005","unstructured":"Alba E (2005) Parallel metaheuristics: a new class of algorithms. John Wiley & Sons"},{"key":"11706_CR10","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.swevo.2011.11.003","volume":"2","author":"F Neri","year":"2012","unstructured":"Neri F, Cotta C (2012) Memetic algorithms and memetic computing optimization: A literature review. Swarm Evol Comput 2:1\u201314","journal-title":"Swarm Evol Comput"},{"key":"11706_CR11","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1007\/978-3-540-39930-8_3","volume":"141","author":"P Moscato","year":"2004","unstructured":"Moscato P, Cotta C, Mendes A (2004) Memetic algorithms. New Optim Tech Eng 141:53\u201385","journal-title":"New Optim Tech Eng"},{"key":"11706_CR12","doi-asserted-by":"publisher","DOI":"10.1016\/j.asoc.2024.111266","volume":"153","author":"Z Lei","year":"2024","unstructured":"Lei Z, Hao JK (2024) An effective memetic algorithm for the close-enough traveling salesman problem. Appl Soft Comput 153:111266","journal-title":"Appl Soft Comput"},{"key":"11706_CR13","volume-title":"Parallel programming in OpenMP","author":"R Chandra","year":"2001","unstructured":"Chandra R (2001) Parallel programming in OpenMP. Morgan Kaufmann"},{"key":"11706_CR14","doi-asserted-by":"crossref","unstructured":"Ayguad\u00e9 E, Copty N, Duran A, Hoeflinger J, Lin Y, Massaioli F, Zhang G (2008) The design of OpenMP tasks. IEEE Trans Parallel Distrib Syst 20(3):404\u2013418","DOI":"10.1109\/TPDS.2008.105"},{"issue":"2","key":"11706_CR15","doi-asserted-by":"publisher","DOI":"10.1002\/cpe.7891","volume":"36","author":"\u00d6 D\u00fclger","year":"2024","unstructured":"D\u00fclger \u00d6, D\u00f6keroglu T (2024) A new parallel tabu search algorithm for the optimization of the maximum vertex weight clique problem. Concurr Comput Pract Exper 36(2):e7891","journal-title":"Concurr Comput Pract Exper"},{"key":"11706_CR16","doi-asserted-by":"crossref","unstructured":"Gulczynski D J, Heath J W, Price C C (2006). The close enough traveling salesman problem: A discussion of several heuristics. Perspectives in Operations Research: Papers in Honor of Saul Gass\u2019 80 th Birthday, 271-283","DOI":"10.1007\/978-0-387-39934-8_16"},{"key":"11706_CR17","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1016\/j.cor.2016.09.003","volume":"78","author":"F Carrabs","year":"2017","unstructured":"Carrabs F, Cerrone C, Cerulli R, Gaudioso M (2017) A novel discretization scheme for the close enough traveling salesman problem. Comput Oper Res 78:163\u2013171","journal-title":"Comput Oper Res"},{"key":"11706_CR18","doi-asserted-by":"publisher","DOI":"10.1016\/j.eswa.2024.125185","volume":"258","author":"J Deckerov\u00e1","year":"2024","unstructured":"Deckerov\u00e1 J, V\u00e1\u0148a P, Faigl J (2024) Combinatorial lower bounds for the generalized traveling salesman problem with neighborhoods. Expert Syst Appl 258:125185","journal-title":"Expert Syst Appl"},{"key":"11706_CR19","doi-asserted-by":"publisher","first-page":"8091","DOI":"10.1007\/s11042-020-10139-6","volume":"80","author":"S Katoch","year":"2021","unstructured":"Katoch S, Chauhan SS, Kumar V (2021) A review on genetic algorithm: past, present, and future. Multimedia Tools Appl 80:8091\u20138126","journal-title":"Multimedia Tools Appl"},{"issue":"4","key":"11706_CR20","doi-asserted-by":"publisher","first-page":"752","DOI":"10.1287\/ijoc.2016.0711","volume":"28","author":"WP Coutinho","year":"2016","unstructured":"Coutinho WP, Nascimento RQD, Pessoa AA, Subramanian A (2016) A branch-and-bound algorithm for the close-enough traveling salesman problem. INFORMS J Comput 28(4):752\u2013765","journal-title":"INFORMS J Comput"},{"issue":"3","key":"11706_CR21","doi-asserted-by":"publisher","first-page":"415","DOI":"10.1287\/ijoc.2013.0574","volume":"26","author":"B Behdani","year":"2014","unstructured":"Behdani B, Smith JC (2014) An integer-programming-based approach to the close-enough traveling salesman problem. INFORMS J Comput 26(3):415\u2013432","journal-title":"INFORMS J Comput"},{"issue":"4","key":"11706_CR22","first-page":"1030","volume":"32","author":"F Carrabs","year":"2020","unstructured":"Carrabs F, Cerrone C, Cerulli R, Golden B (2020) An adaptive heuristic approach to compute upper and lower bounds for the close-enough traveling salesman problem. INFORMS J Comput 32(4):1030\u20131048","journal-title":"INFORMS J Comput"},{"key":"11706_CR23","doi-asserted-by":"crossref","unstructured":"Deckerov\u00e1 J, Ku\u010derov\u00e1 K, Faigl J (2023). On improvement heuristic to solutions of the close enough traveling salesman problem in environments with obstacles. In 2023 European Conference on Mobile Robots (ECMR) (pp. 1-6). IEEE","DOI":"10.1109\/ECMR59166.2023.10256328"},{"key":"11706_CR24","doi-asserted-by":"crossref","unstructured":"Kennedy J, Eberhart R (1995, November). Particle swarm optimization. In Proceedings of ICNN\u201995-international conference on neural networks (Vol. 4, pp. 1942-1948). ieee","DOI":"10.1109\/ICNN.1995.488968"},{"key":"11706_CR25","doi-asserted-by":"publisher","DOI":"10.1016\/j.cie.2019.106040","volume":"137","author":"T Dokeroglu","year":"2019","unstructured":"Dokeroglu T, Sevinc E, Kucukyilmaz T, Cosar A (2019) A survey on new generation metaheuristic algorithms. Comput Indus Eng 137:106040","journal-title":"Comput Indus Eng"},{"issue":"1","key":"11706_CR26","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1016\/j.ejor.2017.07.024","volume":"265","author":"Z Yang","year":"2018","unstructured":"Yang Z, Xiao MQ, Ge YW, Feng DL, Zhang L, Song HF, Tang XL (2018) A double-loop hybrid algorithm for the traveling salesman problem with arbitrary neighbourhoods. Eur J Oper Res 265(1):65\u201380","journal-title":"Eur J Oper Res"},{"issue":"1","key":"11706_CR27","doi-asserted-by":"publisher","first-page":"44","DOI":"10.3390\/a16010044","volume":"16","author":"C Cariou","year":"2023","unstructured":"Cariou C, Moiroux-Arvis L, Pinet F, Chanet JP (2023) Evolutionary algorithm with geometrical heuristics for solving the Close Enough Traveling Salesman Problem: Application to the trajectory planning of an Unmanned Aerial Vehicle. Algorithms 16(1):44","journal-title":"Algorithms"},{"key":"11706_CR28","doi-asserted-by":"publisher","first-page":"120","DOI":"10.1016\/j.neucom.2018.05.079","volume":"312","author":"J Faigl","year":"2018","unstructured":"Faigl J (2018) GSOA: growing self-organizing array-unsupervised learning for the close-enough traveling salesman problem and other routing problems. Neurocomputing 312:120\u2013134","journal-title":"Neurocomputing"},{"key":"11706_CR29","doi-asserted-by":"crossref","unstructured":"Carrabs F, Cerulli R, D\u2019Ambrosio C, Murano G (2025). Upper Bound Computation for the Multiple Close-Enough Traveling Salesman Problem. In Proceedings of the 14th International Conference on Operations Research and Enterprise Systems-ICORES (pp. 186-195)","DOI":"10.5220\/0013377900003893"},{"key":"11706_CR30","unstructured":"Toman O (2025). Toward optimal solution of the close enough traveling salesman problem using interval sampling. Master\u2019s thesis"},{"key":"11706_CR31","doi-asserted-by":"crossref","unstructured":"Dokeroglu T, Canturk D (2025). New Harris Hawks algorithms for the Close-Enough Traveling Salesman Problem. Intelligent Systems with Applications, 200586","DOI":"10.1016\/j.iswa.2025.200586"},{"key":"11706_CR32","doi-asserted-by":"publisher","first-page":"200","DOI":"10.1016\/j.cor.2018.07.023","volume":"101","author":"X Wang","year":"2019","unstructured":"Wang X, Golden B, Wasil E (2019) A steiner zone variable neighborhood search heuristic for the close-enough traveling salesman problem. Comput Oper Res 101:200\u2013219","journal-title":"Comput Oper Res"},{"key":"11706_CR33","volume-title":"Heuristics for solving three routing problems: Close-enough traveling salesman problem, close-enough vehicle routing problem, and sequence-dependent team orienteering problem","author":"WK Mennell","year":"2009","unstructured":"Mennell WK (2009) Heuristics for solving three routing problems: Close-enough traveling salesman problem, close-enough vehicle routing problem, and sequence-dependent team orienteering problem. University of Maryland, College Park"},{"key":"11706_CR34","doi-asserted-by":"crossref","unstructured":"Padilha G A G, Jung J J, de Mattos Neto P S (2024). Memetic algorithm-based optimization of hybrid forecasting systems for multivariate time series. Neural Computing and Applications, 1-18","DOI":"10.1007\/s00521-024-10618-z"},{"issue":"3","key":"11706_CR35","doi-asserted-by":"publisher","first-page":"423","DOI":"10.1007\/s13675-016-0075-x","volume":"5","author":"P Hansen","year":"2017","unstructured":"Hansen P, Mladenovi\u0107 N, Todosijevi\u0107 R, Hanafi S (2017) Variable neighborhood search: basics and variants. EURO J Comput Optim 5(3):423\u2013454","journal-title":"EURO J Comput Optim"},{"issue":"1","key":"11706_CR36","doi-asserted-by":"publisher","first-page":"106","DOI":"10.1016\/S0377-2217(99)00284-2","volume":"126","author":"K Helsgaun","year":"2000","unstructured":"Helsgaun K (2000) An effective implementation of the Lin-Kernighan traveling salesman heuristic. Eur J Oper Res 126(1):106\u2013130","journal-title":"Eur J Oper Res"},{"key":"11706_CR37","unstructured":"Aslan Y, Candotti M, Yarovoy A (2019). Synthesis of multi-beam space-tapered linear arrays with side lobe level minimization in the presence of mutual coupling. In 2019 13th European Conference on Antennas and Propagation (EuCAP) (pp. 1-5). IEEE"},{"key":"11706_CR38","volume-title":"A memetic algorithm for the close-enough traveling salesman problem","author":"Z Lei","year":"2023","unstructured":"Lei Z, Hao JK (2023) A memetic algorithm for the close-enough traveling salesman problem. In EU\/Meeting, Troyes, France"},{"key":"11706_CR39","doi-asserted-by":"publisher","first-page":"873","DOI":"10.1007\/s00500-006-0139-6","volume":"11","author":"J Tang","year":"2007","unstructured":"Tang J, Lim MH, Ong YS (2007) Diversity-adaptive parallel memetic algorithm for solving large scale combinatorial optimization problems. Soft Comput 11:873\u2013888","journal-title":"Soft Comput"},{"key":"11706_CR40","doi-asserted-by":"publisher","first-page":"812","DOI":"10.1007\/s10766-014-0343-4","volume":"43","author":"J Nalepa","year":"2015","unstructured":"Nalepa J, Blocho M (2015) Co-operation in the parallel memetic algorithm. Int J Parallel Prog 43:812\u2013839","journal-title":"Int J Parallel Prog"},{"issue":"5","key":"11706_CR41","doi-asserted-by":"publisher","first-page":"1214","DOI":"10.1016\/j.cor.2004.09.011","volume":"33","author":"K S\u00f6rensen","year":"2006","unstructured":"S\u00f6rensen K, Sevaux M (2006) MA|PM: memetic algorithms with population management. Comput Oper Res 33(5):1214\u20131225","journal-title":"Comput Oper Res"},{"key":"11706_CR42","doi-asserted-by":"publisher","first-page":"136","DOI":"10.1016\/j.ins.2020.08.040","volume":"547","author":"G D\u2019Angelo","year":"2021","unstructured":"D\u2019Angelo G, Palmieri F (2021) GGA: A modified genetic algorithm with gradient-based local search for solving constrained optimization problems. Inf Sci 547:136\u2013162","journal-title":"Inf Sci"},{"issue":"3","key":"11706_CR43","doi-asserted-by":"publisher","first-page":"1245","DOI":"10.1007\/s12065-023-00822-6","volume":"17","author":"B Alhijawi","year":"2024","unstructured":"Alhijawi B, Awajan A (2024) Genetic algorithms: Theory, genetic operators, solutions, and applications. Evol Intel 17(3):1245\u20131256","journal-title":"Evol Intel"},{"key":"11706_CR44","unstructured":"Gurobi Optimization, LLC, (2023) Gurobi Optimizer Reference Manual, https:\/\/www.gurobi.com"},{"key":"11706_CR45","first-page":"43","volume":"3","author":"M L\u00f3pez-Ib\u00e1\u00f1ez","year":"2016","unstructured":"L\u00f3pez-Ib\u00e1\u00f1ez M, Dubois-Lacoste J, C\u00e1ceres LP, Birattari M, St\u00fctzle T (2016) The irace package: Iterated racing for automatic algorithm configuration. Oper Res Perspect 3:43\u201358","journal-title":"Oper Res Perspect"},{"key":"11706_CR46","doi-asserted-by":"publisher","first-page":"376","DOI":"10.1287\/ijoc.3.4.376","volume":"3","author":"B Bixby","year":"1991","unstructured":"Bixby B, Reinelt G (1991) TSPLIB, A traveling salesman problem library. ORSA J Comput 3:376\u2013384","journal-title":"ORSA J Comput"},{"key":"11706_CR47","volume-title":"Algorithms and solutions to multi-level vehicle routing problems","author":"IM Chao","year":"1993","unstructured":"Chao IM (1993) Algorithms and solutions to multi-level vehicle routing problems. University of Maryland, College Park"}],"container-title":["Neural Computing and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00521-025-11706-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00521-025-11706-4","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00521-025-11706-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,2,14]],"date-time":"2026-02-14T05:19:32Z","timestamp":1771046372000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00521-025-11706-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,1]]},"references-count":47,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2026,1]]}},"alternative-id":["11706"],"URL":"https:\/\/doi.org\/10.1007\/s00521-025-11706-4","relation":{},"ISSN":["0941-0643","1433-3058"],"issn-type":[{"value":"0941-0643","type":"print"},{"value":"1433-3058","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,1]]},"assertion":[{"value":"27 March 2025","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"6 December 2025","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"30 January 2026","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"There is no Conflict of interest between authors.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}},{"value":"This article does not contain any studies with human participants or animals performed by any of the authors.","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Ethical approval"}}],"article-number":"27"}}