Five years of multi-depot vehicle routing problems
Article Sidebar
Issue
Vol. 5 No. 2 (2020)
Keywords:
-
multi-depot vehicle routing problem, exact methods, heuristic, meta-heuristic
Abstract
With vast range of applications in real life situations, the Vehicle Routing Problems (VRPs) have been the subject of countless studies since the late 1950s. However, a more realistic version of the classical VRP, where the distribution of goods is done from several depots is the Multi-Depot Vehicle Routing Problem (MDVRP), which has been the central attraction of recent researches. The objective of this problem is to find the routes for vehicles to serve all the customers at a minimal cost in terms of the number of routes and the total distance travelled without violating the capacity and travel time constraints of the vehicles, and it is handled with a variety of assumptions and constraints in the existing literature. This survey reviews the current status of the MDVRP and discuss the future direction regarding this problem.
Full text article
Generated from XML file
References
Afshar-Nadjafi, B., & Afshar-Nadjafi, A. (2017). A 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
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
Brandão, J. (2020). A memory-based iterated local search algorithm for the multi-depot open vehicle routing problem. European Journal of Operational Research, 284(2), 559–571. https://doi.org/10.1016/j.ejor.2020.01.008
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
Crevier, B., Cordeau, J.-F., & Laporte, G. (2007). The multi-depot vehicle routing problem with inter-depot routes. European Journal of Operational Research, 176(2), 756–773. https://doi.org/10.1016/j.ejor.2005.08.015
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, D. G. 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.
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
Ho, W., Ho, G. T. S., Ji, P., & Lau, H. C. W. (2008). A hybrid genetic algorithm for the multi-depot vehicle routing problem. Engineering Applications of Artificial Intelligence, 21(4), 548–557. https://doi.org/10.1016/j.engappai.2007.06.001
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, D. G. N. D., Lanel, G. H. J., & Juman, Z. (2019). A Contemporary Recapitulation of Major Findings on Vehicle Routing Problems: Models and Methodologies. International Journal of Recent Technology and Engineering (IJRTE) Volume 8, 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. 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
Modeling of an Optimal Outbound Logistics System (A Contemporary Review Study on effects of Vehicle Routing, Facility Location and Locational Routing Problems). (n.d.). Retrieved January 20, 2020, from http://www.ijhssi.org/papers/vol8(10)/Series-2/C0810020830.pdf
Montoya-Torres, J. R., López Franco, J., Nieto Isaza, S., Felizzola Jiménez, H., & Herazo-Padilla, N. (2015). A literature review on the vehicle routing problem with multiple depots. Computers & Industrial Engineering, 79, 115–129. https://doi.org/10.1016/j.cie.2014.10.029
Nagy, G., & Salhi, S. (2005). Heuristic algorithms for single and multiple depot vehicle routing problems with pickups and deliveries. European Journal of Operational Research, 162(1), 126–141. https://doi.org/10.1016/j.ejor.2002.11.003
Osaba, E., Yang, X.-S., Diaz, F., Onieva, E., Masegosa, A. D., & Perallos, A. (2017). A Discrete Firefly Algorithm to Solve a Rich Vehicle Routing Problem Modelling a Newspaper Distribution System with Recycling Policy. Soft Computing, 21(18), 5295–5308. https://doi.org/10.1007/s00500-016-2114-1
Osaba, Eneko, Yang, X.-S., Fister, I., Del Ser, J., Lopez-Garcia, P., & Vazquez-Pardavila, A. J. (2019). A 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
Pardalos, P., & Coleman, T. (Eds.). (2009). Lectures on Global Optimization. American Mathematical Society. https://doi.org/10.1090/fic/055
Prodhon, C. (2011). A hybrid evolutionary algorithm for the periodic location-routing problem. European Journal of Operational Research, 210(2), 204–212.
Ropke, S., & Pisinger, D. (2006). An Adaptive Large Neighborhood Search Heuristic for the Pickup and Delivery Problem with Time Windows. Transportation Science, 40(4), 455–472. https://doi.org/10.1287/trsc.1050.0135
Salhi, S., Imran, A., & Wassan, N. A. (2014). The multi-depot vehicle routing problem with heterogeneous vehicle fleet: Formulation and a variable neighborhood search implementation. Computers & Operations Research, 52, 315–325. https://doi.org/10.1016/j.cor.2013.05.011
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, 113099. 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. (2018). A 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. (2014). A 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
Wang, Y., Assogba, K., Fan, J., Xu, M., Liu, Y., & Wang, H. (2019). Multi-depot green vehicle routing problem with shared transportation resource: Integration of time-dependent speed and piecewise penalty cost. Journal of Cleaner Production, 232, 12–29. https://doi.org/10.1016/j.jclepro.2019.05.344
Wasner, M., & Zäpfel, G. (2004). An integrated multi-depot hub-location vehicle routing model for network planning of parcel service. International Journal of Production Economics, 90(3), 403–419. https://doi.org/10.1016/j.ijpe.2003.12.002
Yu, B., Yang, Z.-Z., & Xie, J.-X. (2011). A parallel improved ant colony optimization for multi-depot vehicle routing problem. Journal of the Operational Research Society, 62(1), 183–188. https://doi.org/10.1057/jors.2009.161
Yücenur, G. N., & Demirel, N. Ç. (2011). A new geometric shape-based genetic clustering algorithm for the multi-depot vehicle routing problem. Expert Systems with Applications, 38(9), 11859–11865. https://doi.org/10.1016/j.eswa.2011.03.077
Zhen, L., Ma, C., Wang, K., Xiao, L., & Zhang, W. (2020). Multi-depot multi-trip vehicle routing problem with time windows and release dates. Transportation Research Part E: Logistics and Transportation Review, 135, 101866. https://doi.org/10.1016/j.tre.2020.101866
Zhou, L., Baldacci, R., Vigo, D., & Wang, X. (2018). A Multi-Depot Two-Echelon Vehicle Routing Problem with Delivery Options Arising in the Last Mile Distribution. European Journal of Operational Research, 265(2), 765–778. https://doi.org/10.1016/j.ejor.2017.08.011
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
Brandão, J. (2020). A memory-based iterated local search algorithm for the multi-depot open vehicle routing problem. European Journal of Operational Research, 284(2), 559–571. https://doi.org/10.1016/j.ejor.2020.01.008
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
Crevier, B., Cordeau, J.-F., & Laporte, G. (2007). The multi-depot vehicle routing problem with inter-depot routes. European Journal of Operational Research, 176(2), 756–773. https://doi.org/10.1016/j.ejor.2005.08.015
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, D. G. 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.
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
Ho, W., Ho, G. T. S., Ji, P., & Lau, H. C. W. (2008). A hybrid genetic algorithm for the multi-depot vehicle routing problem. Engineering Applications of Artificial Intelligence, 21(4), 548–557. https://doi.org/10.1016/j.engappai.2007.06.001
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, D. G. N. D., Lanel, G. H. J., & Juman, Z. (2019). A Contemporary Recapitulation of Major Findings on Vehicle Routing Problems: Models and Methodologies. International Journal of Recent Technology and Engineering (IJRTE) Volume 8, 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. 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
Modeling of an Optimal Outbound Logistics System (A Contemporary Review Study on effects of Vehicle Routing, Facility Location and Locational Routing Problems). (n.d.). Retrieved January 20, 2020, from http://www.ijhssi.org/papers/vol8(10)/Series-2/C0810020830.pdf
Montoya-Torres, J. R., López Franco, J., Nieto Isaza, S., Felizzola Jiménez, H., & Herazo-Padilla, N. (2015). A literature review on the vehicle routing problem with multiple depots. Computers & Industrial Engineering, 79, 115–129. https://doi.org/10.1016/j.cie.2014.10.029
Nagy, G., & Salhi, S. (2005). Heuristic algorithms for single and multiple depot vehicle routing problems with pickups and deliveries. European Journal of Operational Research, 162(1), 126–141. https://doi.org/10.1016/j.ejor.2002.11.003
Osaba, E., Yang, X.-S., Diaz, F., Onieva, E., Masegosa, A. D., & Perallos, A. (2017). A Discrete Firefly Algorithm to Solve a Rich Vehicle Routing Problem Modelling a Newspaper Distribution System with Recycling Policy. Soft Computing, 21(18), 5295–5308. https://doi.org/10.1007/s00500-016-2114-1
Osaba, Eneko, Yang, X.-S., Fister, I., Del Ser, J., Lopez-Garcia, P., & Vazquez-Pardavila, A. J. (2019). A 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
Pardalos, P., & Coleman, T. (Eds.). (2009). Lectures on Global Optimization. American Mathematical Society. https://doi.org/10.1090/fic/055
Prodhon, C. (2011). A hybrid evolutionary algorithm for the periodic location-routing problem. European Journal of Operational Research, 210(2), 204–212.
Ropke, S., & Pisinger, D. (2006). An Adaptive Large Neighborhood Search Heuristic for the Pickup and Delivery Problem with Time Windows. Transportation Science, 40(4), 455–472. https://doi.org/10.1287/trsc.1050.0135
Salhi, S., Imran, A., & Wassan, N. A. (2014). The multi-depot vehicle routing problem with heterogeneous vehicle fleet: Formulation and a variable neighborhood search implementation. Computers & Operations Research, 52, 315–325. https://doi.org/10.1016/j.cor.2013.05.011
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, 113099. 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. (2018). A 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. (2014). A 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
Wang, Y., Assogba, K., Fan, J., Xu, M., Liu, Y., & Wang, H. (2019). Multi-depot green vehicle routing problem with shared transportation resource: Integration of time-dependent speed and piecewise penalty cost. Journal of Cleaner Production, 232, 12–29. https://doi.org/10.1016/j.jclepro.2019.05.344
Wasner, M., & Zäpfel, G. (2004). An integrated multi-depot hub-location vehicle routing model for network planning of parcel service. International Journal of Production Economics, 90(3), 403–419. https://doi.org/10.1016/j.ijpe.2003.12.002
Yu, B., Yang, Z.-Z., & Xie, J.-X. (2011). A parallel improved ant colony optimization for multi-depot vehicle routing problem. Journal of the Operational Research Society, 62(1), 183–188. https://doi.org/10.1057/jors.2009.161
Yücenur, G. N., & Demirel, N. Ç. (2011). A new geometric shape-based genetic clustering algorithm for the multi-depot vehicle routing problem. Expert Systems with Applications, 38(9), 11859–11865. https://doi.org/10.1016/j.eswa.2011.03.077
Zhen, L., Ma, C., Wang, K., Xiao, L., & Zhang, W. (2020). Multi-depot multi-trip vehicle routing problem with time windows and release dates. Transportation Research Part E: Logistics and Transportation Review, 135, 101866. https://doi.org/10.1016/j.tre.2020.101866
Zhou, L., Baldacci, R., Vigo, D., & Wang, X. (2018). A Multi-Depot Two-Echelon Vehicle Routing Problem with Delivery Options Arising in the Last Mile Distribution. European Journal of Operational Research, 265(2), 765–778. https://doi.org/10.1016/j.ejor.2017.08.011
Authors
Jayarathna, N., Lanel, J., & Juman, Z. (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
Authors retain copyright and grant the journal right of first publication, with the work simultaneously licensed under a CC BY 4.0Â License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
Article Details
