{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,19]],"date-time":"2026-01-19T10:25:41Z","timestamp":1768818341456,"version":"3.49.0"},"reference-count":28,"publisher":"Springer Science and Business Media LLC","issue":"5-6","license":[{"start":{"date-parts":[[2022,10,15]],"date-time":"2022-10-15T00:00:00Z","timestamp":1665792000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,10,15]],"date-time":"2022-10-15T00:00:00Z","timestamp":1665792000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100005416","name":"Norges Forskningsr\u00e5d","doi-asserted-by":"publisher","award":["263031"],"award-info":[{"award-number":["263031"]}],"id":[{"id":"10.13039\/501100005416","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Heuristics"],"published-print":{"date-parts":[[2022,12]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>The Capacitated Vehicle Routing Problem (CVRP) has been subject to intense research efforts for more than sixty years. Yet, significant algorithmic improvements are still being made. The most competitive heuristic solution algorithms of today utilize, and often combine, strategies and elements from evolutionary algorithms, local search, and ruin-and-recreate based large neighborhood search. In this paper we propose a new hybrid metaheuristic for the CVRP, where the education phase of the hybrid genetic search (HGS) algorithm proposed by (Vidal Hybrid Genetic Search for the CVRP: Open-Source Implementation and SWAP* Neighborhood 2020) is extended by applying large neighborhood search (LNS). By performing a series of computational experiments, we attempt to answer the following research questions: 1) Is it possible to gain performance by adding LNS as a component in the education phase of HGS? 2) How does the addition of LNS change the relative importance of the local search neighborhoods of HGS? 3) What is the effect of devoting computational efforts to the creation of an elite solution in the initial population of HGS? Through a set of computational experiments we answer these research questions, while at the same time obtaining a good configuration of global parameter settings for the proposed heuristic. Testing the heuristic on benchmark instances from the literature with limited computing time, it outperforms existing algorithms, both in terms of the final gap and the primal integral.<\/jats:p>","DOI":"10.1007\/s10732-022-09500-9","type":"journal-article","created":{"date-parts":[[2022,10,15]],"date-time":"2022-10-15T10:02:38Z","timestamp":1665828158000},"page":"653-697","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":9,"title":["Combining hybrid genetic search with ruin-and-recreate for solving the capacitated vehicle routing problem"],"prefix":"10.1007","volume":"28","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-7529-7481","authenticated-orcid":false,"given":"Martin","family":"Simensen","sequence":"first","affiliation":[]},{"given":"Geir","family":"Hasle","sequence":"additional","affiliation":[]},{"given":"Magnus","family":"St\u00e5lhane","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,10,15]]},"reference":[{"key":"9500_CR1","doi-asserted-by":"publisher","first-page":"32","DOI":"10.1016\/j.cor.2019.01.002","volume":"105","author":"F Arnold","year":"2019","unstructured":"Arnold, F., S\u00f6rensen, K.: Knowledge-guided local search for the vehicle routing problem. Computers & Operations Research 105, 32\u201346 (2019)","journal-title":"Computers & Operations Research"},{"key":"9500_CR2","doi-asserted-by":"publisher","first-page":"32","DOI":"10.1016\/j.cor.2019.03.006","volume":"107","author":"F Arnold","year":"2019","unstructured":"Arnold, F., Gendreau, M., S\u00f6rensen, K.: Efficiently solving very large-scale routing problems. Computers & Operations Research 107, 32\u201342 (2019)","journal-title":"Computers & Operations Research"},{"issue":"9","key":"9500_CR3","doi-asserted-by":"publisher","first-page":"815","DOI":"10.1057\/jors.1981.159","volume":"32","author":"J Baxter","year":"1981","unstructured":"Baxter, J.: Local optima avoidance in depot location. Journal of the Operational Research Society 32(9), 815\u2013819 (1981)","journal-title":"Journal of the Operational Research Society"},{"issue":"6","key":"9500_CR4","doi-asserted-by":"publisher","first-page":"611","DOI":"10.1016\/j.orl.2013.08.007","volume":"41","author":"T Berthold","year":"2013","unstructured":"Berthold, T.: Measuring the impact of primal heuristics. Oper. Res. Lett. 41(6), 611\u2013614 (2013)","journal-title":"Oper. Res. Lett."},{"issue":"2","key":"9500_CR5","doi-asserted-by":"publisher","first-page":"417","DOI":"10.1287\/trsc.2019.0914","volume":"54","author":"J Christiaens","year":"2020","unstructured":"Christiaens, J., Vanden Berghe, G.: Slack Induction by String Removals for Vehicle Routing Problems. Transp. Sci. 54(2), 417\u2013433 (2020)","journal-title":"Transp. Sci."},{"key":"9500_CR6","unstructured":"CVRPLIB: Capacitated vehicle routing problem library. Retrieved from http:\/\/vrp.atd-lab.inf.puc-rio.br\/index.php\/en\/. Accessed 8. July 2021 (2021)"},{"issue":"1","key":"9500_CR7","doi-asserted-by":"publisher","first-page":"80","DOI":"10.1287\/mnsc.6.1.80","volume":"6","author":"GB Dantzig","year":"1959","unstructured":"Dantzig, G.B., Ramser, J.H.: The Truck Dispatching Problem. Manage. Sci. 6(1), 80\u201391 (1959)","journal-title":"Manage. Sci."},{"issue":"4","key":"9500_CR8","doi-asserted-by":"publisher","first-page":"1472","DOI":"10.1016\/j.cie.2009.05.009","volume":"57","author":"B Eksioglu","year":"2009","unstructured":"Eksioglu, B., Vural, A.V., Reisman, A.: The vehicle routing problem: A taxonomic review. Computers & Industrial Engineering 57(4), 1472\u20131483 (2009)","journal-title":"Computers & Industrial Engineering"},{"issue":"5","key":"9500_CR9","doi-asserted-by":"publisher","first-page":"533","DOI":"10.1016\/0305-0548(86)90048-1","volume":"13","author":"F Glover","year":"1986","unstructured":"Glover, F.: Future paths for integer programming and links to artificial intelligence. Computers & Operations Research 13(5), 533\u2013549 (1986)","journal-title":"Computers & Operations Research"},{"issue":"3","key":"9500_CR10","doi-asserted-by":"publisher","first-page":"190","DOI":"10.1287\/ijoc.1.3.190","volume":"1","author":"F Glover","year":"1989","unstructured":"Glover, F.: Tabu search-part i. ORSA J. Comput. 1(3), 190\u2013206 (1989)","journal-title":"ORSA J. Comput."},{"issue":"4598","key":"9500_CR11","doi-asserted-by":"publisher","first-page":"671","DOI":"10.1126\/science.220.4598.671","volume":"220","author":"S Kirkpatrick","year":"1983","unstructured":"Kirkpatrick, S., Gelatt, C.D., Vecchi, M.P.: Optimization by Simulated Annealing. Science 220(4598), 671\u2013680 (1983)","journal-title":"Science"},{"issue":"4","key":"9500_CR12","doi-asserted-by":"publisher","first-page":"408","DOI":"10.1287\/trsc.1090.0301","volume":"43","author":"G Laporte","year":"2009","unstructured":"Laporte, G.: Fifty years of vehicle routing. Transp. Sci. 43(4), 408\u2013416 (2009)","journal-title":"Transp. Sci."},{"key":"9500_CR13","doi-asserted-by":"publisher","first-page":"87","DOI":"10.1137\/1.9781611973594.ch4","volume-title":"Vehicle Routing: Problems, Methods, and Applications","author":"G Laporte","year":"2014","unstructured":"Laporte, G., Ropke, S., Vidal, T.: Chapter 4: Heuristics for the vehicle routing problem. In: Vehicle Routing: Problems, Methods, and Applications, pp. 87\u2013116. SIAM, Second Edition (2014)"},{"issue":"2","key":"9500_CR14","doi-asserted-by":"publisher","first-page":"221","DOI":"10.1002\/net.3230110211","volume":"11","author":"JK Lenstra","year":"1981","unstructured":"Lenstra, J.K., Kan, A.R.: Complexity of vehicle routing and scheduling problems. Networks 11(2), 221\u2013227 (1981)","journal-title":"Networks"},{"key":"9500_CR15","unstructured":"Oliver, I., Smith, D., Holland, J.R.: Study of permutation crossover operators on the traveling salesman problem. In: Genetic algorithms and their applications: proceedings of the second International Conference on Genetic Algorithms: July 28-31, 1987 at the Massachusetts Institute of Technology, Cambridge, MA, Hillsdale, NJ: L. Erlhaum Associates, 1987 (1987)"},{"key":"9500_CR16","unstructured":"PassMark Software: CPU benchmarks. Retrieved from https:\/\/www.cpubenchmark.net\/. Accessed 13. April 2021 (2021)"},{"issue":"1","key":"9500_CR17","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1007\/s12532-016-0108-8","volume":"9","author":"D Pecin","year":"2017","unstructured":"Pecin, D., Pessoa, A., Poggi, M., Uchoa, E.: Improved branch-cut-and-price for capacitated vehicle routing. Math. Program. Comput. 9(1), 61\u2013100 (2017)","journal-title":"Math. Program. Comput."},{"issue":"1","key":"9500_CR18","doi-asserted-by":"publisher","first-page":"483","DOI":"10.1007\/s10107-020-01523-z","volume":"183","author":"A Pessoa","year":"2020","unstructured":"Pessoa, A., Sadykov, R., Uchoa, E., Vanderbeck, F.: A generic exact solver for vehicle routing and related problems. Math. Program. 183(1), 483\u2013523 (2020)","journal-title":"Math. Program."},{"issue":"12","key":"9500_CR19","doi-asserted-by":"publisher","first-page":"1985","DOI":"10.1016\/S0305-0548(03)00158-8","volume":"31","author":"C Prins","year":"2004","unstructured":"Prins, C.: A simple and effective evolutionary algorithm for the vehicle routing problem. Computers & Operations Research 31(12), 1985\u20132002 (2004)","journal-title":"Computers & Operations Research"},{"issue":"10","key":"9500_CR20","doi-asserted-by":"publisher","first-page":"2519","DOI":"10.1016\/j.cor.2013.01.013","volume":"40","author":"A Subramanian","year":"2013","unstructured":"Subramanian, A., Uchoa, E., Ochi, L.S.: A hybrid algorithm for a class of vehicle routing problems. Computers & Operations Research 40(10), 2519\u20132531 (2013)","journal-title":"Computers & Operations Research"},{"key":"9500_CR21","doi-asserted-by":"crossref","unstructured":"Toth, P., Vigo, D.: Vehicle Routing: Problems, Methods, and Applications. Society for Industrial and Applied Mathematics (2014)","DOI":"10.1137\/1.9781611973594"},{"issue":"3","key":"9500_CR22","doi-asserted-by":"publisher","first-page":"845","DOI":"10.1016\/j.ejor.2016.08.012","volume":"257","author":"E Uchoa","year":"2017","unstructured":"Uchoa, E., Pecin, D., Pessoa, A., Poggi, M., Vidal, T., Subramanian, A.: New benchmark instances for the Capacitated Vehicle Routing Problem. Eur. J. Oper. Res. 257(3), 845\u2013858 (2017)","journal-title":"Eur. J. Oper. Res."},{"key":"9500_CR23","doi-asserted-by":"publisher","first-page":"40","DOI":"10.1016\/j.cor.2015.11.012","volume":"69","author":"T Vidal","year":"2016","unstructured":"Vidal, T.: Split algorithm in $$O(n)$$ for the capacitated vehicle routing problem. Computers & Operations Research 69, 40\u201347 (2016)","journal-title":"Computers & Operations Research"},{"key":"9500_CR24","unstructured":"Vidal, T.: Hybrid Genetic Search for the CVRP: Open-Source Implementation and SWAP* Neighborhood. arXiv preprint arXiv:2012.10384 (2020)"},{"issue":"3","key":"9500_CR25","doi-asserted-by":"publisher","first-page":"611","DOI":"10.1287\/opre.1120.1048","volume":"60","author":"T Vidal","year":"2012","unstructured":"Vidal, T., Crainic, T.G., Gendreau, M., Lahrichi, N., Rei, W.: A hybrid Genetic Algorithm for Multidepot and Periodic Vehicle Routing Problems. Oper. Res. 60(3), 611\u2013624 (2012)","journal-title":"Oper. Res."},{"issue":"1","key":"9500_CR26","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.ejor.2013.02.053","volume":"231","author":"T Vidal","year":"2013","unstructured":"Vidal, T., Crainic, T.G., Gendreau, M., Prins, C.: Heuristics for multi-attribute vehicle routing problems: A survey and synthesis. Eur. J. Oper. Res. 231(1), 1\u201321 (2013)","journal-title":"Eur. J. Oper. Res."},{"key":"9500_CR27","doi-asserted-by":"crossref","unstructured":"Voudouris, C., Tsang, E.P.: Guided Local Search. In: Handbook of Metaheuristics, Springer, pp 185\u2013218 (2003)","DOI":"10.1007\/0-306-48056-5_7"},{"key":"9500_CR28","doi-asserted-by":"crossref","unstructured":"Wilcoxon, F.: Individual comparisons by ranking methods. biometrics bulletin 1, 6: 80\u201383. URL http:\/\/www.jstor.org\/stable\/3001968 (1945)","DOI":"10.2307\/3001968"}],"container-title":["Journal of Heuristics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10732-022-09500-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10732-022-09500-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10732-022-09500-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,11,3]],"date-time":"2022-11-03T09:20:07Z","timestamp":1667467207000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10732-022-09500-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,10,15]]},"references-count":28,"journal-issue":{"issue":"5-6","published-print":{"date-parts":[[2022,12]]}},"alternative-id":["9500"],"URL":"https:\/\/doi.org\/10.1007\/s10732-022-09500-9","relation":{},"ISSN":["1381-1231","1572-9397"],"issn-type":[{"value":"1381-1231","type":"print"},{"value":"1572-9397","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,10,15]]},"assertion":[{"value":"7 September 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"10 May 2022","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"24 May 2022","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"15 October 2022","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}