Survey on Ten Years of Multi-Depot Vehicle Routing Problems: Mathematical Models, Solution Methods and Real-Life Applications

  • D. G. N. D. Jayarathna Colombo International Nautical and Engineering College, Sri Lanka
  • G. H. J. Lanel Department of Mathematics, University of Sri Jayewardenepura, Sri Lanka
  • Z. A. M. S. Juman Department of Mathematics, Faculty of Science, University of Peradeniya, Sri Lanka
Keywords: multi-depot vehicle routing problem, exact methods, heuristic, meta-heuristic


A crucial practical issue encountered in logistics management is the circulation of final products from depots to end-user customers. When routing and scheduling systems are improved, they will not only improve customer satisfaction but also increase the capacity to serve a large number of customers minimizing time. On the assumption that there is only one depot, the key issue of distribution is generally identified and formulated as VRP standing for Vehicle Routing Problem. In case, a company having more than one depot, the suggested VRP is most unlikely to work out. In view of resolving this limitation and proposing alternatives, VRP with multiple depots and multi-depot MDVRP have been a focus of this paper. Carrying out a comprehensive analytical literature survey of past ten years on cost-effective Multi-Depot Vehicle Routing is the main aim of this research. Therefore, the current status of the MDVRP along with its future developments is reviewed at length in the paper.


Alinaghian, M., & Shokouhi, N. (2018). Multi-depot multi-compartment vehicle routing problem, solved by a hybrid adaptive large neighborhood search. Omega, 76, 85–99.
Aras, N., Aksen, D., & Tuğrul, Tekin, M. (2011). Selective multi-depot vehicle routing problem with pricing. Transportation Research Part C: Emerging Technologies, 19(5), 866–884.
Contardo, C., & Martinelli, R. (2014). A new exact algorithm for the multi-depot vehicle routing problem under capacity and route length constraints. Discrete Optimization, 12, 129–146.
De Oliveira, F. B., Enayatifar, R., Sadaei, H. J., Guimarães, F. G., & Potvin, J. Y. (2016). A cooperative coevolutionary algorithm for the Multi-Depot Vehicle Routing Problem. Expert Systems with Applications, 43, 117–130.
Du, J., Li, X., Yu, L., Dan, R., & Zhou, J. (2017). Multi-depot vehicle routing problem for hazardous materials transportation: A fuzzy bilevel programming. Information Sciences, 399, 201–218.
Ganepola, D. D., Jayarathna, N. D., & Madhushani, G. (2018). An intelligent cost optimized central warehouse and redistribution root plan with truck allocation system in Colombo region for Lion Brewery Ceylon PLC. Journal of Sustainable Development of Transport and Logistics, 3(2), 66-73.
Gulczynski, D., Golden, B., & Wasil, E. (2011). The multi-depot split delivery vehicle routing problem: An integer programming-based heuristic, new test problems, and computational results. Computers & Industrial Engineering, 61(3), 794–804.
Jabir, E., Panicker, V. V., & Sridharan, R. (2017). Design and development of a hybrid ant colony-variable neighbourhood search algorithm for a multi-depot green vehicle routing problem. Transportation Research Part D: Transport and Environment, 57, 422–457.
Jayarathna, N., Lanel, J., & Juman, Z. A. M. S. (2020). Five years of multi-depot vehicle routing problems. Journal of Sustainable Development of Transport and Logistics, 5(2), 109-123.
Jayarathna, N., Lanel, J., Juman, S., (2019). A contemporary Recapitulation of Major Findings on Vehicle Routing Problems: Models and Methodologies. International Journal of Recent Technology and Engineering, 8(2S4), 581-585.
Kachitvichyanukul, V., Sombuntham, P., & Kunnapapdeelert, S. (2015). Two solution representations for solving multi-depot vehicle routing problem with multiple pickup and delivery requests via PSO. Computers & Industrial Engineering, 89, 125–136.
Kramer, R., Cordeau, J. F., & Iori, M. (2019). Rich vehicle routing with auxiliary depots and anticipated deliveries: An application to pharmaceutical distribution. Transportation Research Part E: Logistics and Transportation Review, 129, 162–174.
Li, J., Pardalos, P. M., Sun, H., Pei, J., & Zhang, Y. (2015). Iterated local search embedded adaptive neighborhood selection approach for the multi-depot vehicle routing problem with simultaneous deliveries and pickups. Expert Systems with Applications, 42(7), 3551–3561.
Li, J., Wang, R., Li, T., Lu, Z., & Pardalos, P. M. (2018). Benefit analysis of shared depot resources for multi-depot vehicle routing problem with fuel consumption. Transportation Research Part D: Transport and Environment, 59, 417–432.
Li, Y., Soleimani, H., & Zohal, M. (2019). An improved ant colony optimization algorithm for the multi-depot green vehicle routing problem with multiple objectives. Journal of Cleaner Production, 227, 1161–1172.
Mancini, S. (2016). A real-life Multi Depot Multi Period Vehicle Routing Problem with a Heterogeneous Fleet: Formulation and Adaptive Large Neighborhood Search based Matheuristic. Transportation Research Part C: Emerging Technologies, 70, 100–112.
Mirabi, M., Fatemi Ghomi, S. M. T., & Jolai, F. (2010). Efficient stochastic hybrid heuristics for the multi-depot vehicle routing problem. Robotics and Computer-Integrated Manufacturing, 26(6), 564–569.
Nadjafi, B. A, & Nadjafi, A, A. (2017). constructive heuristic for time-dependent multi-depot vehicle routing problem with time-windows and heterogeneous fleet. Journal of King Saud University. Engineering Sciences, 29(1), 29–34.
Osaba, E., Yang, X. S., Fister, I., Del Ser, J., Lopez-Garcia, P., & Vazquez-Pardavila, A. J. A. (2019). Discrete and Improved Bat Algorithm for solving a medical goods distribution problem with pharmacological waste collection. Swarm and Evolutionary Computation, 44, 273-286.
Seyyedhasani, H., & Dvorak, J. S. (2018). Dynamic rerouting of a fleet of vehicles in agricultural operations through a Dynamic Multiple Depot Vehicle Routing Problem representation. Biosystems Engineering, 171, 63–77.
Soeanu, A., Ray, S., Berger, J., Boukhtouta, A., & Debbabi, M. (2020). Multi-depot vehicle routing problem with risk mitigation: Model and solution algorithm. Expert Systems with Applications, 145, 11309.
Soto, M., Sevaux, M., Rossi, A., & Reinholz, A. (2017). Multiple neighborhood search, tabu search and ejection chains for the multi-depot open vehicle routing problem. Computers & Industrial Engineering, 107, 211–222.
Tohidifard, M., Tavakkoli-Moghaddam, R., Navazi, F., & Partovi, M, A. (2018). Multi-Depot Home Care Routing Problem with Time Windows and Fuzzy Demands Solving by Particle Swarm Optimization and Genetic Algorithm.
Tu, W., Fang, Z., Li, Q., Shaw, S.-L., & Chen, B, A. (2014). bi-level Voronoi diagram-based metaheuristic for a large-scale multi-depot vehicle routing problem. Transportation Research Part E: Logistics and Transportation Review, 61, 84–97.
Wang, X., Golden, B., Wasil, E., & Zhang, R. (2016). The min–max split delivery multi-depot vehicle routing problem with minimum service time requirement. Computers & Operations Research, 71, 110–126.
Yücenur, G. N., & Demirel, N. (2011). Expert Systems with Applications, 38(9), 11859–11865.