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

Year 2024, Volume: 8 Issue: 1, 215 - 240, 18.07.2024

Ergül Kısa Toğrul

https://doi.org/10.56554/jtom.1302872

Abstract

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.

Keywords

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ı

Abstract

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.

Keywords

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

References

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