Green two-echelon vehicle routing problem: Fuel consumption calculation considering real road grade

Öz

With the intensification of logistics activities day by day, increasing energy consumption and greenhouse gas emissions create concerns about environmental sustainability and make it necessary to have different purposes in transportation. Therefore, in routing problems, it becomes critical to consider fuel consumption or emissions as well as basic objectives such as cost, distance or time. Ignoring or superficially considering the road grade, which is one of the important factors affecting fuel consumption, may lead to unrealistic results and misleading decisions. In this context, this study presents a mixed integer programming model for the Green Two-Echelon Vehicle Routing Problem (G-2E-VRP), which is considered to minimize fuel consumption, with realistic and detailed road gradient calculations. With the fact that the road grade can vary considerably even at a very short distance, all roads in the distribution network are divided into parts of certain lengths, the grade value of each part is calculated separately and the fuel consumption calculation is made using these relevant values. The applicability of the subject is shown in the study, which is taken as an example of the distribution network of a pharmaceutical warehouse in Turkey. In addition, sensitivity analyzes were performed in order to examine how the changes in grade and speed values will affect the total fuel consumption of the vehicles. The results show that road grade and speed factors are very efficient in fuel consumption of vehicles and should not be ignored.

Anahtar Kelimeler

• Sustainability
• Logistics
• Green Two-Echelon Vehicle Routing Problem
• Fuel Consumption
• Road Grade

Yeşil iki-aşamalı araç rotalama problemi: Gerçek yol eğimini dikkate alan yakıt tüketimi hesaplaması

Öz

Lojistik faaliyetlerin gün geçtikçe daha da yoğunlaşması ile artan enerji tüketimi ve sera gazı emisyonları çevresel sürdürülebilirliğe yönelik kaygılar yaratmakta ve taşımacılıkta farklı amaçlar edinmeyi zorunlu hale getirmektedir. Böylece, rotalama problemlerinde maliyet, mesafe ve zaman gibi temel amaçların yanı sıra yakıt tüketimi veya emisyonların da gözetilmesi kritik hale gelmektedir. Yakıt tüketimini etkileyen önemli unsurlardan biri olan yol eğiminin göz ardı edilmesi veya yüzeysel olarak hesaba katılması gerçeklikten uzak sonuçlar doğurmaktadır. Bu bağlamda, çalışmada yakıt tüketimini en aza indirmek amacıyla ele alınan Yeşil İki-Aşamalı Araç Rotalama Problemi (Y-2A-ARP)’nde, gerçekçi ve detaylı yol eğimleri ile hesaplamalar yapılmıştır. Çok kısa bir mesafede dahi eğimin oldukça değişebileceği gerçeği ile dağıtım ağında yer alan tüm yollar belirli uzunluklarda parçalara ayrılmış, her bir parçanın eğim değeri ayrı ayrı hesaplanmış ve yakıt tüketimi hesaplaması da bu ilgili değerler kullanılarak yapılmıştır. Türkiye’de bir ecza deposunun dağıtım ağının örnek alındığı çalışmada konunun uygulanabilirliği gösterilmiştir. Ayrıca, eğim ve hız değerlerindeki değişimin araçların toplam yakıt tüketimini nasıl etkileyeceğinin irdelenmesi amacıyla duyarlılık analizleri gerçekleştirilmiştir. Sonuçlar, yol eğimi ve hız faktörlerinin araçların yakıt tüketiminde oldukça etkili olduğunu ve göz ardı edilmemesi gerektiğini göstermektedir.

Anahtar Kelimeler

• Sürdürülebilirlik
• Lojistik
• Yakıt Tüketimi
• Yol Eğimi
• Yeşil İki-Aşamalı Araç Rotalama Problemi

Kaynakça

