{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,7,26]],"date-time":"2024-07-26T00:13:38Z","timestamp":1721952818990},"reference-count":32,"publisher":"Oxford University Press (OUP)","issue":"4","license":[{"start":{"date-parts":[[2024,3,24]],"date-time":"2024-03-24T00:00:00Z","timestamp":1711238400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/academic.oup.com\/pages\/standard-publication-reuse-rights"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2024,7,25]]},"abstract":"Abstract<\/jats:title>\n This paper investigates the Generalized Traveling Salesman Problem (GTSP), which is an extension of the well-known Traveling Salesman Problem (TSP), and it searches for an optimal tour in a clustered graph, such that every cluster is visited exactly once. In this paper, we describe a novel Memetic Algorithm (MA) for solving efficiently the GTSP. Our proposed MA has at its core a genetic algorithm (GA), completed by a Chromosome Enhancement Procedure (CEP), which is based on a TSP solver and the Shortest Path (SP) algorithm and for improving the convergence characteristics of the GA, a Local Search (LS) operation is applied for the best chromosomes in each generation. We tested our algorithm on a set of well-known instances from the literature and the achieved results prove that our novel memetic algorithm is highly competitive against the existing solution approaches from the specialized literature.<\/jats:p>","DOI":"10.1093\/jigpal\/jzae019","type":"journal-article","created":{"date-parts":[[2024,3,27]],"date-time":"2024-03-27T15:37:25Z","timestamp":1711553845000},"page":"576-588","source":"Crossref","is-referenced-by-count":0,"title":["A novel memetic algorithm for solving the generalized traveling salesman problem"],"prefix":"10.1093","volume":"32","author":[{"given":"Ovidiu","family":"Cosma","sequence":"first","affiliation":[{"name":"Department of Mathematics and Informatics, Technical University of Cluj-Napoca, North University Center at Baia Mare , Baia Mare 430122, Romania, ovidiu.cosma@mi.utcluj.ro"}]},{"given":"Petric\u0103 C","family":"Pop","sequence":"additional","affiliation":[{"name":"Department of Mathematics and Informatics, Technical University of Cluj-Napoca, North University Center at Baia Mare , Baia Mare 430122, Romania, petrica.pop@mi.utcluj.ro"}]},{"given":"Laura","family":"Cosma","sequence":"additional","affiliation":[{"name":"Department of Mathematics and Informatics, Technical University of Cluj-Napoca, North University Center at Baia Mare , Baia Mare 430122, Romania, laura.ov.cosma@student.utcluj.ro"}]}],"member":"286","published-online":{"date-parts":[[2024,3,24]]},"reference":[{"key":"2024072520071183800_ref1","volume-title":"Concorde Tsp Solver","author":"Applegate"},{"key":"2024072520071183800_ref2","doi-asserted-by":"crossref","first-page":"444","DOI":"10.1016\/j.ejor.2020.01.053","article-title":"A transformation technique for the clustered generalized traveling salesman problem with applications to logistics","volume":"285","author":"Baniasadi","year":"2020","journal-title":"European Journal of Operational Research"},{"key":"2024072520071183800_ref3","doi-asserted-by":"crossref","first-page":"1844","DOI":"10.1016\/j.cor.2009.05.004","article-title":"A memetic algorithm with a large neighborhood crossover operator for the generalized traveling salesman problem","volume":"37","author":"Bontoux","year":"2010","journal-title":"Computers & Operations Research"},{"key":"2024072520071183800_ref4","doi-asserted-by":"crossref","first-page":"231","DOI":"10.1002\/net.20421","article-title":"A multistart heuristic for the equality generalized traveling salesman problem","volume":"57","author":"Cacchiani","year":"2011","journal-title":"Networks"},{"key":"2024072520071183800_ref5","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":"Computers & Operations Research"},{"key":"2024072520071183800_ref6","doi-asserted-by":"crossref","first-page":"15570","DOI":"10.1109\/ACCESS.2021.3053295","article-title":"An effective genetic algorithm for solving the clustered shortest-path tree problem","volume":"9","author":"Cosma","year":"2021","journal-title":"IEEE Access"},{"key":"2024072520071183800_ref7","doi-asserted-by":"crossref","first-page":"113","DOI":"10.1007\/978-3-030-86271-8_10","article-title":"An effective hybrid genetic algorithm for solving the generalized traveling salesman problem","volume":"12886","author":"Cosma","year":"2021","journal-title":"Lecture Notes in Computer Science"},{"key":"2024072520071183800_ref8","doi-asserted-by":"crossref","first-page":"378","DOI":"10.1287\/opre.45.3.378","article-title":"A branch-and-cut algorithm for the symmetric generalized traveling salesman problem","volume":"45","author":"Fischetti","year":"1997","journal-title":"Operations Research"},{"key":"2024072520071183800_ref9","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":"Natural Computing"},{"key":"2024072520071183800_ref10","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":"Mathematical Programming Computation"},{"key":"2024072520071183800_ref11","doi-asserted-by":"crossref","first-page":"221","DOI":"10.1016\/j.ejor.2010.08.011","article-title":"Lin\u2013Kernighan heuristic adaptations for the generalized traveling salesman problem","volume":"208","author":"Karapetyan","year":"2011","journal-title":"European Journal of Operational Research"},{"key":"2024072520071183800_ref12","doi-asserted-by":"crossref","first-page":"234","DOI":"10.1016\/j.ejor.2012.01.011","article-title":"Efficient local search algorithms for known and new neighborhoods for the generalized traveling salesman problem","volume":"219","author":"Karapetyan","year":"2012","journal-title":"European Journal of Operational Research"},{"key":"2024072520071183800_ref13","first-page":"114","article-title":"Computational evaluation of a transformation procedure for the symmetric generalized traveling salesman problem","volume":"37","author":"Laporte","year":"1999","journal-title":"INFOR: Information Systems and Operational Research"},{"key":"2024072520071183800_ref14","doi-asserted-by":"crossref","first-page":"1461","DOI":"10.1057\/jors.1996.190","article-title":"Some applications of the generalized travelling salesman problem","volume":"47","author":"Laporte","year":"1996","journal-title":"Journal of the Operational Research Society"},{"key":"2024072520071183800_ref15","author":"The LEMON library"},{"key":"2024072520071183800_ref16","doi-asserted-by":"crossref","first-page":"87","DOI":"10.1109\/ICCP.2010.5606458","article-title":"An efficient genetic algorithm for solving the generalized traveling salesman problem","volume-title":"Proceedings of the 2010 IEEE 6th International Conference on Intelligent Computer Communication and Processing","author":"Matei","year":"2010"},{"key":"2024072520071183800_ref17","doi-asserted-by":"crossref","first-page":"3218","DOI":"10.1016\/j.cor.2012.10.001","article-title":"GRASP with path relinking for the symmetric Euclidean clustered traveling salesman problem","volume":"40","author":"Mestria","year":"2013","journal-title":"Computers & Operations Research"},{"key":"2024072520071183800_ref18","doi-asserted-by":"crossref","first-page":"623","DOI":"10.1287\/opre.39.4.623","article-title":"A Lagrangian based approach for the asymmetric generalized traveling salesman problem","volume":"39","author":"Noon","year":"1991","journal-title":"Operations Research"},{"key":"2024072520071183800_ref19","article-title":"The generalized traveling salesman problem solved with ant algorithms","volume":"5","author":"Pintea","year":"2017","journal-title":"Complex Adaptive Modelling Systems"},{"key":"2024072520071183800_ref20","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.ejor.2019.05.017","article-title":"The generalized minimum spanning tree problem: an overview of formulations, solution procedures and latest advances","volume":"283","author":"Pop","year":"2020","journal-title":"European Journal of Operational Research"},{"key":"2024072520071183800_ref21","first-page":"149","article-title":"A hybrid diploid genetic based algorithm for solving the generalized traveling salesman problem","volume-title":"HAIS 2017, LNCS","author":"Pop","year":"2017"},{"key":"2024072520071183800_ref22","doi-asserted-by":"crossref","DOI":"10.1515\/9783110267686","volume-title":"Generalized Network Design Problems. Modeling and Optimization","author":"Pop","year":"2012"},{"key":"2024072520071183800_ref23","doi-asserted-by":"crossref","first-page":"481","DOI":"10.1145\/2001576.2001643","article-title":"A hybrid heuristic approach for solving the generalized traveling salesman problem","volume-title":"Proceedings of the 13th Annual Conference on Genetic and Evolutionary Computation, GECCO 2011","author":"Pop","year":"2011"},{"key":"2024072520071183800_ref24","first-page":"62","article-title":"A new approach for solving the generalized traveling salesman problem","volume-title":"Hybrid Metaheuristics. HM 2010","author":"Pop","year":"2010"},{"key":"2024072520071183800_ref25","doi-asserted-by":"crossref","first-page":"932","DOI":"10.3844\/ajassp.2007.932.937","article-title":"New integer programming formulations of the generalized traveling salesman problem","volume":"4","author":"Pop","year":"2007","journal-title":"American Journal of Applied Sciences"},{"key":"2024072520071183800_ref26","first-page":"22","article-title":"An efficient hybrid ant colony system for the generalized traveling salesman problem","volume":"7","author":"Reihaneh","year":"2012","journal-title":"Algorithmic Operations Research"},{"key":"2024072520071183800_ref27","doi-asserted-by":"crossref","first-page":"571","DOI":"10.1016\/S0377-2217(97)00142-2","article-title":"An efficient composite heuristic for the symmetric generalized traveling salesman problem","volume":"108","author":"Renaud","year":"1998","journal-title":"European Journal of Operational Research"},{"key":"2024072520071183800_ref28","first-page":"1","article-title":"New neighborhoods and an iterated local search algorithm for the generalized traveling salesman problem","volume-title":"Gutenberg School of Management and Economics Working Papers","author":"Schmidt","year":"2020"},{"key":"2024072520071183800_ref29","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":"Computers & Operations Research"},{"key":"2024072520071183800_ref30","doi-asserted-by":"crossref","first-page":"38","DOI":"10.1016\/j.ejor.2004.09.057","article-title":"A random-key genetic algorithm for the generalized traveling salesman problem","volume":"174","author":"Snyder","year":"2006","journal-title":"European Journal of Operational Research"},{"key":"2024072520071183800_ref31","first-page":"158","article-title":"A discrete particle swarm optimization algorithm for the generalized traveling salesman problem","volume-title":"Proceedings of the 9th Annual Conference on Genetic and Evolutionary Computation, GECCO 2007","author":"Tasgetiren","year":"2007"},{"key":"2024072520071183800_ref32","article-title":"Mixed integer programming formulations for the generalized traveling salesman problem with time windows","author":"Yuan","year":"2020","journal-title":"4OR - A Quarterly of Journal Operations Research"}],"container-title":["Logic Journal of the IGPL"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/jigpal\/article-pdf\/32\/4\/576\/58646519\/jzae019.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/jigpal\/article-pdf\/32\/4\/576\/58646519\/jzae019.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,7,25]],"date-time":"2024-07-25T20:09:21Z","timestamp":1721938161000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/jigpal\/article\/32\/4\/576\/7632100"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,3,24]]},"references-count":32,"journal-issue":{"issue":"4","published-online":{"date-parts":[[2024,3,24]]},"published-print":{"date-parts":[[2024,7,25]]}},"URL":"https:\/\/doi.org\/10.1093\/jigpal\/jzae019","relation":{},"ISSN":["1367-0751","1368-9894"],"issn-type":[{"value":"1367-0751","type":"print"},{"value":"1368-9894","type":"electronic"}],"subject":[],"published-other":{"date-parts":[[2024,8]]},"published":{"date-parts":[[2024,3,24]]}}}