{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,24]],"date-time":"2026-03-24T05:19:43Z","timestamp":1774329583705,"version":"3.50.1"},"reference-count":33,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2023,10,25]],"date-time":"2023-10-25T00:00:00Z","timestamp":1698192000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,10,25]],"date-time":"2023-10-25T00:00:00Z","timestamp":1698192000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100011033","name":"Agencia Estatal de Investigaci\u00f3n","doi-asserted-by":"publisher","award":["PID2019-106263RB-I00"],"award-info":[{"award-number":["PID2019-106263RB-I00"]}],"id":[{"id":"10.13039\/501100011033","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100011033","name":"Agencia Estatal de Investigaci\u00f3n","doi-asserted-by":"publisher","award":["PID2019-106263RB-I00"],"award-info":[{"award-number":["PID2019-106263RB-I00"]}],"id":[{"id":"10.13039\/501100011033","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100011033","name":"Agencia Estatal de Investigaci\u00f3n","doi-asserted-by":"publisher","award":["PID2019-106263RB-I00"],"award-info":[{"award-number":["PID2019-106263RB-I00"]}],"id":[{"id":"10.13039\/501100011033","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004488","name":"Hrvatska Zaklada za Znanost","doi-asserted-by":"publisher","award":["IP-2019-04-4333"],"award-info":[{"award-number":["IP-2019-04-4333"]}],"id":[{"id":"10.13039\/501100004488","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100006382","name":"Universidad de Oviedo","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100006382","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Nat Comput"],"published-print":{"date-parts":[[2023,12]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>The Travelling Salesman Problem (TSP) is a well-known optimisation problem that has been widely studied over the last century. As a result, a variety of exact and approximate algorithms have been proposed in the literature. When it comes to solving large instances in real-time, greedy algorithms guided by priority rules represent the most common approach, being the nearest neighbour (NN) heuristic one of the most popular rules. NN is quite general but it is too simple and so it may not be the best choice in some cases. Alternatively, we may design more sophisticated heuristics considering the particular features of families of instances. To do that, we have to consider problem attributes other than the proximity of the next city to build priority rules. However, this process may not be easy for humans and so it is often addressed by some learning procedure. In this regard, hyper-heuristics as Genetic Programming (GP) stands as one of the most popular approaches. Furthermore, a single heuristic, even being good in average, may not be good for a number of instances of a given set. For this reason, the use of ensembles of heuristics is often a good alternative, which raises the problem of building ensembles from a given set of heuristic rules. In this paper, we study the application of two kinds of ensembles to the TSP. Given a set of TSP instances having similar characteristics, we firstly exploit a GP to build a set of heuristics involving a number of problem attributes, and then we build ensembles combining these heuristics by means of a Genetic Algorithm (GA). The experimental study provided valuable insights into the construction and utilisation of single rules and ensembles. It clearly demonstrated that the performance of ensembles justifies the time invested when compared to using individual heuristics.<\/jats:p>","DOI":"10.1007\/s11047-023-09968-9","type":"journal-article","created":{"date-parts":[[2023,10,25]],"date-time":"2023-10-25T03:40:28Z","timestamp":1698205228000},"page":"671-684","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":17,"title":["Evolving ensembles of heuristics for the travelling salesman problem"],"prefix":"10.1007","volume":"22","author":[{"given":"Francisco J.","family":"Gil-Gala","sequence":"first","affiliation":[]},{"given":"Marko","family":"Durasevi\u0107","sequence":"additional","affiliation":[]},{"given":"Mar\u00eda R.","family":"Sierra","sequence":"additional","affiliation":[]},{"given":"Ramiro","family":"Varela","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2023,10,25]]},"reference":[{"issue":"2","key":"9968_CR1","doi-asserted-by":"publisher","first-page":"249","DOI":"10.1162\/EVCO_a_00131","volume":"23","author":"J Branke","year":"2015","unstructured":"Branke J, Hildebrandt T, Scholz-Reiter B (2015) Hyper-heuristic evolution of dispatching rules: a comparison of rule representations. Evol Comput 23(2):249\u2013277","journal-title":"Evol Comput"},{"issue":"1","key":"9968_CR2","doi-asserted-by":"publisher","first-page":"110","DOI":"10.1109\/TEVC.2015.2429314","volume":"20","author":"J Branke","year":"2016","unstructured":"Branke J, Nguyen S, Pickardt CW, Zhang M (2016) Automated design of production scheduling heuristics: a review. IEEE Trans Evol Comput 20(1):110\u2013124","journal-title":"IEEE Trans Evol Comput"},{"key":"9968_CR3","doi-asserted-by":"crossref","unstructured":"Burke EK, Hyde MR, Kendall G, Ochoa G, \u00d6zcan E, Woodward JR (2019) A classification of hyper-heuristic approaches: revisited. In: Gendreau M, Potvin JY (eds) Handbook of metaheuristics. International series in operations research & management science vol 272, pp 453\u2013477","DOI":"10.1007\/978-3-319-91086-4_14"},{"issue":"1","key":"9968_CR4","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1162\/EVCO_a_00044","volume":"20","author":"EK Burke","year":"2012","unstructured":"Burke EK, Hyde MR, Kendall G, Woodward J (2012) Automating the packing heuristic design process with genetic programming. Evol Comput 20(1):63\u201389","journal-title":"Evol Comput"},{"key":"9968_CR5","unstructured":"Christofides N (1976) Worst-case analysis of a new heuristic for the travelling salesman problem Carnegie-Mellon Univ Pittsburgh Pa Management Sciences Research Group"},{"key":"9968_CR6","doi-asserted-by":"crossref","unstructured":"Duflo G, Kieffer E, Brust MR, Danoy G, Bouvry P (2019) A gp hyper-heuristic approach for generating tsp heuristics. In: IPDPSW\u201919: IEEE international parallel and distributed processing symposium workshops, pp 521\u2013529","DOI":"10.1109\/IPDPSW.2019.00094"},{"key":"9968_CR7","doi-asserted-by":"publisher","DOI":"10.1016\/j.asoc.2021.107606","volume":"110","author":"M Dumi\u0107","year":"2021","unstructured":"Dumi\u0107 M, Jakobovi\u0107 D (2021) Ensembles of priority rules for resource constrained project scheduling problem. Appl Soft Comput 110:107606","journal-title":"Appl Soft Comput"},{"key":"9968_CR8","doi-asserted-by":"publisher","first-page":"959","DOI":"10.1007\/s10732-019-09416-x","volume":"25","author":"M Durasevi\u0107","year":"2019","unstructured":"Durasevi\u0107 M, Jakobovi\u0107 D (2019) Creating dispatching rules by simple ensemble combination. J Heurist 25:959\u20131013","journal-title":"J Heurist"},{"key":"9968_CR9","doi-asserted-by":"publisher","first-page":"419","DOI":"10.1016\/j.asoc.2016.07.025","volume":"48","author":"M Durasevi\u0107","year":"2016","unstructured":"Durasevi\u0107 M, Jakobovi\u0107 D, Kne\u017eevi\u0107 K (2016) Adaptive scheduling on unrelated machines with genetic programming. Appl Soft Comput 48:419\u2013430","journal-title":"Appl Soft Comput"},{"key":"9968_CR10","doi-asserted-by":"publisher","DOI":"10.1016\/j.engappai.2023.106096","volume":"122","author":"M Durasevi\u0107","year":"2023","unstructured":"Durasevi\u0107 M, Gil-Gala FJ, Planini\u0107 L, Jakobovi\u0107 D (2023) Collaboration methods for ensembles of dispatching rules for the dynamic unrelated machines environment. Eng Appl Artific Intell 122:106096","journal-title":"Eng Appl Artific Intell"},{"key":"9968_CR11","doi-asserted-by":"publisher","DOI":"10.1016\/j.swevo.2023.101318","volume":"80","author":"M Durasevi\u0107","year":"2023","unstructured":"Durasevi\u0107 M, Gil-Gala FJ, Jakobovi\u0107 D, Coello-Coello CA (2023) Combining single objective dispatching rules into multi-objective ensembles for the dynamic unrelated machines environment. Swarm Evol Comput 80:101318","journal-title":"Swarm Evol Comput"},{"key":"9968_CR12","unstructured":"Freisleben B, Merz P (1996) A genetic local search algorithm for solving symmetric and asymmetric traveling salesman problems international conference on evolutionary computation"},{"key":"9968_CR13","doi-asserted-by":"crossref","unstructured":"Gil-Gala FJ, Durasevi\u0107 M, Sierra MR, Varela R (2022) Building heuristics and ensembles for the travel salesman problem. In: Ferr\u00e1ndez\u00a0Vicente JM et al (eds) Bio-inspired Systems and Applications: from robotics to ambient intelligence. proceedings of IWINAC 2022. Lecture Notes in Computer Science, vol 13259. Springer, Cham","DOI":"10.1007\/978-3-031-06527-9_13"},{"key":"9968_CR14","doi-asserted-by":"publisher","DOI":"10.1016\/j.asoc.2019.105782","volume":"85","author":"FJ Gil-Gala","year":"2019","unstructured":"Gil-Gala FJ, Menc\u00eda C, Sierra MR, Varela R (2019) Evolving priority rules for on-line scheduling of jobs on a single machine with variable capacity over time. Appl Soft Comput 85:105782","journal-title":"Appl Soft Comput"},{"key":"9968_CR15","doi-asserted-by":"publisher","first-page":"553","DOI":"10.1007\/s11047-020-09793-4","volume":"21","author":"FJ Gil-Gala","year":"2020","unstructured":"Gil-Gala FJ, Sierra MR, Menc\u00eda C, Varela R (2020) Combining hyper-heuristics to evolve ensembles of priority rules for on-line scheduling. Nat Comput 21:553\u2013563","journal-title":"Nat Comput"},{"key":"9968_CR16","doi-asserted-by":"publisher","DOI":"10.1016\/j.swevo.2021.100944","volume":"66","author":"FJ Gil-Gala","year":"2021","unstructured":"Gil-Gala FJ, Sierra MR, Menc\u00eda C, Varela R (2021) Genetic programming with local search to evolve priority rules for scheduling jobs on a machine with time-varying capacity. Swarm Evol Comput 66:100944","journal-title":"Swarm Evol Comput"},{"key":"9968_CR17","doi-asserted-by":"publisher","first-page":"340","DOI":"10.1016\/j.ins.2023.03.114","volume":"634","author":"FJ Gil-Gala","year":"2023","unstructured":"Gil-Gala FJ, Durasevi\u0107 M, Varela R, Jakobovi\u0107 D (2023) Ensembles of priority rules to solve one machine scheduling problem in real-time. Inf Sci 634:340\u2013358","journal-title":"Inf Sci"},{"issue":"4","key":"9968_CR18","doi-asserted-by":"publisher","first-page":"609","DOI":"10.1162\/EVCO_a_00183","volume":"24","author":"E Hart","year":"2016","unstructured":"Hart E, Sim K (2016) A hyper-heuristic ensemble method for static job-shop scheduling. Evol Comput 24(4):609\u2013635","journal-title":"Evol Comput"},{"key":"9968_CR19","doi-asserted-by":"crossref","unstructured":"Jia YH, Mei Y, Zhang M (2022) Learning heuristics with different representations for stochastic routing. IEEE Trans Cybern 53(5):3205\u20133219","DOI":"10.1109\/TCYB.2022.3169210"},{"key":"9968_CR20","unstructured":"Koza JR (1992) Genetic programming: on the programming of computers by means of natural selection. MIT Press"},{"issue":"2","key":"9968_CR21","doi-asserted-by":"publisher","first-page":"498","DOI":"10.1287\/opre.21.2.498","volume":"21","author":"S Link","year":"1973","unstructured":"Link S, Kernighan BW (1973) An effective heuristic algorithm for the traveling-salesman problem. Oper Res 21(2):498\u2013516","journal-title":"Oper Res"},{"issue":"7","key":"9968_CR22","doi-asserted-by":"publisher","first-page":"1743","DOI":"10.1109\/TCYB.2016.2556742","volume":"47","author":"M Mavrovouniotis","year":"2017","unstructured":"Mavrovouniotis M, M\u00fcller FM, Yang S (2017) Ant colony optimization with local search for dynamic traveling salesman problems. IEEE Trans Cybern 47(7):1743\u20131756","journal-title":"IEEE Trans Cybern"},{"issue":"3","key":"9968_CR23","doi-asserted-by":"publisher","first-page":"467","DOI":"10.1162\/evco_a_00230","volume":"27","author":"S Nguyen","year":"2019","unstructured":"Nguyen S, Mei Y, Xue B, Zhang M (2019) A hybrid genetic programming algorithm for automated design of dispatching rules. Evol Comput 27(3):467\u2013496","journal-title":"Evol Comput"},{"key":"9968_CR24","unstructured":"Optimal TSP LIB Solutions. http:\/\/comopt.ifi.uni-heidelberg.de\/software\/TSPLIB95\/STSP.html. Accessed 16 June 2022"},{"key":"9968_CR25","doi-asserted-by":"publisher","first-page":"72","DOI":"10.1016\/j.asoc.2017.11.020","volume":"63","author":"J Park","year":"2018","unstructured":"Park J, Mei Y, Nguyen S, Chen G, Zhang M (2018) An investigation of ensemble combination schemes for genetic programming based hyper-heuristic approaches to dynamic job shop scheduling. Appl Soft Comput 63:72\u201386","journal-title":"Appl Soft Comput"},{"key":"9968_CR26","unstructured":"Psaraftis HN (1998) Dynamic vehicle routing problems vehicle routing: methods and studies, pp 223\u2013248 North-Holland"},{"key":"9968_CR27","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1002\/net.21628","volume":"67","author":"HN Psaraftis","year":"2016","unstructured":"Psaraftis HN, Wen M, Kontovas CA (2016) Dynamic vehicle routing problems: three decades and counting. Networks 67:3\u201331","journal-title":"Networks"},{"key":"9968_CR28","doi-asserted-by":"crossref","unstructured":"Punnen AP (2007) The traveling salesman problem: applications, formulations and variations the traveling salesman problem and its variations. Springer US, pp 1\u201328","DOI":"10.1007\/0-306-48213-4_1"},{"key":"9968_CR29","doi-asserted-by":"publisher","DOI":"10.1016\/j.swevo.2022.101095","volume":"72","author":"E Singh","year":"2022","unstructured":"Singh E, Pillay N (2022) A study of ant-based pheromone spaces for generation constructive hyper-heuristics. Swarm Evol Comput 72:101095","journal-title":"Swarm Evol Comput"},{"key":"9968_CR30","unstructured":"TSP Test Data. http:\/\/www.math.uwaterloo.ca\/tsp\/data\/index.html. Accessed 1 Feb 2022"},{"key":"9968_CR31","doi-asserted-by":"crossref","unstructured":"Wang S, Mei Y, Zhang M (2019) Novel ensemble genetic programming hyper-heuristics for uncertain capacitated arc routing problem. In: Proceedings of the genetic and evolutionary computation conference","DOI":"10.1145\/3321707.3321797"},{"issue":"3","key":"9968_CR32","first-page":"1","volume":"1","author":"F Zhang","year":"2021","unstructured":"Zhang F, Mei Y, Nguyen S, Tan KC, Zhang M (2021) Multitask genetic programming-based generative hyperheuristics: a case study in dynamic scheduling. IEEE Trans Cybern 1(3):1\u201314","journal-title":"IEEE Trans Cybern"},{"key":"9968_CR33","doi-asserted-by":"crossref","unstructured":"Zhang F, Mei Y, Nguyen S, Tan KC, Zhang M (2022) Instance rotation based surrogate in genetic programming with brood recombination for dynamic job shop scheduling. IEEE Trans Evolut Comput 27(5):1192\u20131206","DOI":"10.1109\/TEVC.2022.3180693"}],"container-title":["Natural Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11047-023-09968-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s11047-023-09968-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11047-023-09968-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,10,31]],"date-time":"2023-10-31T17:19:16Z","timestamp":1698772756000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s11047-023-09968-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,10,25]]},"references-count":33,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2023,12]]}},"alternative-id":["9968"],"URL":"https:\/\/doi.org\/10.1007\/s11047-023-09968-9","relation":{},"ISSN":["1567-7818","1572-9796"],"issn-type":[{"value":"1567-7818","type":"print"},{"value":"1572-9796","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,10,25]]},"assertion":[{"value":"4 October 2023","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"25 October 2023","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"Not applicable.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Ethical approval"}},{"value":"The authors declare that they have no conflict of interest.","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}