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

Öz

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.

Anahtar Kelimeler

• Green vehicle routing problem
• genetic algorithm
• tabu search

Kaynakça

1. 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
2. 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
3. Bektaş, T. & Laporte, G. (2011). The pollution-routing problem, Transportation Research Part B: Methodological, 45 (8), 1232-1250, 2011. google scholar
4. 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
5. 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
6. Christofides, N. & Eilon, S. (1969). An Algorithm for The Vehicle Dispatching Problem. Operational Research Quarterly, 20 (3). google scholar
7. 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
8. 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

9. Ç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
10. Dantzig, G.B & Ramser, J.H (1959). The truck dispatching problem, Management science, 6 (1), 80-91. google scholar
11. 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
12. 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
13. 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
14. 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
15. Eiben, E.A. & Smith, E.J. (2003). Introduction to Evolutionary Computing, Springer, Berlin, Heidelberg, ISSN: 1619-7127, 2003, pp. 25-45. google scholar
16. 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
17. 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
18. 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
19. Figliozzi, M. (2010). Vehicle routing problem for emissions minimization. Transportation Research Record: Journal of the Transportation Research Board, (2197), 1-7. google scholar
20. 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
21. Glover, F. & Laguna, M. (1997). Tabu Search, Kluwer Academic Publishers Norwell, MA, USA. google scholar
22. 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
23. International Energy Agency, World Energy Outlook (2023). https://iea.blob.core.windows.net/assets/42b23c45-78bc-4482-b0f9 eb826ae2da3d/WorldEnergyOutlook2023.pdf. google scholar
24. 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
25. 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
26. 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
27. 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
28. 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
29. 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
30. 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
31. 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
32. 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
33. 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
34. Maranzana, F. (1964). On the Location ofSupply Points to Minimize Transport Costs. Operations Research Quarterly, 15, 261-70. google scholar
35. 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
36. Nagy, G. & Salhi, S. (2007). Location Routing: Issues, Models and Methods. European Journal of Operational Research, 177, 649-672. google scholar
37. Nilsson, C.(2003). Heuristics for the Traveling Salesman Problem, Technical Report, Linköping University, Sweden, google scholar
38. Parberry, I. (1996). Scalability ofa neural network for the knight’s tour problem, Neuro computing, 12 (1), 19-20. google scholar
39. 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
40. 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
41. Sakawa, M. (2002). Genetic Algorithms and Fuzzy Multiobjective Optimization, 14. Ed., Springer Science & Business Media. google scholar
42. 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
43. 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
44. 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
45. 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
46. 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
47. 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
48. 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
49. 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
50. Waters, D. (2003). Logistics: An Introduction to Supply Chain Management, Palgrave Macmillan, Basingstoke, England. google scholar
51. Webb, M.H.J. (1968). Cost Functions in The Location of Depots for MultipleDelivery Journeys. Operational Research Quarterly, 19, 311-320. google scholar
52. 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
53. 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
54. Zbigniew, M.(1996). Genetic Algorithms Data Structures Evolution Programs, Berlin, Springer, Third Edition. google scholar