Five years of multi-depot vehicle routing problems

• Autorzy: Jayarathna Nuwan , Lanel Jayantha , Juman Z. A. M. S.

Identyfikatory

DOI

10.14254/jsdtl.2020.5-2.10

• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

multi-depot vehicle routing problem; exact methods; heuristic; meta-heuristic

• Wydawca: Fundacja Centrum Badań Socjologicznych ; Scientific Publishing House "SciView"
• Czasopismo: Journal of Sustainable Development of Transport and Logistics
• Rocznik: 2020
• Tom: Vol. 5, No. 2
• Strony: 109--123
• Opis fizyczny: Bibliogr. 41 poz., rys., tab., wzory

Twórcy

autor

Jayarathna Nuwan

• Colombo International Nautical and Engineering College, Sri Lanka

autor

Lanel Jayantha

• University of Sri Jayewardenepura, Sri Lanka

autor

Juman Z. A. M. S.

• University of Peradeniya, Sri Lanka

Bibliografia

• 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. ttps://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

Uwagi

PL

Opracowanie rekordu ze środków MNiSW, umowa Nr 461252 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2020).