{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,4]],"date-time":"2026-03-04T08:55:45Z","timestamp":1772614545203,"version":"3.50.1"},"reference-count":35,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2026,3,4]],"date-time":"2026-03-04T00:00:00Z","timestamp":1772582400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2026,3,4]],"date-time":"2026-03-04T00:00:00Z","timestamp":1772582400000},"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":[[2026,6]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>Many variants of the vehicle routing problem (VRP) pose significant computational challenges in logistics optimization, and improvement heuristics have emerged as effective tools for refining solutions found by local search methods and meta-heuristics. This paper introduces exact route-modifying improvement models (RMIMs). They are improvement models that aim to assemble high-quality solutions by selecting routes from a pool while allowing modifications to be made to the selected routes. These models can be embedded in a complete heuristic or used to post-optimize solutions produced by other methods. We evaluate our proposed models on vehicle routing problems with intra-route constraints, including the multi-trip VRP (MTVRP), the pickup and delivery problem with time windows (PDPTW), and the VRP with time windows (VRPTW). For the MTVRP, we propose a full matheuristic that uses a RMIM to achieve best known solutions for most benchmark instances for the MTVRP. By warm-starting with the current best known solutions from the literature the RMIMs improve many existing solutions for both the PDPTW and the VRPTW. These findings showcase the value of using RMIMs to enhance solutions to different types of VRPs.<\/jats:p>","DOI":"10.1007\/s10732-026-09583-8","type":"journal-article","created":{"date-parts":[[2026,3,4]],"date-time":"2026-03-04T05:22:55Z","timestamp":1772601775000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Mixed integer programs to improve solutions of vehicle routing problems with intra-route constraints"],"prefix":"10.1007","volume":"32","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-3964-5810","authenticated-orcid":false,"given":"Simen T.","family":"Vadseth","sequence":"first","affiliation":[]},{"given":"Henrik","family":"Andersson","sequence":"additional","affiliation":[]},{"given":"Jean-Fran\u00e7ois","family":"Cordeau","sequence":"additional","affiliation":[]},{"given":"Magnus","family":"St\u00e5lhane","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2026,3,4]]},"reference":[{"issue":"8","key":"9583_CR1","doi-asserted-by":"publisher","first-page":"1295","DOI":"10.3390\/electronics9081295","volume":"9","author":"M Ahmed","year":"2020","unstructured":"Ahmed, M., Seraj, R., Islam, S.M.S.: The k-means algorithm: a comprehensive survey and performance evaluation. Electronics 9(8), 1295 (2020)","journal-title":"Electronics"},{"issue":"1","key":"9583_CR2","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s10479-024-06295-9","volume":"343","author":"MA Akbay","year":"2024","unstructured":"Akbay, M.A., Blum, C., Kalayci, C.B.: Cmsa based on set covering models for packing and routing problems. Ann. Oper. Res. 343(1), 1\u201338 (2024)","journal-title":"Ann. Oper. Res."},{"issue":"6","key":"9583_CR3","doi-asserted-by":"publisher","first-page":"1561","DOI":"10.1016\/j.cor.2005.07.025","volume":"34","author":"GB Alvarenga","year":"2007","unstructured":"Alvarenga, G.B., Mateus, G.R., De Tomi, G.: A genetic and set partitioning two-phase approach for the vehicle routing problem with time windows. Computers & Operations Research 34(6), 1561\u20131584 (2007)","journal-title":"Computers & Operations Research"},{"issue":"3","key":"9583_CR4","doi-asserted-by":"publisher","first-page":"377","DOI":"10.1287\/ijoc.2016.0737","volume":"29","author":"C Archetti","year":"2017","unstructured":"Archetti, C., Boland, N., Speranza, M.G.: A matheuristic for the multivehicle inventory routing problem. INFORMS J. Comput. 29(3), 377\u2013387 (2017)","journal-title":"INFORMS J. Comput."},{"issue":"4","key":"9583_CR5","doi-asserted-by":"publisher","first-page":"223","DOI":"10.1007\/s13675-014-0030-7","volume":"2","author":"C Archetti","year":"2014","unstructured":"Archetti, C., Speranza, M.G.: A survey on matheuristics for routing problems. EURO Journal on Computational Optimization 2(4), 223\u2013246 (2014)","journal-title":"EURO Journal on Computational Optimization"},{"key":"9583_CR6","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1007\/s10479-018-2988-7","volume":"271","author":"D Cattaruzza","year":"2018","unstructured":"Cattaruzza, D., Absi, N., Feillet, D.: Vehicle routing problems with multiple trips. Ann. Oper. Res. 271, 127\u2013159 (2018)","journal-title":"Ann. Oper. Res."},{"issue":"2","key":"9583_CR7","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":"9583_CR8","first-page":"315","volume-title":"Combinatorial optimization","author":"N Christofides","year":"1979","unstructured":"Christofides, N., Mingozzi, A., Toth, P.: The vehicle routing problem. In: Toth, P. (ed.) Combinatorial optimization, pp. 315\u2013338. John Wiley & Sons Ltd, Chichester (1979)"},{"key":"9583_CR9","doi-asserted-by":"publisher","first-page":"279","DOI":"10.1007\/0-387-24977-X_9","volume-title":"Logistics systems: design and optimization","author":"J-F Cordeau","year":"2005","unstructured":"Cordeau, J.-F., Gendreau, M., Hertz, A., Laporte, G., Sormany, J.-S.: New heuristics for the vehicle routing problem. In: Langevin, A., Riopel, D. (eds.) Logistics systems: design and optimization, pp. 279\u2013297. Springer, US, Boston, MA (2005)"},{"key":"9583_CR10","doi-asserted-by":"publisher","first-page":"145","DOI":"10.1007\/0-387-23667-8_6","volume-title":"Metaheuristic optimization via memory and evolution: tabu search and scatter search","author":"J-F Cordeau","year":"2005","unstructured":"Cordeau, J.-F., Laporte, G.: Tabu search heuristics for the vehicle routing problem. In: Sharda, R., Vo\u00df, S., Rego, C., Alidaee, B. (eds.) Metaheuristic optimization via memory and evolution: tabu search and scatter search, pp. 145\u2013163. Springer, US, Boston, MA (2005)"},{"issue":"4","key":"9583_CR11","doi-asserted-by":"publisher","first-page":"626","DOI":"10.1287\/opre.42.4.626","volume":"42","author":"ML Fisher","year":"1994","unstructured":"Fisher, M.L.: Optimal solution of vehicle routing problems using minimum k-trees. Oper. Res. 42(4), 626\u2013642 (1994)","journal-title":"Oper. Res."},{"key":"9583_CR12","unstructured":"Gehring, H., Homberger, J.: A parallel hybrid evolutionary metaheuristic for the vehicle routing problem with time windows. In Proceedings of EUROGEN99, 2, 57\u201364, Berlin. Springer (1999)"},{"issue":"4","key":"9583_CR13","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."},{"issue":"2","key":"9583_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":"9583_CR15","doi-asserted-by":"crossref","unstructured":"Li, H., Lim, A.: A metaheuristic for the pickup and delivery problem with time windows. In Proceedings 13th IEEE International Conference on Tools with Artificial Intelligence. ICTAI 2001, pages 160\u2013167. IEEE (2001)","DOI":"10.1109\/ICTAI.2001.974461"},{"issue":"2","key":"9583_CR16","doi-asserted-by":"publisher","first-page":"478","DOI":"10.1016\/j.ejor.2021.05.037","volume":"298","author":"EG Manousakis","year":"2022","unstructured":"Manousakis, E.G., Kasapidis, G.A., Kiranoudis, C.T., Zachariadis, E.E.: An infeasible space exploring matheuristic for the production routing problem. Eur. J. Oper. Res. 298(2), 478\u2013495 (2022)","journal-title":"Eur. J. Oper. Res."},{"issue":"1\u20133","key":"9583_CR17","doi-asserted-by":"publisher","first-page":"69","DOI":"10.1016\/S0166-218X(03)00434-7","volume":"133","author":"RJ Petch","year":"2003","unstructured":"Petch, R.J., Salhi, S.: A multi-phase constructive heuristic for the vehicle routing problem with multiple trips. Discret. Appl. Math. 133(1\u20133), 69\u201392 (2003)","journal-title":"Discret. Appl. Math."},{"issue":"8","key":"9583_CR18","doi-asserted-by":"publisher","first-page":"2403","DOI":"10.1016\/j.cor.2005.09.012","volume":"34","author":"D Pisinger","year":"2007","unstructured":"Pisinger, D., Ropke, S.: A general heuristic for vehicle routing problems. Computers & Operations Research 34(8), 2403\u20132435 (2007)","journal-title":"Computers & Operations Research"},{"key":"9583_CR19","doi-asserted-by":"publisher","first-page":"147","DOI":"10.1007\/BF02430370","volume":"1","author":"Y Rochat","year":"1995","unstructured":"Rochat, Y., Taillard, \u00c9.D.: Probabilistic diversification and intensification in local search for vehicle routing. Journal of Heuristics 1, 147\u2013167 (1995)","journal-title":"Journal of Heuristics"},{"issue":"3","key":"9583_CR20","doi-asserted-by":"publisher","first-page":"267","DOI":"10.1287\/trsc.1090.0272","volume":"43","author":"S Ropke","year":"2009","unstructured":"Ropke, S., Cordeau, J.-F.: Branch and cut and price for the pickup and delivery problem with time windows. Transp. Sci. 43(3), 267\u2013286 (2009)","journal-title":"Transp. Sci."},{"issue":"4","key":"9583_CR21","doi-asserted-by":"publisher","first-page":"258","DOI":"10.1002\/net.20177","volume":"49","author":"S Ropke","year":"2007","unstructured":"Ropke, S., Cordeau, J.-F., Laporte, G.: Models and branch-and-cut algorithms for pickup and delivery problems with time windows. Networks: An International Journal 49(4), 258\u2013272 (2007)","journal-title":"Networks: An International Journal"},{"key":"9583_CR22","doi-asserted-by":"publisher","first-page":"40","DOI":"10.1016\/j.ijpe.2017.06.033","volume":"193","author":"RA Russell","year":"2017","unstructured":"Russell, R.A.: Mathematical programming heuristics for the production routing problem. Int. J. Prod. Econ. 193, 40\u201349 (2017)","journal-title":"Int. J. Prod. Econ."},{"key":"9583_CR23","doi-asserted-by":"publisher","DOI":"10.1016\/j.cor.2020.105065","volume":"124","author":"CS Sartori","year":"2020","unstructured":"Sartori, C.S., Buriol, L.S.: A study on the pickup and delivery problem with time windows: matheuristics and new instances. Computers & Operations Research 124, 105065 (2020)","journal-title":"Computers & Operations Research"},{"issue":"3","key":"9583_CR24","doi-asserted-by":"publisher","first-page":"992","DOI":"10.1016\/j.ejor.2023.08.010","volume":"313","author":"J Sk\u00e5lnes","year":"2024","unstructured":"Sk\u00e5lnes, J., Ahmed, M.B., Hvattum, L.M., St\u00e5lhane, M.: New benchmark instances for the inventory routing problem. Eur. J. Oper. Res. 313(3), 992\u20131014 (2024)","journal-title":"Eur. J. Oper. Res."},{"key":"9583_CR25","doi-asserted-by":"publisher","DOI":"10.1016\/j.cor.2023.106353","volume":"159","author":"J Sk\u00e5lnes","year":"2023","unstructured":"Sk\u00e5lnes, J., Vadseth, S.T., Andersson, H., St\u00e5lhane, M.: A branch-and-cut embedded matheuristic for the inventory routing problem. Computers & Operations Research 159, 106353 (2023)","journal-title":"Computers & Operations Research"},{"issue":"2","key":"9583_CR26","doi-asserted-by":"publisher","first-page":"254","DOI":"10.1287\/opre.35.2.254","volume":"35","author":"MM Solomon","year":"1987","unstructured":"Solomon, M.M.: Algorithms for the vehicle routing and scheduling problems with time window constraints. Oper. Res. 35(2), 254\u2013265 (1987)","journal-title":"Oper. Res."},{"key":"9583_CR27","doi-asserted-by":"publisher","first-page":"114","DOI":"10.1016\/j.cor.2017.06.007","volume":"87","author":"O Solyal\u0131","year":"2017","unstructured":"Solyal\u0131, O., S\u00fcral, H.: A multi-phase heuristic for the production routing problem. Computers & Operations Research 87, 114\u2013124 (2017)","journal-title":"Computers & Operations Research"},{"issue":"10","key":"9583_CR28","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"},{"issue":"8","key":"9583_CR29","doi-asserted-by":"publisher","first-page":"1065","DOI":"10.1057\/jors.1996.133","volume":"47","author":"ED Taillard","year":"1996","unstructured":"Taillard, E.D., Laporte, G., Gendreau, M.: Vehicle routeing with multiple use of vehicles. Journal of the Operational Research Society 47(8), 1065\u20131070 (1996)","journal-title":"Journal of the Operational Research Society"},{"key":"9583_CR30","doi-asserted-by":"crossref","unstructured":"Toth, P., Vigo, D.: Vehicle Routing: Problems, Methods, and Applications. SIAM (2014)","DOI":"10.1137\/1.9781611973594"},{"issue":"3","key":"9583_CR31","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":"9583_CR32","doi-asserted-by":"crossref","unstructured":"Vadseth, S.\u00a0T., Andersson, H., St\u00e5lhane, M., Chitsaz, M.: A multi-start route improving matheuristic for the production routeing problem. International Journal of Production Research, 1\u201322 (2023)","DOI":"10.1080\/00207543.2022.2154402"},{"issue":"3","key":"9583_CR33","doi-asserted-by":"publisher","first-page":"480","DOI":"10.1016\/0377-2217(94)00064-J","volume":"86","author":"A Van Breedam","year":"1995","unstructured":"Van Breedam, A.: Improvement heuristics for the vehicle routing problem based on simulated annealing. Eur. J. Oper. Res. 86(3), 480\u2013490 (1995)","journal-title":"Eur. J. Oper. Res."},{"key":"9583_CR34","doi-asserted-by":"publisher","DOI":"10.1016\/j.cor.2021.105643","volume":"140","author":"T Vidal","year":"2022","unstructured":"Vidal, T.: Hybrid genetic search for the cvrp: open-source implementation and swap* neighborhood. Computers & Operations Research 140, 105643 (2022)","journal-title":"Computers & Operations Research"},{"issue":"3","key":"9583_CR35","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."}],"container-title":["Journal of Heuristics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10732-026-09583-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10732-026-09583-8","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10732-026-09583-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,3,4]],"date-time":"2026-03-04T05:22:59Z","timestamp":1772601779000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10732-026-09583-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,3,4]]},"references-count":35,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2026,6]]}},"alternative-id":["9583"],"URL":"https:\/\/doi.org\/10.1007\/s10732-026-09583-8","relation":{},"ISSN":["1381-1231","1572-9397"],"issn-type":[{"value":"1381-1231","type":"print"},{"value":"1572-9397","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,3,4]]},"assertion":[{"value":"22 August 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"1 September 2025","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"29 January 2026","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"4 March 2026","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors have no competing interests to declare that are relevant to the content of this article.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing interests"}}],"article-number":"13"}}