1. Alinaghian, M., & Naderipour, M. (2016). A novel comprehensive macroscopic model for time-dependent vehicle routing problem with multi-alternative graph to reduce fuel consumption: A case study. Computers & Industrial Engineering, 99, 210-222. doi: https://doi.org/10.1016/j.cie.2016.07.029
2. Anderluh, A., Nolz, P. C., Hemmelmayr, V. C., & Crainic, T. G. (2021). Multi-objective optimization of a twoechelon vehicle routing problem with vehicle synchronization and ‘grey zone’customers arising in urban logistics. European Journal of Operational Research, 289(3), 940-958. doi:https://doi.org/10.1016/j.ejor.2019.07.049
3. Asghari, M., & Al-e-hashem, S. M. J. M. (2021). Green vehicle routing problem: A state-of-the-art review. International Journal of Production Economics, 231, 107899. doi: https://doi.org/10.1016/j.ijpe.2020.107899
4. Babaee Tirkolaee, E., Hadian, S., & Golpira, H. (2019). A novel multi-objective model for two-echelon green routing problem of perishable products with intermediate depots. Journal of İndustrial Engineering And Management Studies, 6(2), 196-213. doi: https://doi.org/10.22116/JIEMS.2019.94158
5. Babagolzadeh, M., Shrestha, A., Abbasi, B., Zhang, S., Atefi, R., & Woodhead, A. (2019). Sustainable open vehicle routing with release-time and time-window: A two-echelon distribution system. IFAC-PapersOnLine, 52(13), 571-576. doi: https://doi.org/10.1016/j.ifacol.2019.11.219
6. Baldacci, R., Mingozzi, A., Roberti, R., & Calvo, R. W. (2013). An exact algorithm for the two-echelon capacitated vehicle routing problem. Operations Research, 61(2), 298-314. doi: https://doi.org/10.1287/opre.1120.1153
7. Barth, M., Younglove, T., & Scora, G. (2005). Development of a heavy-duty diesel modal emissions and fuel consumption model. UC Berkeley: California Partners for Advanced Transportation Technology. doi:https://escholarship.org/uc/item/67f0v3zf
8. Breunig, U., Schmid, V., Hartl, R. F., & Vidal, T. (2016). A large neighbourhood based heuristic for two-echelon routing problems. Computers & Operations Research, 76, 208-225. doi: https://doi.org/10.1016/j.cor.2016.06.014

