Survey on Ten Years of Multi-Depot Vehicle Routing Problems: Mathematical Models, Solution Methods and Real-Life Applications
Keywords:
multi-depot vehicle routing problem, exact methods, heuristic, meta-heuristic
Abstract
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.
References
Alinaghian, M., & Shokouhi, N. (2018). Multi-depot multi-compartment vehicle routing problem, solved by a hybrid adaptive large neighborhood search. Omega, 76, 85–99. https://doi.org/10.1016/j.omega.2017.05.002
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. https://doi.org/10.1016/j.trc.2010.08.003
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. https://doi.org/10.1016/j.disopt.2014.03.001
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. https://doi.org/10.1016/j.eswa.2015.08.030
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. https://doi.org/10.1016/j.ins.2017.02.011
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. https://doi.org/10.14254/jsdtl.2018.3-2.4.
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. https://doi.org/10.1016/j.cie.2011.05.012
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. https://doi.org/10.1016/j.trd.2017.09.003
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. https://doi.org/10.14254/jsdtl.2020.5-2.10.
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. https://doi.org/10.35940/ijrte.B1115.0782S419
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. https://doi.org/10.1016/j.cie.2015.04.011
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. https://doi.org/10.1016/j.tre.2019.07.012
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. https://doi.org/10.1016/j.eswa.2014.12.004
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. https://doi.org/10.1016/j.trd.2018.01.026
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. https://doi.org/10.1016/j.jclepro.2019.03.185
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. https://doi.org/10.1016/j.trc.2015.06.016
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. https://doi.org/10.1016/j.rcim.2010.06.023
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. https://doi.org/10.1016/j.jksues.2014.04.007
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. https://doi.org/10.1016/j.swevo.2018.04.001
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. https://doi.org/10.1016/j.biosystemseng.2018.04.003
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. https://doi.org/10.1016/j.eswa.2019.113099
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. https://doi.org/10.1016/j.cie.2017.03.022
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. https://doi.org/10.1016/j.ifacol.2018.08.318
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. https://doi.org/10.1016/j.tre.2013.11.003
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. https://doi.org/10.1016/j.cor.2016.01.008
Yücenur, G. N., & Demirel, N. (2011). Expert Systems with Applications, 38(9), 11859–11865. https://doi.org/10.1016/j.eswa.2011.03.077
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. https://doi.org/10.1016/j.trc.2010.08.003
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. https://doi.org/10.1016/j.disopt.2014.03.001
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. https://doi.org/10.1016/j.eswa.2015.08.030
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. https://doi.org/10.1016/j.ins.2017.02.011
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. https://doi.org/10.14254/jsdtl.2018.3-2.4.
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. https://doi.org/10.1016/j.cie.2011.05.012
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. https://doi.org/10.1016/j.trd.2017.09.003
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. https://doi.org/10.14254/jsdtl.2020.5-2.10.
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. https://doi.org/10.35940/ijrte.B1115.0782S419
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. https://doi.org/10.1016/j.cie.2015.04.011
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. https://doi.org/10.1016/j.tre.2019.07.012
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. https://doi.org/10.1016/j.eswa.2014.12.004
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. https://doi.org/10.1016/j.trd.2018.01.026
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. https://doi.org/10.1016/j.jclepro.2019.03.185
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. https://doi.org/10.1016/j.trc.2015.06.016
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. https://doi.org/10.1016/j.rcim.2010.06.023
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. https://doi.org/10.1016/j.jksues.2014.04.007
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. https://doi.org/10.1016/j.swevo.2018.04.001
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. https://doi.org/10.1016/j.biosystemseng.2018.04.003
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. https://doi.org/10.1016/j.eswa.2019.113099
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. https://doi.org/10.1016/j.cie.2017.03.022
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. https://doi.org/10.1016/j.ifacol.2018.08.318
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. https://doi.org/10.1016/j.tre.2013.11.003
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. https://doi.org/10.1016/j.cor.2016.01.008
Yücenur, G. N., & Demirel, N. (2011). Expert Systems with Applications, 38(9), 11859–11865. https://doi.org/10.1016/j.eswa.2011.03.077
Published
2021-02-27
Issue
Section
Articles
This work is licensed under a Creative Commons Attribution 4.0 International License.
Copyright for this article is retained by the author(s), with first publication rights granted to the journal.
This is an open-access article distributed under the terms and conditions of the Creative Commons Attribution license (http://creativecommons.org/licenses/by/4.0/).
