A Sectoral Application for Green Vehicle Routing Problem Optimization with Capacity Constrained and Heterogeneous Fleet

Year 2024, , 183 - 198, 26.06.2024

Furkan Dişkaya , Sait Erdal Dinçer

https://doi.org/10.26650/ekoist.2024.40.1451034

Abstract

The vehicle routing problem (VRP), which is a type of traveling salesman problem (TSP), is a combinatorial optimization problem which determines the shortest route distribution from a central warehouse to customer points in certain locations. Today, global climate change resulting from high greenhouse gas emissions and the rapid decrease in natural resources have begun to threaten life as well as the sustainability of our economic structures. For this purpose, businesses have begun to prioritize to the concept of green logistics, which is based on the strategy of environmentally friendly activities in the production of goods and services. In this study, a mathematical model is proposed to solve the green vehicle routing problem with capacity limited and heterogeneous fleet (CHFGVRP), which is a type of vehicle routing problem under the green logistics strategy. Metaheuristic approaches produce successful solutions when solving routing problems with an NP-hard class problem structure. The presented model was developed by Ekol Inc., with the help of the Genetic Algorithm (GA) and Tabu Search (TS) metaheuristic solution approaches. It has been optimized as a real distribution operation for logistics businesses. The main purpose of the present study is assigning vehicles of different capacities of a logistics company to the most suitable loads for two different order sets, to determine the most appropriate customer point route. Thus, as transportation costs decrease thanks to fuel savings, the amount of carbon emissions released into the environment will also decrease. The results of this research will contribute to businesses which seek environmental and economic sustainability, as well as to the developing scientific literature on the subject.

Keywords

Green vehicle routing problem, genetic algorithm, tabu search

References