9. Breunig, U., Baldacci, R., Hartl, R. F., & Vidal, T. (2019). The electric two-echelon vehicle routing problem. Computers & Operations Research, 103, 198-210. doi: https://doi.org/10.1016/j.cor.2018.11.005
10. Crainic, T. G., Ricciardi, N., & Storchi, G. (2009). Models for evaluating and planning city logistics systems. Transportation Science, 43(4), 432-454. doi: https://doi.org/10.1287/trsc.1090.0279
11. Cuda, R., Guastaroba, G., & Speranza, M. G. (2015). A survey on two-echelon routing problems. Computers & Operations Research, 55, 185-199. doi:https://doi.org/10.1016/j.cor.2014.06.008
12. Dellaert, N., Dashty Saridarq, F., Van Woensel, T., & Crainic, T. G. (2016). Branch & price based algorithms for the two-echelon vehicle routing problem with time windows. Technical report, CIRRELT-2016-45, Montreal, Kanada. doi: https://doi.org/10.1287/trsc.2018.0844
13. Demir, E., Bektaş, T., & Laporte, G. (2014). A review of recent research on green road freight transportation. European Journal Of Operational Research, 237(3), 775-793. doi:https://doi.org/10.1016/j.ejor.2013.12.033
14. Doolan, R., & Muntean, G. M. (2016). EcoTrec—A novel VANET-based approach to reducing vehicle emissions. IEEE Transactions on Intelligent Transportation Systems, 18(3), 608-620. doi:https://doi.org/10.1109/TITS.2016.2585925
15. Dündar, H., Soysal, M., Ömürgönülşen, M., & Kanellopoulos, A. (2022). A green dynamic TSP with detailed road gradient dependent fuel consumption estimation. Computers & Industrial Engineering, 168, 108024. doi:https://doi.org/10.1016/j.cie.2022.108024
16. Eitzen, H., Lopez-Pires, F., Baran, B., Sandoya, F., & Chicaiza, J. L. (2017). A multi-objective two-echelon vehicle routing problem. An urban goods movement approach for smart city logistics. XLIII Latin American Computer Conference (CLEI), 4–8 Eylül, 1-10. doi:https://doi.org/10.1109/CLEI.2017.8226454
17. Erdelic, T., & Caric, T. (2019). A survey on the electric vehicle routing problem: Variants and solution approaches. Journal of Advanced Transportation, 2019, 5075671. doi: https://doi.org/10.1155/2019/5075671
18. Erdoğan, S., & Miller-Hooks, E. (2012). A green vehicle routing problem. Transportation Research Part E: Logistics And Transportation Review, 48(1), 100-114. doi: https://doi.org/10.1016/j.tre.2011.08.001
19. Esmaeili, M., & Sahraeian, R. (2019). Comparing two-echelon and single-echelon multi-objective capacitated vehicle routing problems. Journal of Quality Engineering and Production Optimization, 4(1), 1-16. Retrieved from https://jqepo.shahed.ac.ir/article_893_131f8d60f21f37eb1d6c28f9f1c4c0e6.pdf
20. Fan, H., Zhang, Y., Tian, P., Lv, Y., & Fan, H. (2021). Time-dependent multi-depot green vehicle routing problem with time windows considering temporal-spatial distance. Computers & Operations Research, 129, 105211. doi:https://doi.org/10.1016/j.cor.2021.105211
21. Fan, P., Song, G., Zhu, Z., Wu, Y., Zhai, Z., & Yu, L. (2022). Road grade estimation based on Large-scale fuel consumption data of connected vehicles. Transportation Research Part D: Transport and Environment, 106, 103262. doi:https://doi.org/10.1016/j.trd.2022.103262
22. Gonzalez-Feliu, J. (2008). Models and methods for the city logistics: The two-echelon capacitated vehicle routing problem (Doctoral dissertation). Politecnico di Torino, Turin, İtalya. Retrieved from https://theses.hal.science/tel- 00844731/
23. Grangier, P., Gendreau, M., Lehuede, F., & Rousseau, L. M. (2016). An adaptive large neighborhood search for the two-echelon multiple-trip vehicle routing problem with satellite synchronization. European Journal of Operational Research, 254(1), 80-91. doi:https://doi.org/10.1016/j.ejor.2016.03.040
24. Hooker, J. N. (1988). Optimal driving for single-vehicle fuel economy. Transportation Research Part A: General, 22(3), 183-201. doi:https://doi.org/10.1016/0191-2607(88)90036-2
25. Jepsen, M., Spoorendonk, S., & Ropke, S. (2013). A branch-and-cut algorithm for the symmetric two-echelon capacitated vehicle routing problem. Transportation Science, 47(1), 23-37. doi:https://doi.org/10.1287/trsc.1110.0399
26. Jie, W., Yang, J., Zhang, M., & Huang, Y. (2019). The two-echelon capacitated electric vehicle routing problem with battery swapping stations: Formulation and efficient methodology. European Journal of Operational Research, 272(3), 879-904. doi:https://doi.org/10.1016/j.ejor.2018.07.002
27. Kamal, M. A. S., Mukai, M., Murata, J., & Kawabe, T. (2011). Ecological vehicle control on roads with up-down slopes. IEEE Transactions on Intelligent Transportation Systems, 12(3), 783-794. doi:https://doi.org/10.1109/TITS.2011.2112648
28. Kancharla, S. R., & Ramadurai, G. (2019). Multi-depot two-echelon fuel minimizing routing problem with heterogeneous fleets: model and heuristic. Networks and Spatial Economics, 19, 969-1005. doi:https://doi.org/10.1007/s11067-018-9437-7
29. Kang, L., Shen, H., & Li, Z. (2019). Road gradient estimation using smartphones: Towards accurate estimation on fuel consumption and air pollution emission on roads. IEEE 39th International Conference on Distributed Computing Systems (ICDCS), Dallas, TX, Amerika, Temmuz, 768-777. doi:https://doi.org/10.1109/ICDCS.2019.00081
30. Lai, D., Costa, Y., Demir, E., Florio, A., & Van Woensel, T. (2021). The pollution-routing problem with speed optimization and uneven topography. arXiv preprint arXiv:2105.09229. doi:https://doi.org/10.48550/arXiv.2105.09229
31. Li, H., Yuan, J., Lv, T., & Chang, X. (2016). The two-echelon time-constrained vehicle routing problem in linehaul-delivery systems considering carbon dioxide emissions. Transportation Research Part D: Transport and Environment, 49, 231-245. doi: https://doi.org/10.1016/j.trd.2016.10.002
32. Li, H., Liu, Y., Jian, X., & Lu, Y. (2018). The two-echelon distribution system considering the real-time transshipment capacity varying. Transportation Research Part B: Methodological, 110, 239-260. doi:https://doi.org/10.1016/j.trb.2018.02.015
33. Liu, R., Tao, Y., Hu, Q., & Xie, X. (2017). Simulation-based optimisation approach for the stochastic two-echelon logistics problem. International Journal of Production Research, 55(1), 187-201. doi:https://doi.org/10.1080/00207543.2016.1201221
34. Liu, D., Deng, Z., Mao, X., Yang, Y., & Kaisar, E. I. (2020). Two-echelon vehicle-routing problem: optimization of autonomous delivery vehicle-assisted E-grocery distribution. IEEE Access, 8, 108705-108719. doi:https://doi.org/10.1109/ACCESS.2020.3001753
35. Liu, L., & Liao, W. (2021). Optimization and profit distribution in a two-echelon collaborative waste collection routing problem from economic and environmental perspective. Waste Management, 120, 400-414. doi:https://doi.org/10.1016/j.wasman.2020.09.045
36. Liu, D., Yang, H., Mao, X., Antonoglou, V., & Kaisar, E. I. (2023). New mobility-assist e-grocery delivery network: a load-dependent two-echelon vehicle routing problem with mixed vehicles. Transportation Research Record, 2677(1), 294-310. doi: https://doi.org/10.1177/036119812210992
37. Pamucar, D., Gigovic, L., Cirovic, G., & Regodic, M. (2016). Transport spatial model for the definition of green routes for city logistics centers. Environmental Impact Assessment Review, 56, 72-87. doi:https://doi.org/10.1016/j.eiar.2015.09.002
38. Paul, A., Kumar, R. S., Rout, C., & Goswami, A. (2021). A bi-objective two-echelon pollution routing problem with simultaneous pickup and delivery under multiple time windows constraint. Opsearch, 1-32. doi:https://doi.org/10.1007/s12597-020-00481-6
39. Perboli, G., Tadei, R., & Vigo, D. (2011). The two-echelon capacitated vehicle routing problem: Models and mathbased heuristics. Transportation Science, 45(3), 364-380. doi: https://doi.org/10.1287/trsc.1110.0368
40. Perboli, G., Tadei, R., & Fadda, E. (2018). New valid inequalities for the two-echelon capacitated vehicle routing problem. Electronic Notes in Discrete Mathematics, 64, 75-84. doi:https://doi.org/10.1016/j.endm.2018.01.009
41. Rao, W., Liu, F., & Wang, S. (2016). An efficient two-objective hybrid local search algorithm for solving the fuel consumption vehicle routing problem. Applied Computational Intelligence and Soft Computing, 2016, 3713918. doi:https://doi.org/10.1155/2016/3713918
42. Reinaldi, M., Redi, A. A. N. P., Prakoso, D. F., Widodo, A. W., Wibisono, M. R., Supranartha, A., Liperda, R. I., Nadlifatin, R., Prasetyo, Y. T., & Sakti, S. (2021). Solving the two echelon vehicle routing problem using simulated annealing algorithm considering drop box facilities and emission cost: a case study of reverse logistics application in Indonesia. Algorithms, 14(9), 259. doi: https://doi.org/10.3390/a14090259
43. Schröder, M., & Cabral, P. (2019). Eco-friendly 3D-Routing: A GIS based 3D-Routing-Model to estimate and reduce CO2-emissions of distribution transports. Computers, Environment and Urban Systems, 73, 40-55. doi:https://doi.org/10.1016/j.compenvurbsys.2018.08.002
44. Scora, G., Boriboonsomsin, K., & Barth, M. (2015). Value of eco-friendly route choice for heavy-duty trucks. Research in Transportation Economics, 52, 3-14. doi:https://doi.org/10.1016/j.retrec.2015.10.002
45. Sluijk, N., Florio, A. M., Kinable, J., Dellaert, N., & Van Woensel, T. (2023). Two-echelon vehicle routing problems: A literature review. European Journal of Operational Research, 304, 865-886. doi:https://doi.org/10.1016/j.ejor.2022.02.022
46. Soysal, M., Bloemhof-Ruwaard, J. M., & Bektaş, T. (2015). The time-dependent two-echelon capacitated vehicle routing problem with environmental considerations. International Journal of Production Economics, 164, 366- 378. doi:https://doi.org/10.1016/j.ijpe.2014.11.016
47. Soysal, M., Çimen, M., & Demir, E. (2018). On the mathematical modeling of green one-to-one pickup and delivery problem with road segmentation. Journal of Cleaner Production, 174, 1664-1678. doi:https://doi.org/10.1016/j.jclepro.2017.11.040
48. Sun, J., & Wang, R. (baskıda). Multi-objective optimization of a sustainable two echelon vehicle routing problem with simultaneous pickup and delivery in construction projects. Journal of Engineering Research. doi: https://doi.org/10.1016/j.jer.2023.10.033 Web of Science Core Collection. Erişim adresi: https://www.webofscience.com, Erişim tarihi: Nisan 2023.
49. Wang, Y., Du, X., Yu, H., Huang, J., & Li, Y. (2015). Impacts of road grade on fuel consumption of light vehicles by use of Google Earth DEM. International Conference on Cyber-Enabled Distributed Computing and Knowledge Discovery, Xi'an, Çin, Eylül, 360-363. doi:https://doi.org/10.1109/CyberC.2015.73
50. Wang, K., Lan, S., & Zhao, Y. (2017). A genetic-algorithm-based approach to the two-echelon capacitated vehicle routing problem with stochastic demands in logistics service. Journal of the Operational Research Society, 68, 1409-1421. doi:https://doi.org/10.1057/s41274-016-0170-7
51. Wang, Y., Zhang, S., Assogba, K., Fan, J., Xu, M., & Wang, Y. (2018). Economic and environmental evaluations in the two-echelon collaborative multiple centers vehicle routing optimization. Journal of Cleaner Production, 197, 443-461. doi:https://doi.org/10.1016/j.jclepro.2018.06.208
52. Wang, Z., & Wen, P. (2020). Optimization of a low-carbon two-echelon heterogeneous-fleet vehicle routing for cold chain logistics under mixed time window. Sustainability, 12(5), 1967. doi:https://doi.org/10.3390/su12051967
53. Wang, Y., Yuan, Y., Guan, X., Xu, M., Wang, L., Wang, H., & Liu, Y. (2020). Collaborative two-echelon multicenter vehicle routing optimization based on state–space–time network representation. Journal of Cleaner Production, 258, 120590. doi: https://doi.org/10.1016/j.jclepro.2020.120590
54. 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. doi:https://doi.org/10.1016/j.ejor.2017.08.011