{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,31]],"date-time":"2025-10-31T20:57:44Z","timestamp":1761944264295,"version":"build-2065373602"},"reference-count":21,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2025,7,19]],"date-time":"2025-07-19T00:00:00Z","timestamp":1752883200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2025,7,19]],"date-time":"2025-07-19T00:00:00Z","timestamp":1752883200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/100015528","name":"Universidad de la Laguna","doi-asserted-by":"crossref","id":[{"id":"10.13039\/100015528","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Comput Optim Appl"],"published-print":{"date-parts":[[2025,11]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>The Capacitated Vehicle Routing Problem with Planned Downtime introduced in this work is a generalization of the classical vehicle routing problem in which two sets of routes have to be jointly designed: one set considering that all the vehicles of the fleet are available, and another set that considers the scheduled unavailability of a vehicle. Besides routing cost minimization, it is also intended that the routes for the two cases (when all vehicles are available and when one is missing) are as similar as possible in order to reduce the impact on the customers. In this paper, we formally define the problem, propose two mixed integer programming models for it, one of them based on bilevel programming, and devise exact branch-and-cut algorithms based on those models. The algorithms are first compared, and then the most efficient one is tested on different benchmark instances with up to 40 nodes and 5 vehicles.<\/jats:p>","DOI":"10.1007\/s10589-025-00713-9","type":"journal-article","created":{"date-parts":[[2025,7,19]],"date-time":"2025-07-19T08:57:22Z","timestamp":1752915442000},"page":"655-681","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["The Capacitated Vehicle Routing Problem with Planned Downtime"],"prefix":"10.1007","volume":"92","author":[{"given":"Mercedes","family":"Landete","sequence":"first","affiliation":[]},{"given":"Marina","family":"Leal","sequence":"additional","affiliation":[]},{"given":"Juan Francisco","family":"Monge","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4877-733X","authenticated-orcid":false,"given":"Inmaculada","family":"Rodr\u00edguez-Mart\u00edn","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2025,7,19]]},"reference":[{"issue":"1","key":"713_CR1","doi-asserted-by":"publisher","first-page":"228","DOI":"10.1287\/opre.1100.0875","volume":"59","author":"R Baldacci","year":"2011","unstructured":"Baldacci, R., Bartolini, E., Mingozzi, A., Valletta, A.: An exact algorithm for the period routing problem. Oper. Res. 59(1), 228\u2013241 (2011)","journal-title":"Oper. Res."},{"key":"713_CR2","doi-asserted-by":"crossref","unstructured":"Bektas, T., Repoussis, P.P., Tarantilis, C.D.: Dynamic vehicle routing problems. In: Toth, P., Vigo, D. (eds.) Vehicle routing: problems, methods, and applications, chapter\u00a011, pp. 299\u2013347. SIAM, Philadelphia, (2014)","DOI":"10.1137\/1.9781611973594.ch11"},{"issue":"1","key":"713_CR3","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1002\/net.3230040106","volume":"4","author":"EJ Beltrami","year":"1974","unstructured":"Beltrami, E.J., Bodin, L.D.: Networks and vehicle routing for municipal waste collection. Networks 4(1), 65\u201394 (1974)","journal-title":"Networks"},{"issue":"1","key":"713_CR4","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."},{"key":"713_CR5","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s11750-018-0469-4","volume":"26","author":"R Eglese","year":"2018","unstructured":"Eglese, R., Zambirinis, S.: Disruption management in vehicle routing and scheduling for road freight transport: a review. TOP 26, 1\u201317 (2018)","journal-title":"TOP"},{"issue":"4","key":"713_CR6","doi-asserted-by":"publisher","first-page":"258","DOI":"10.1002\/net.20209","volume":"50","author":"H Hern\u00e1ndez-P\u00e9rez","year":"2007","unstructured":"Hern\u00e1ndez-P\u00e9rez, H., Salazar-Gonz\u00e1lez, J.J.: The one-commodity pickup-and-delivery traveling salesman problem: Inequalities and algorithms. Networks 50(4), 258\u2013272 (2007)","journal-title":"Networks"},{"key":"713_CR7","doi-asserted-by":"publisher","first-page":"100007","DOI":"10.1016\/j.ejco.2021.100007","volume":"9","author":"T Kleinert","year":"2021","unstructured":"Kleinert, T., Labb\u00e9, M., Ljubi\u0107, I., Schmidt, M.: A survey on mixed-integer programming techniques in bilevel optimization. EURO J. Comput. Optim. 9, 100007 (2021)","journal-title":"EURO J. Comput. Optim."},{"key":"713_CR8","doi-asserted-by":"publisher","first-page":"419","DOI":"10.1016\/j.tre.2008.09.002","volume":"45","author":"J-Q Li","year":"2009","unstructured":"Li, J.-Q., Borenstein, D., Mirchandani, P.B.: A lagrangian heuristic for the real-time vehicle rescheduling problem. Transp. Res. Part E 45, 419\u2013433 (2009)","journal-title":"Transp. Res. Part E"},{"issue":"3","key":"713_CR9","doi-asserted-by":"publisher","first-page":"711","DOI":"10.1016\/j.ejor.2007.12.037","volume":"194","author":"J-Q Li","year":"2009","unstructured":"Li, J.-Q., Mirchandani, P.B., Borenstein, D.: Real-time vehicle rerouting problems with time windows. Eur. J. Oper. Res. 194(3), 711\u2013727 (2009)","journal-title":"Eur. J. Oper. Res."},{"key":"713_CR10","doi-asserted-by":"publisher","first-page":"423","DOI":"10.1007\/s10107-003-0481-8","volume":"100","author":"J Lysgaard","year":"2004","unstructured":"Lysgaard, J., Letchford, A., Eglese, R.: A new branch-and-cut algorithm for the capacitated vehicle routing problem. Math. Programm. Ser. A 100, 423\u2013445 (2004)","journal-title":"Math. Programm. Ser. A"},{"key":"713_CR11","doi-asserted-by":"publisher","first-page":"555","DOI":"10.1007\/s10898-006-9094-0","volume":"38","author":"Y Marinakis","year":"2007","unstructured":"Marinakis, Y., Migdalas, A., Pardalos, P.M.: A new bilevel formulation for the vehicle routing problem and a solution method using a genetic algorithm. J. Global Optim. 38, 555\u2013580 (2007)","journal-title":"J. Global Optim."},{"issue":"6","key":"713_CR12","doi-asserted-by":"publisher","first-page":"1325","DOI":"10.1111\/itor.12346","volume":"24","author":"M Monroy-Licht","year":"2017","unstructured":"Monroy-Licht, M., Amaya, C.A., Langevin, A., Rousseau, L.-M.: The rescheduling arc routing problem. Int. Trans. Oper. Res. 24(6), 1325\u20131346 (2017)","journal-title":"Int. Trans. Oper. Res."},{"key":"713_CR13","doi-asserted-by":"crossref","unstructured":"Mor, A., Speranza, M.G.: Vehicle routing problems over time: a survey. 4OR, 18, 06 (2020)","DOI":"10.1007\/s10288-020-00433-2"},{"issue":"4","key":"713_CR14","doi-asserted-by":"publisher","first-page":"742","DOI":"10.1057\/jors.2010.19","volume":"62","author":"Q Mu","year":"2011","unstructured":"Mu, Q., Fu, Z., Lysgaard, J., Eglese, R.: Disruption management of the vehicle routing problem with vehicle breakdown. J. Oper. Res. Soc. 62(4), 742\u2013749 (2011)","journal-title":"J. Oper. Res. Soc."},{"key":"713_CR15","doi-asserted-by":"crossref","unstructured":"Naddef, D., Rinaldi, G.: Branch-and-cut algorithms for the capacitated VRP. In: Toth, P., Vigo, D. (eds.) The Vehicle Routing Problem, chapter\u00a03, pp. 53\u201384. SIAM, Philadelphia (2002)","DOI":"10.1137\/1.9780898718515.ch3"},{"key":"713_CR16","doi-asserted-by":"publisher","first-page":"107604","DOI":"10.1016\/j.cie.2021.107604","volume":"160","author":"BH Ojeda Rios","year":"2021","unstructured":"Ojeda Rios, B.H., Xavier, E.C., Miyazawa, F.K., Amorim, P., Curcio, E., Santos, M.J.: Recent dynamic vehicle routing problems: a survey. Comput. Industr. Eng. 160, 107604 (2021)","journal-title":"Comput. Industr. Eng."},{"key":"713_CR17","doi-asserted-by":"publisher","first-page":"60","DOI":"10.1137\/1033004","volume":"33","author":"MW Padberg","year":"1991","unstructured":"Padberg, M.W., Rinaldi, G.: A branch-and-cut algorithm for the resolution of large-scale symmetric traveling salesman problems. SIAM Rev. 33, 60\u2013100 (1991)","journal-title":"SIAM Rev."},{"issue":"1","key":"713_CR18","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.ejor.2012.08.015","volume":"225","author":"V Pillac","year":"2013","unstructured":"Pillac, V., Gendreau, M., Gu\u00e9ret, C., Medaglia, A.L.: A review of dynamic vehicle routing problems. Eur. J. Oper. Res. 225(1), 1\u201311 (2013)","journal-title":"Eur. J. Oper. Res."},{"issue":"1","key":"713_CR19","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1002\/net.21628","volume":"67","author":"HN Psaraftis","year":"2016","unstructured":"Psaraftis, H.N., Wen, M., Kontovas, C.A.: Dynamic vehicle routing problems: three decades and counting. Networks 67(1), 3\u201331 (2016)","journal-title":"Networks"},{"key":"713_CR20","doi-asserted-by":"publisher","first-page":"468","DOI":"10.1016\/j.trb.2022.11.004","volume":"166","author":"I Rodrguez-Martn","year":"2022","unstructured":"Rodr\u00edguez-Mart\u00edn, I., Yaman, H.: Periodic vehicle routing problem with driver consistency and service time optimization. Transp. Res. B Methodol. 166, 468\u2013484 (2022)","journal-title":"Transportation Research Part B: Methodological"},{"key":"713_CR21","doi-asserted-by":"crossref","unstructured":"Toth, P., Vigo, D.: (eds.) Vehicle routing: problems, methods, and applications. MOS-SIAM Series on Optimization. Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, USA, second edition, (2014)","DOI":"10.1137\/1.9781611973594"}],"container-title":["Computational Optimization and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10589-025-00713-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10589-025-00713-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10589-025-00713-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,31]],"date-time":"2025-10-31T20:55:14Z","timestamp":1761944114000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10589-025-00713-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,7,19]]},"references-count":21,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2025,11]]}},"alternative-id":["713"],"URL":"https:\/\/doi.org\/10.1007\/s10589-025-00713-9","relation":{},"ISSN":["0926-6003","1573-2894"],"issn-type":[{"type":"print","value":"0926-6003"},{"type":"electronic","value":"1573-2894"}],"subject":[],"published":{"date-parts":[[2025,7,19]]},"assertion":[{"value":"9 June 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"26 June 2025","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"19 July 2025","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}