{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,8]],"date-time":"2026-02-08T08:35:49Z","timestamp":1770539749158,"version":"3.49.0"},"reference-count":45,"publisher":"Springer Science and Business Media LLC","issue":"9","license":[{"start":{"date-parts":[[2022,2,4]],"date-time":"2022-02-04T00:00:00Z","timestamp":1643932800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,2,4]],"date-time":"2022-02-04T00:00:00Z","timestamp":1643932800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Optim Lett"],"published-print":{"date-parts":[[2022,12]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>In this paper, we study the multi-depot <jats:italic>k<\/jats:italic>-traveling repairman problem. This problem extends the traditional traveling repairman problem to the multi-depot case. Its objective, similar to the single depot variant, is the minimization of the sum of the arrival times to customers. We propose two distinct formulations to model the problem, obtained on layered graphs. In order to find feasible solutions for the largest instances, we propose a hybrid genetic algorithm where initial solutions are built using a splitting heuristic and a local search is embedded into the genetic algorithm. The efficiency of the mathematical formulations and of the solution approach are investigated through computational experiments. The proposed models are scalable enough to solve instances up to 240 customers.<\/jats:p>","DOI":"10.1007\/s11590-021-01845-7","type":"journal-article","created":{"date-parts":[[2022,2,4]],"date-time":"2022-02-04T16:21:31Z","timestamp":1643991691000},"page":"2681-2709","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":6,"title":["The multi-depot k-traveling repairman problem"],"prefix":"10.1007","volume":"16","author":[{"given":"Maria Elena","family":"Bruni","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3858-2571","authenticated-orcid":false,"given":"Sara","family":"Khodaparasti","sequence":"additional","affiliation":[]},{"given":"Iris","family":"Mart\u00ednez-Salazar","sequence":"additional","affiliation":[]},{"given":"Samuel","family":"Nucamendi-Guill\u00e9n","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,2,4]]},"reference":[{"issue":"2","key":"1845_CR1","first-page":"369","volume":"19","author":"F \u00c1ngel-Bello","year":"2019","unstructured":"\u00c1ngel-Bello, F., Cardona-Vald\u00e9s, Y., \u00c1lvarez, A.: Mixed integer formulations for the multiple minimum latency problem. Oper. Res. 19(2), 369\u2013398 (2019)","journal-title":"Oper. Res."},{"issue":"2","key":"1845_CR2","doi-asserted-by":"publisher","first-page":"81","DOI":"10.1002\/net.3230230202","volume":"23","author":"L Bianco","year":"1993","unstructured":"Bianco, L., Mingozzi, A., Ricciardelli, S.: The traveling salesman problem with cumulative costs. Networks 23(2), 81\u201391 (1993)","journal-title":"Networks"},{"key":"1845_CR3","doi-asserted-by":"crossref","unstructured":"Blum, A., Chalasani, P., Coppersmith, D., Pulleyblank, B., Raghavan, P., Sudan, M.: The minimum latency problem. In: Proceedings of the Twenty-sixth Annual ACM Symposium on Theory of Computing, pp. 163\u2013171 (1994)","DOI":"10.1145\/195058.195125"},{"key":"1845_CR4","first-page":"304","volume":"30","author":"M Bruni","year":"2018","unstructured":"Bruni, M., Beraldi, P., Khodaparasti, S.: A fast heuristic for routing in post-disaster humanitarian relief logistics. Transp. Res. Proc. 30, 304\u2013313 (2018)","journal-title":"Transp. Res. Proc."},{"key":"1845_CR5","doi-asserted-by":"publisher","first-page":"104854","DOI":"10.1016\/j.cor.2019.104854","volume":"115","author":"ME Bruni","year":"2020","unstructured":"Bruni, M.E., Beraldi, P., Khodaparasti, S.: A hybrid reactive grasp heuristic for the risk-averse k-traveling repairman problem with profits. Comput. Oper. Res. 115, 104854 (2020)","journal-title":"Comput. Oper. Res."},{"issue":"2","key":"1845_CR6","doi-asserted-by":"publisher","first-page":"586","DOI":"10.1016\/j.ejor.2004.08.017","volume":"169","author":"F Chu","year":"2006","unstructured":"Chu, F., Labadi, N., Prins, C.: A scatter search for the periodic capacitated arc routing problem. Eur. J. Oper. Res. 169(2), 586\u2013605 (2006)","journal-title":"Eur. J. Oper. Res."},{"key":"1845_CR7","doi-asserted-by":"crossref","unstructured":"Cordeau, J.F., Gendreau, M., Laporte, G.: A tabu search heuristic for periodic and multi-depot vehicle routing problems. Netw. Int. J. 30(2), 105\u2013119 (1997)","DOI":"10.1002\/(SICI)1097-0037(199709)30:2<105::AID-NET5>3.0.CO;2-G"},{"key":"1845_CR8","doi-asserted-by":"crossref","unstructured":"Fakcharoenphol, J., Harrelson, C., Rao, S.: The k-traveling repairmen problem. ACM Trans. Algo. (TALG) 3(4), 40-es (2007)","DOI":"10.1145\/1290672.1290677"},{"issue":"6","key":"1845_CR9","doi-asserted-by":"publisher","first-page":"1055","DOI":"10.1287\/opre.41.6.1055","volume":"41","author":"M Fischetti","year":"1993","unstructured":"Fischetti, M., Laporte, G., Martello, S.: The delivery man problem and cumulative matroids. Oper. Res. 41(6), 1055\u20131064 (1993)","journal-title":"Oper. Res."},{"issue":"5","key":"1845_CR10","doi-asserted-by":"publisher","first-page":"519","DOI":"10.1287\/mnsc.36.5.519","volume":"36","author":"R Fourer","year":"1990","unstructured":"Fourer, R., Gay, D.M., Kernighan, B.W.: A modeling language for mathematical programming. Manage. Sci. 36(5), 519\u2013554 (1990)","journal-title":"Manage. Sci."},{"key":"1845_CR11","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1016\/j.dam.2018.01.012","volume":"280","author":"DR Gaur","year":"2020","unstructured":"Gaur, D.R., Mudgal, A., Singh, R.R.: Improved approximation algorithms for cumulative vrp with stochastic demands. Discret. Appl. Math. 280, 133\u2013143 (2020)","journal-title":"Discret. Appl. Math."},{"key":"1845_CR12","doi-asserted-by":"crossref","unstructured":"Gaur, D.R., Singh, R.R.: Cumulative vehicle routing problem: a column generation approach. In: Conference on Algorithms and Discrete Applied Mathematics, pp. 262\u2013274. Springer (2015)","DOI":"10.1007\/978-3-319-14974-5_25"},{"key":"1845_CR13","doi-asserted-by":"publisher","first-page":"140","DOI":"10.1016\/j.dam.2016.05.030","volume":"228","author":"DR Gaur","year":"2017","unstructured":"Gaur, D.R., Singh, R.R.: A heuristic for cumulative vehicle routing using column generation. Disc. Appl. Math. 228, 140\u2013157 (2017)","journal-title":"Disc. Appl. Math."},{"key":"1845_CR14","unstructured":"Gurobi\u00a0Optimization, L.: Gurobi optimizer reference manual. gurobi optimization inc (2020)"},{"issue":"1","key":"1845_CR15","doi-asserted-by":"publisher","first-page":"66","DOI":"10.1038\/scientificamerican0792-66","volume":"267","author":"JH Holland","year":"1992","unstructured":"Holland, J.H.: Genetic algorithms. Sci. Am. 267(1), 66\u201373 (1992)","journal-title":"Sci. Am."},{"issue":"2","key":"1845_CR16","first-page":"293","volume":"5","author":"R Jothi","year":"2007","unstructured":"Jothi, R., Raghavachari, B.: Approximating the k-traveling repairman problem with repairtimes. J. Disc. Algo. 5(2), 293\u2013303 (2007)","journal-title":"J. Disc. Algo."},{"key":"1845_CR17","doi-asserted-by":"crossref","unstructured":"Kara, \u0130., Kara, B.Y., Yeti\u015f, M.K.: Cumulative vehicle routing problems. In-Teh (2008)","DOI":"10.5772\/5812"},{"issue":"2","key":"1845_CR18","doi-asserted-by":"publisher","first-page":"633","DOI":"10.1016\/j.cor.2012.08.020","volume":"40","author":"L Ke","year":"2013","unstructured":"Ke, L., Feng, Z.: A two-phase metaheuristic for the cumulative capacitated vehicle routing problem. Comput. Oper. Res. 40(2), 633\u2013638 (2013)","journal-title":"Comput. Oper. Res."},{"issue":"3","key":"1845_CR19","doi-asserted-by":"publisher","first-page":"671","DOI":"10.1007\/s11590-018-1376-1","volume":"14","author":"E Lalla-Ruiz","year":"2020","unstructured":"Lalla-Ruiz, E., Vo\u00df, S.: A popmusic approach for the multi-depot cumulative capacitated vehicle routing problem. Optim. Lett. 14(3), 671\u2013691 (2020)","journal-title":"Optim. Lett."},{"issue":"6","key":"1845_CR20","doi-asserted-by":"publisher","first-page":"753","DOI":"10.1002\/net.3230200605","volume":"20","author":"A Lucena","year":"1990","unstructured":"Lucena, A.: Time-dependent traveling salesman problem-the deliveryman case. Networks 20(6), 753\u2013763 (1990)","journal-title":"Networks"},{"issue":"1","key":"1845_CR21","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1016\/j.ejor.2013.09.014","volume":"234","author":"Z Luo","year":"2014","unstructured":"Luo, Z., Qin, H., Lim, A.: Branch-and-price-and-cut for the multiple traveling repairman problem with distance constraints. Eur. J. Oper. Res. 234(1), 49\u201360 (2014)","journal-title":"Eur. J. Oper. Res."},{"issue":"3","key":"1845_CR22","doi-asserted-by":"publisher","first-page":"800","DOI":"10.1016\/j.ejor.2013.08.032","volume":"236","author":"J Lysgaard","year":"2014","unstructured":"Lysgaard, J., W\u00f8hlk, S.: A branch-and-cut-and-price algorithm for the cumulative capacitated vehicle routing problem. Eur. J. Oper. Res. 236(3), 800\u2013810 (2014)","journal-title":"Eur. J. Oper. Res."},{"issue":"17","key":"1845_CR23","doi-asserted-by":"publisher","first-page":"3223","DOI":"10.1016\/j.dam.2008.05.009","volume":"156","author":"I M\u00e9ndez-D\u00edaz","year":"2008","unstructured":"M\u00e9ndez-D\u00edaz, I., Zabala, P., Lucena, A.: A new formulation for the traveling deliveryman problem. Disc. Appl. Math. 156(17), 3223\u20133237 (2008)","journal-title":"Disc. Appl. Math."},{"key":"1845_CR24","doi-asserted-by":"crossref","unstructured":"Mladenovi\u0107, N., Uro\u0161evi\u0107, D., Hanafi, S.: Variable neighborhood search for the travelling deliveryman problem. 4OR 11(1), 57\u201373 (2013)","DOI":"10.1007\/s10288-012-0212-1"},{"key":"1845_CR25","doi-asserted-by":"publisher","first-page":"115","DOI":"10.1016\/j.cie.2014.10.029","volume":"79","author":"JR Montoya-Torres","year":"2015","unstructured":"Montoya-Torres, J.R., Franco, J.L., Isaza, S.N., Jim\u00e9nez, H.F., Herazo-Padilla, N.: A literature review on the vehicle routing problem with multiple depots. Comput. Indus. Eng. 79, 115\u2013129 (2015)","journal-title":"Comput. Indus. Eng."},{"issue":"11","key":"1845_CR26","doi-asserted-by":"publisher","first-page":"1877","DOI":"10.1016\/j.cor.2009.06.014","volume":"37","author":"SU Ngueveu","year":"2010","unstructured":"Ngueveu, S.U., Prins, C., Calvo, R.W.: An effective memetic algorithm for the cumulative capacitated vehicle routing problem. Comput. Oper. Res. 37(11), 1877\u20131885 (2010)","journal-title":"Comput. Oper. Res."},{"key":"1845_CR27","doi-asserted-by":"publisher","first-page":"315","DOI":"10.1016\/j.eswa.2018.07.025","volume":"113","author":"S Nucamendi-Guill\u00e9n","year":"2018","unstructured":"Nucamendi-Guill\u00e9n, S., Angel-Bello, F., Mart\u00ednez-Salazar, I., Cordero-Franco, A.E.: The cumulative capacitated vehicle routing problem: new formulations and iterated greedy algorithms. Exp. Syst. Appl. 113, 315\u2013327 (2018)","journal-title":"Exp. Syst. Appl."},{"issue":"8","key":"1845_CR28","doi-asserted-by":"publisher","first-page":"1121","DOI":"10.1057\/jors.2015.113","volume":"67","author":"S Nucamendi-Guill\u00e9n","year":"2016","unstructured":"Nucamendi-Guill\u00e9n, S., Mart\u00ednez-Salazar, I., Angel-Bello, F., Moreno-Vega, J.M.: A mixed integer formulation and an efficient metaheuristic procedure for the k-travelling repairmen problem. J. Oper. Res. Soc. 67(8), 1121\u20131134 (2016)","journal-title":"J. Oper. Res. Soc."},{"issue":"10","key":"1845_CR29","doi-asserted-by":"publisher","first-page":"1321","DOI":"10.1080\/02331934.2013.841158","volume":"62","author":"FB Ozsoydan","year":"2013","unstructured":"Ozsoydan, F.B., Sipahioglu, A.: Heuristic solution approaches for the cumulative capacitated vehicle routing problem. Optimization 62(10), 1321\u20131340 (2013)","journal-title":"Optimization"},{"key":"1845_CR30","doi-asserted-by":"publisher","first-page":"102184","DOI":"10.1016\/j.tre.2020.102184","volume":"145","author":"G Perboli","year":"2021","unstructured":"Perboli, G., Brotcorne, L., Bruni, M.E., Rosano, M.: A new model for last-mile delivery and satellite depots management: the impact of the on-demand economy. Transp. Res. Part E Logist. Transp. Rev. 145, 102184 (2021)","journal-title":"Transp. Res. Part E Logist. Transp. Rev."},{"issue":"12","key":"1845_CR31","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. Comput. Oper. Res. 31(12), 1985\u20132002 (2004)","journal-title":"Comput. Oper. Res."},{"key":"1845_CR32","doi-asserted-by":"publisher","first-page":"179","DOI":"10.1016\/j.trc.2014.01.011","volume":"40","author":"C Prins","year":"2014","unstructured":"Prins, C., Lacomme, P., Prodhon, C.: Order-first split-second methods for vehicle routing problems: a review. Transp. Res. Part C Emerg. Technol. 40, 179\u2013200 (2014)","journal-title":"Transp. Res. Part C Emerg. Technol."},{"issue":"2","key":"1845_CR33","doi-asserted-by":"publisher","first-page":"103","DOI":"10.1080\/13675567.2019.1630374","volume":"23","author":"TRP Ramos","year":"2020","unstructured":"Ramos, T.R.P., Gomes, M.I., P\u00f3voa, A.P.B.: Multi-depot vehicle routing problem: a comparative study of alternative formulations. Int. J. Log. Res. Appl. 23(2), 103\u2013120 (2020)","journal-title":"Int. J. Log. Res. Appl."},{"issue":"3","key":"1845_CR34","doi-asserted-by":"publisher","first-page":"728","DOI":"10.1016\/j.cor.2011.05.005","volume":"39","author":"GM Ribeiro","year":"2012","unstructured":"Ribeiro, G.M., Laporte, G.: An adaptive large neighborhood search heuristic for the cumulative capacitated vehicle routing problem. Comput. Oper. Res. 39(3), 728\u2013735 (2012)","journal-title":"Comput. Oper. Res."},{"issue":"1","key":"1845_CR35","doi-asserted-by":"publisher","first-page":"159","DOI":"10.1007\/s10589-014-9713-5","volume":"61","author":"JC Rivera","year":"2015","unstructured":"Rivera, J.C., Afsar, H.M., Prins, C.: A multistart iterated local search for the multitrip cumulative capacitated vehicle routing problem. Comput. Optim. Appl. 61(1), 159\u2013187 (2015)","journal-title":"Comput. Optim. Appl."},{"issue":"1","key":"1845_CR36","doi-asserted-by":"publisher","first-page":"93","DOI":"10.1016\/j.ejor.2015.08.067","volume":"249","author":"JC Rivera","year":"2016","unstructured":"Rivera, J.C., Afsar, H.M., Prins, C.: Mathematical formulations and exact algorithm for the multitrip cumulative capacitated single-vehicle routing problem. Eur. J. Oper. Res. 249(1), 93\u2013104 (2016)","journal-title":"Eur. J. Oper. Res."},{"key":"1845_CR37","doi-asserted-by":"crossref","unstructured":"Salehipour, A., S\u00f6rensen, K., Goos, P., Br\u00e4ysy, O.: Efficient grasp+ vnd and grasp+ vns metaheuristics for the traveling repairman problem. 4OR 9(2), 189\u2013209 (2011)","DOI":"10.1007\/s10288-011-0153-0"},{"key":"1845_CR38","doi-asserted-by":"crossref","unstructured":"Sharma, R., Saini, S.: Heuristics and meta-heuristics based multiple depot vehicle routing problem: a review. In: 2020 International Conference on Electronics and Sustainable Communication Systems (ICESC), pp. 683\u2013689. IEEE (2020)","DOI":"10.1109\/ICESC48915.2020.9155814"},{"key":"1845_CR39","doi-asserted-by":"publisher","first-page":"162","DOI":"10.1016\/j.trb.2017.04.003","volume":"101","author":"JF Sze","year":"2017","unstructured":"Sze, J.F., Salhi, S., Wassan, N.: The cumulative capacitated vehicle routing problem with min-sum and min-max objectives: an effective hybridisation of adaptive variable neighbourhood search and large neighbourhood search. Transp. Res. Part B Methodol. 101, 162\u2013184 (2017)","journal-title":"Transp. Res. Part B Methodol."},{"key":"1845_CR40","doi-asserted-by":"publisher","first-page":"120","DOI":"10.1016\/j.cor.2014.11.006","volume":"56","author":"L Talarico","year":"2015","unstructured":"Talarico, L., Meisel, F., S\u00f6rensen, K.: Ambulance routing for disaster response with patient groups. Comput. Oper. Res. 56, 120\u2013133 (2015)","journal-title":"Comput. Oper. Res."},{"issue":"3","key":"1845_CR41","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":"1845_CR42","doi-asserted-by":"publisher","first-page":"475","DOI":"10.1016\/j.cor.2012.07.018","volume":"40","author":"T Vidal","year":"2013","unstructured":"Vidal, T., Crainic, T.G., Gendreau, M., Prins, C.: A hybrid genetic algorithm with adaptive diversity management for a large class of vehicle routing problems with time-windows. Comput. Oper. Res. 40(1), 475\u2013489 (2013)","journal-title":"Comput. Oper. Res."},{"key":"1845_CR43","doi-asserted-by":"crossref","unstructured":"Vieira, Y.E.M., de\u00a0Mello\u00a0Bandeira, R.A., da\u00a0Silva\u00a0J\u00fanior, O.S.: Multi-depot vehicle routing problem for large scale disaster relief in drought scenarios: the case of the brazilian northeast region. Int. J. Disas. Risk Reduct. 58, 102193 (2021)","DOI":"10.1016\/j.ijdrr.2021.102193"},{"issue":"12","key":"1845_CR44","doi-asserted-by":"publisher","first-page":"4948","DOI":"10.1109\/TSMC.2019.2938298","volume":"50","author":"X Wang","year":"2019","unstructured":"Wang, X., Choi, T.M., Li, Z., Shao, S.: An effective local search algorithm for the multidepot cumulative capacitated vehicle routing problem. IEEE Trans. Syst. Man Cybern. Syst. 50(12), 4948\u20134958 (2019)","journal-title":"IEEE Trans. Syst. Man Cybern. Syst."},{"key":"1845_CR45","doi-asserted-by":"publisher","first-page":"106632","DOI":"10.1016\/j.cie.2020.106632","volume":"147","author":"X Wei","year":"2020","unstructured":"Wei, X., Qiu, H., Wang, D., Duan, J., Wang, Y., Cheng, T.: An integrated location-routing problem with post-disaster relief distribution. Comput. Indus. Eng. 147, 106632 (2020)","journal-title":"Comput. Indus. Eng."}],"container-title":["Optimization Letters"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11590-021-01845-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s11590-021-01845-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11590-021-01845-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,10,27]],"date-time":"2022-10-27T13:04:25Z","timestamp":1666875865000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s11590-021-01845-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,2,4]]},"references-count":45,"journal-issue":{"issue":"9","published-print":{"date-parts":[[2022,12]]}},"alternative-id":["1845"],"URL":"https:\/\/doi.org\/10.1007\/s11590-021-01845-7","relation":{},"ISSN":["1862-4472","1862-4480"],"issn-type":[{"value":"1862-4472","type":"print"},{"value":"1862-4480","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,2,4]]},"assertion":[{"value":"6 July 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"10 December 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"4 February 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}