• Abdullahi H., Reyes-Rubiano L., Ouelhadj D., Faulin J. & Juan A. A. (2021). Modelling and multi-criteria analysis of the sustainability dimensions for the green vehicle routing problem”, European Journal of Operational Research, 292(1), 143-154. google scholar
• Akcakoca, A. E., Kızılkaya Aydogan, E., Delice, Y., Himmetoğlu, S. (2023). Heterojen Filolu ve Kapasite Kısıtlı Yeşil Araç Rotalama Problemi için Bir Matematiksel Model ve Endüstriyel Bir Uygulama. Politeknik Dergisi1-1. https://doi.org/10.2339/politeknik.1200084 google scholar
• Bektaş, T. & Laporte, G. (2011). The pollution-routing problem, Transportation Research Part B: Methodological, 45 (8), 1232-1250, 2011. google scholar
• Boz, E., Çalık, A., & Şahin, Y. (2024). Yeşil zaman pencereli ve eş zamanlı topla dağıt araç rotalama problemlerinin metasezgisel yöntemlerle çözümü. Gazi Üniversitesi Mühendislik Mimarlık Fakültesi Dergisi, 39(2), 757-770. https://doi.org/10.17341/gazimmfd.1180965 google scholar
• Bruglieri M., Ferone D., Festa P. & Pisacane O. (2022). A grasp with penalty objective function for the green vehicle routing problem with private capacitated stations, Computers and Operations Research, 143, 105770. google scholar
• Christofides, N. & Eilon, S. (1969). An Algorithm for The Vehicle Dispatching Problem. Operational Research Quarterly, 20 (3). google scholar
• Christopher, M, (2011). Logistics, the supply chain and competitive strategy. In Logistics and Supply Chain Management (4th ed.). Prentice Hall. London, Pearson Education, pp. 11. google scholar
• Clarke, G. & Wright, J.W. (1964). Scheduling of vehicles from a central depot to a number of delivery points, Operations research, 12 (4), 568-581. google scholar
• Çevik, O. & Gülcan, B. (2011). Lojistik Faaliyetlerin Çevresel Sürdürülebilirliği ve Marco Polo Programı, KMÜ Sosyal ve Ekonomik Araştırmalar Dergisi 13 (20). google scholar
• Dantzig, G.B & Ramser, J.H (1959). The truck dispatching problem, Management science, 6 (1), 80-91. google scholar
• Demir, E., Bektaş, T., & Laporte, G. (2012). An adaptive large neighborhood search heuristic for the pollution-routing problem. European Journal of Operational Research, 223(2), 346-359. google scholar
• Desrochers, M., Desrosiers, J., & Solomon, M. (1992). A New Optimization Algorithm for the Vehicle Routing Problem with Time Windows. Operations Research, 40(2), 342-354. http://www.jstor.org/stable/171457 google scholar
• Desrochers, M., Lenstra, J.K. & Savelsbergh. (1990). A classification scheme for vehicle routing and scheduling problems. European Journal of Operational Research. 46 (3), 322-332. google scholar
• Drake, A. E. & Marks, R.E. (2002). Genetic Algorithms in Economics and Finance: Forecasting Stock Market Prices and Foreign Exchange-A Review, Genetic Algorithms and Genetic Programming in Computational Finance, Springer, US. google scholar
• Eiben, E.A. & Smith, E.J. (2003). Introduction to Evolutionary Computing, Springer, Berlin, Heidelberg, ISSN: 1619-7127, 2003, pp. 25-45. google scholar
• Erdoğan, S. & Miller-Hooks, E. (2012). A green vehicle routing problem, Transportation research part E: logistics and transportation review, 48 (1), 100-114. google scholar
• Fakhrzad, M., Hoseini Shorshani, S., Hosseininasab & H., Mostafaeipour, A. (2022). Developing a green vehicle routing problem model with time windows and simultaneous pickup and delivery under demand uncertainty: Minimizing fuel consumption, Int. J. Nonlinear Anal. Appl., doi: 10.22075Zynaa.2021.23209.2493. google scholar
• Ferreira K. M., de Queiroz T. A. & Toledo F. M. B. (2021). An exact approach for the green vehicle routing problem with two-dimensional loading constraints and split delivery, Computers and Operations Research, 136, 105452. google scholar
• Figliozzi, M. (2010). Vehicle routing problem for emissions minimization. Transportation Research Record: Journal of the Transportation Research Board, (2197), 1-7. google scholar
• Fisher, M. (1995). Vehicle Routing. M.O. Ball et al., Eds., Handbooks in OR & MS, Vol. 8, 1995 Elsevier Science B.V. All rights reserved google scholar
• Glover, F. & Laguna, M. (1997). Tabu Search, Kluwer Academic Publishers Norwell, MA, USA. google scholar
• Hiermann, G., Puchinger, J., Ropke, S., & Hartl, R. F. (2016). The electric fleet size and mix vehicle routing problem with time windows and recharging stations. European Journal of Operational Research, 252(3), 995-1018. google scholar
• International Energy Agency, World Energy Outlook (2023). https://iea.blob.core.windows.net/assets/42b23c45-78bc-4482-b0f9 eb826ae2da3d/WorldEnergyOutlook2023.pdf. google scholar
• Koç, Ç., Bektaş, T., Jabali, O., & Laporte, G. (2016). The impact of depot location, fleet composition and routing on emissions in city logistics. Transportation Research Part B: Methodological, 84, 81-102. google scholar
• Kramer, R., Maculan, N., Subramanian, A., & Vidal, T. (2015). A speed and departure time optimization algorithm for the pollution-routing problem. European Journal of Operational Research, 247(3), 782-787. google scholar
• Laporte, G. (1992) The Vehicle Routing Problem: An Overview of Exact and Approximate Algorithms. European Journal of Operational Research, 59, 345-358. http://dx.doi.org/10.1016/0377-2217(92)90192-C google scholar
• Laporte, G., Nobert, Y. & Taillefer, S. (1987). A branch-and-bound algorithm for the asymmetrical distance-constrained vehicle routing problem. Mathematical Modelling. 9 (12), 857-868. google scholar
• Lei L., Liu S., Ruszczynski A. & Park S. (2006). On the integrated production, inventory, and distribution routing problem, IIE Transactions, 38:11, 955-970, DOI: 10.1080/07408170600862688 google scholar
• 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. google scholar
• Lin, C., Choy, K. L., Ho, G. T., & Ng, T. W. (2014). A genetic algorithm-based optimization model for supporting green transportation operations. Expert Systems with Applications, 41(7), 3284-3296. google scholar
• Liu, W. Y., Lin, C. C., Chiu, C. R., Tsao, Y. S., & Wang, Q. (2014). Minimizing the Carbon Footprint for the Time-Dependent Heterogeneous-Fleet Vehicle Routing Problem with Alternative Paths. Sustainability, 6(7), 4658-4684. google scholar
• Lopez, L., W. Carter, M. & Gendreau, M. (1998). The hot strip mill production scheduling problem: A tabu search approach, European Journal of Operational Research, 106(2). google scholar
• Majidi, S., Hosseini-Motlagh, S. M., Yaghoubi, S. & Jokar, A. (2017). Fuzzy green vehicle routing problem with simultaneouspickup-delivery and time Windows, RAIRO-operations research, 51 (4), 1151-1176. google scholar
• Maranzana, F. (1964). On the Location ofSupply Points to Minimize Transport Costs. Operations Research Quarterly, 15, 261-70. google scholar
• Meng, X., Lin, Z., & Tang, J. (2023). Heterogeneous Green Vehicle Routing Problem with different Customers Service Requirements, The 2023 2nd International Conference on Machine Learning, Control, and Robotics (MLCR 2023), www.mlcr-conf.org. google scholar
• Nagy, G. & Salhi, S. (2007). Location Routing: Issues, Models and Methods. European Journal of Operational Research, 177, 649-672. google scholar
• Nilsson, C.(2003). Heuristics for the Traveling Salesman Problem, Technical Report, Linköping University, Sweden, google scholar
• Parberry, I. (1996). Scalability ofa neural network for the knight’s tour problem, Neuro computing, 12 (1), 19-20. google scholar
• Ren X., Huang H., Feng S. & Liang, G. (2020). An improved variable neighborhood search for bi-objective mixed-energy fleet vehicle routing problem, Journal of Cleaner Production, 275, 124155. google scholar
• S. Al-Anzi, F. & Allahverdi, A. (2007). A self-adaptive differential evolution heuristic for two-stage assembly scheduling problem to minimize maximum lateness with setup times, European Journal of Operational Research, V: 182, Issue: 1. google scholar
• Sakawa, M. (2002). Genetic Algorithms and Fuzzy Multiobjective Optimization, 14. Ed., Springer Science & Business Media. google scholar
• Schneider, M., Stenger, A. & Goeke, D. (2014). The electric vehicle-routing problem with time windows and recharging stations, Transportation science, 48 (4), 500-520. google scholar
• Srivastara, S. (2007). Green Supply-Chain Management: A State-Of-The-Art Literature Review, International Journal Of Physical Distribution & Logistics Management, 1(7), 53-80. google scholar
• Su, Yukang and Zhang, Shuo & Zhang, Chengning. (2023). A Lightweight Genetic Algorithm with Variable Neighborhood Search for Multi-Depot Vehicle Routing Problem with Time Windows. Available at SSRN, http://dx.doi.org/10.2139/ssrn.4685925. google scholar
• Suzuki, Y. (2011). A new truck-routing approach for reducing fuel consumption and pollutants emission. Transportation Research Part D: Transport and Environment, 16(1), 73-77. google scholar
• Toth, P. & Vigo D. (2002). Models, relaxations and exact approaches for the capacitated vehicle routing problem, Discrete Applied Mathematics, Volume 123, Issues 1-3, pp. 487-512, doi.org/10.1016/S0166-218X(01)00351-1. google scholar
• Toth, P. & Vigo, D. (1998). Exact Solution of the Vehicle Routing Problem. Fleet Management and Logistic, Editör: T.G. Crainic, G. Laporte, Kluwer Academic, Boston, 1-31. google scholar
• Utama, D. M., Fitria, T.A. & Garside, A.K. (2021). Artificial bee colony algorithm for solving green vehicle routing problems with time windows. Journal of Physics: Conference Series, 1933 (1), 012043. google scholar
• Velâzquez-Martmez, J. C., Fransoo, J. C., Blanco, E. E., & Valenzuela-Ocana, K. B. (2016). A new statistical method of assigning vehicles to delivery areas for CO2 emissions reduction. Transportation Research Part D: Transport and Environment, 43, 133-144. google scholar
• Waters, D. (2003). Logistics: An Introduction to Supply Chain Management, Palgrave Macmillan, Basingstoke, England. google scholar
• Webb, M.H.J. (1968). Cost Functions in The Location of Depots for MultipleDelivery Journeys. Operational Research Quarterly, 19, 311-320. google scholar
• Xu, Z., Elomri, A., Pokharel, S. & Mutlu, F. (2019). A model for capacitated green vehicle routing problem with the time-varying vehicle speed and soft time Windows, Computers & Industrial Engineering, 137, 106011. google scholar
• Yu, Y., Wang, S., Wang, J. & Huang, M. (2019). A branch-and-price algorithmfor the heterogeneous fleet green vehicle routing problem with time Windows, Transportation Research Part B: Methodological, 122, 511-527. google scholar
• Zbigniew, M.(1996). Genetic Algorithms Data Structures Evolution Programs, Berlin, Springer, Third Edition. google scholar