A hybrid heuristic approach for the multi-objective multi depot vehicle routing problem

Abstract: Efficiency in logistics is often affected by the fair distribution of the customers along the routes and the available depots for goods delivery. From this perspective, in this study, the Multi-depot Vehicle Routing Problem (MDVRP), by considering two objectives, is addressed. The two objectives in conflict for MDVRP are the distance traveled by vehicles and the standard deviation of the routes’ length. A significant standard deviation value provides a small distance traveled by vehicles, translated into unbalanced routes. We have used a weighted average objective function involving the two objectives. A Variable Neighborhood Search algorithm within a Chu-Beasley Genetic Algorithm has been proposed to solve the problem. For decision-making purposes, several values are chosen for the weight factors multiplying the terms at the objective function to build up a non-dominated front of solutions. The methodology is tested in large-size instances for the MDVRP, reporting noticeable results for managerial insights.

How to cite this paper

 Londoño, A., González, W., Giraldo, O & Escobar, J. (2024). A hybrid heuristic approach for the multi-objective multi depot vehicle routing problem.International Journal of Industrial Engineering Computations , 15(1), 337-354.

Refrences

Borgulya, I. (2008). An algorithm for the capacitated vehicle routing problem with route balancing. Central European Journal of Operations Research, 16, 331-343.
Chao, I. M., Golden, B. L., & Wasil, E. (1993). A new heuristic for the multi-depot vehicle routing problem that improves upon best-known solutions. American Journal of Mathematical and Management Sciences, 13(3-4), 371-406.
Chu, P. C., & Beasley, J. E. (1997). A genetic algorithm for the generalised assignment problem. Computers & Operations Research, 24(1), 17-23.
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.
Deb, K., Pratap, A., Agarwal, S., & Meyarivan, T. A. M. T. (2002). A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE transactions on evolutionary computation, 6(2), 182-197.
Escobar, J. W., Linfati, R., Toth, P., & Baldoquin, M. G. (2014). A hybrid granular tabu search algorithm for the multi-depot vehicle routing problem. Journal of heuristics, 20, 483-509.
Filipec, M., Škrlec, D., & Krajcar, S. (2000). Genetic algorithm approach for multiple depot capacitated vehicle routing problem solving with heuristic improvements. International Journal of Modelling and Simulation, 20(4), 320-328.
Galindres-Guancha, L., Toro-Ocampo, E., & Rendón, R. (2018). Multi-objective MDVRP solution considering route balance and cost using the ILS metaheuristic. International Journal of Industrial Engineering Computations, 9(1), 33-46.
Garcia-Najera, A., & Bullinaria, J. A. (2011). An improved multi-objective evolutionary algorithm for the vehicle routing problem with time windows. Computers & Operations Research, 38(1), 287-300.
Geetha, S., Vanathi, P. T., & Poonthalir, G. (2012). Metaheuristic approach for the multi-depot vehicle routing problem. Applied Artificial Intelligence, 26(9), 878-901.
Ho, W., Ho, G. T., Ji, P., & Lau, H. C. (2008). A hybrid genetic algorithm for the multi-depot vehicle routing problem. Engineering applications of artificial intelligence, 21(4), 548-557.
Hou, D., Fan, H., & Ren, X. (2021). Multi-Depot Joint Distribution Vehicle Routing Problem Considering Energy Consumption with Time-Dependent Networks. Symmetry, 13(11), 2082.
Hou, D., Fan, H., Ren, X., Tian, P., & Lv, Y. (2021). Time-dependent multi-depot heterogeneous vehicle routing problem considering temporal–spatial distance. Sustainability, 13(9), 4674.
Jayarathna, D. G. N. D., Lanel, G. H. J., & Juman, Z. A. M. S. (2021). Survey on ten years of multi-depot vehicle routing problems: mathematical models, solution methods and real-life applications. Sustainable Development Research, 3(1), p36-p36.
Jayarathna, N., Lanel, J., & Juman, Z. (2020). View of Five years of multi-depot vehicle routing problems. Journal of Sustainable Development Transport and Logistics, 109-123.
Jozefowiez, N., Semet, F., & Talbi, E. G. (2007). Target aiming Pareto search and its application to the vehicle routing problem with route balancing. Journal of Heuristics, 13, 455-469.
Jozefowiez, N., Semet, F., & Talbi, E. G. (2009). An evolutionary algorithm for the vehicle routing problem with route balancing. European Journal of Operational Research, 195(3), 761-769.
Karakatič, S., & Podgorelec, V. (2015). A survey of genetic algorithms for solving multi depot vehicle routing problem. Applied Soft Computing, 27, 519-532.
Li, Y., Qian, B., Hu, R., Wu, L. P., & Liu, B. (2019). Two-stage algorithm for solving multi-depot green vehicle routing problem with time window. In Intelligent Computing Theories and Application: 15th International Conference, ICIC 2019, Nanchang, China, August 3–6, 2019, Proceedings, Part I 15 (pp. 665-675). Springer International Publishing.
Li, Y., Soleimani, H., & Zohal, M. (2019b). An improved ant colony optimization algorithm for the multi-depot green vehicle routing problem with multiple objectives. Journal of cleaner production, 227, 1161-1172.
Liu, R., Jiang, Z., & Geng, N. (2014). A hybrid genetic algorithm for the multi-depot open vehicle routing problem. OR spectrum, 36, 401-421.
Luo, J., & Chen, M. R. (2014). Improved shuffled frog leaping algorithm and its multi-phase model for multi-depot vehicle routing problem. Expert Systems with Applications, 41(5), 2535-2545.
Luo, J., Li, X., & Chen, M. R. (2012). A Novel Meta-heuristic for the Multi-depot Vehicle Routing Problem. In Information Computing and Applications: Third International Conference, ICICA 2012, Chengde, China, September 14-16, 2012. Proceedings, Part I 3 (pp. 216-224). Springer Berlin Heidelberg.
Mancini, S., Gansterer, M., & Hartl, R. F. (2021). The collaborative consistent vehicle routing problem with workload balance. European journal of operational research, 293(3), 955-965.
Matl, P., Hartl, R. F., & Vidal, T. (2018). Workload equity in vehicle routing problems: A survey and analysis. Transportation Science, 52(2), 239-260.
Mirabi, M. (2014). A hybrid electromagnetism algorithm for multi-depot periodic vehicle routing problem. The International Journal of Advanced Manufacturing Technology, 71(1-4), 509-518.
Montoya, O. D., Gil-González, W., & Orozco-Henao, C. (2020). Vortex search and Chu-Beasley genetic algorithms for optimal location and sizing of distributed generators in distribution networks: A novel hybrid approach. Engineering Science and Technology, an International Journal, 23(6), 1351-1363.
Moonsri, K., Sethanan, K., Worasan, K., & Nitisiri, K. (2021). A hybrid and self-adaptive differential evolution algorithm for the multi-depot vehicle routing problem in egg distribution. Applied Sciences, 12(1), 35.
Networking and Emerging Optimization. (2006). The VRP web. Retrieved from https://www.bernabe.dorronsoro.es/vrp/index.html?/Problem_Instances/CVRPTWInstances.html
Ombuki-Berman, B., & Hanshar, F. T. (2009). Using genetic algorithms for multi-depot vehicle routing. In Bio-inspired algorithms for the vehicle routing problem (pp. 77-99). Berlin, Heidelberg: Springer Berlin Heidelberg.
Peng, B., Wu, L., Yi, Y., & Chen, X. (2020). Solving the multi-depot green vehicle routing problem by a hybrid evolutionary algorithm. Sustainability, 12(5), 2127.
Prabu, U., Ravisasthiri, P., Sriram, R., Malarvizhi, N., & Amudhavel, J. (2019). EODVGA: an enhanced ODV based genetic algorithm for multi-depot vehicle routing problem. EAI Endorsed Transactions on Scalable Information Systems, 6(21), e8-e8.
Renaud, J., Laporte, G., & Boctor, F. F. (1996). A tabu search heuristic for the multi-depot vehicle routing problem. Computers & Operations Research, 23(3), 229-235.
Shen, L., Tao, F., & Wang, S. (2018). Multi-depot open vehicle routing problem with time windows based on carbon trading. International journal of environmental research and public health, 15(9), 2025.
Singh, V., Ganapathy, L., & Pundir, A. K. (2021). An improved genetic algorithm for solving multi depot Vehicle Routing Problems. In Research anthology on multi-industry uses of genetic programming and algorithms (pp. 375-402). IGI Global.
Skok, M., Skrlec, D., & Krajcar, S. (2000, August). The genetic algorithm method for multiple depot capacitated vehicle routing problem solving. In KES'2000. Fourth International Conference on Knowledge-Based Intelligent Engineering Systems and Allied Technologies. Proceedings (Cat. No. 00TH8516) (Vol. 2, pp. 520-526). IEEE.
Subramanian, A., Uchoa, E., & Ochi, L. S. (2013). A hybrid algorithm for a class of vehicle routing problems. Computers & Operations Research, 40(10), 2519-2531.
Surekha, P., & Sumathi, S. (2011). Solution to multi-depot vehicle routing problem using genetic algorithms. World Applied Programming, 1(3), 118-131.
Tang, Y. L., Cai, Y. G., & Yang, Q. J. (2015). Optimization of Multi-Depot Heterogeneous Incident Vehicle Routing Problem with Soft Time Windows based on an Improved Ant Colony Optimization. Advanced Materials Research, 1061, 1108-1117.
Wink, S., Bäck, T., & Emmerich, M. (2012, June). A meta-genetic algorithm for solving the capacitated vehicle routing problem. In 2012 IEEE congress on evolutionary computation (pp. 1-8). IEEE.
Yu, V. F., Aloina, G., Susanto, H., Effendi, M. K., & Lin, S. W. (2022). Regional Location Routing Problem for Waste Collection Using Hybrid Genetic Algorithm-Simulated Annealing. Mathematics, 10(12), 2131.
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.
Zacharia, P., Drosos, C., Piromalis, D., & Papoutsidakis, M. (2021). The vehicle routing problem with fuzzy payloads considering fuel consumption. Applied Artificial Intelligence, 35(15), 1755-1776.
Zhang, W., Gajpal, Y., Appadoo, S. S., & Wei, Q. (2020). Multi-depot green vehicle routing problem to minimize carbon emissions. Sustainability, 12(8), 3500.
Zhou, W., Song, T., He, F., & Liu, X. (2013). Multiobjective vehicle routing problem with route balance based on genetic algorithm. discrete Dynamics in Nature and Society, 2013.
Zhou, Z., Ha, M., Hu, H., & Ma, H. (2021). Half open multi-depot heterogeneous vehicle routing problem for hazardous materials transportation. Sustainability, 13(3), 1262.