Bi-Objective Green Vehicle Routing Problem Minimizing Carbon Emissions and Maximizing Service Level

Öz

In this study, a bi-objective Green Vehicle Routing Problem (GVRP) is presented as an extension of the well-known Vehicle Routing Problem (VRP). Green Vehicle Routing Problem aims to improve routing decisions of companies using Alternative Fuel Vehicles to reduce carbon emissions. Due to the limited number of Alternative Fuel Stations, alternative fuel vehicles have limited driving distances. Therefore, the routing decisions of alternative fuel vehicles are more critical and difficult. The presented problem herein has two objectives that are the minimization of total carbon emissions and the maximization of service level. While total carbon emission is assumed to be proportional to total distance, cargo delivery time window violations of customers are considered as an indicator of service level. The problem was modeled as Mixed-Integer Linear Programming (MILP) and ε-constraint method, a multi-objective optimization method, is used to solve it. Since this method enumerates all Pareto-optimal solutions of a multi-objective problem, the proposed model presents the best solutions that have different carbon emission and service level values to the decision maker. Our proposed model is tested on six realistically designed hypothetical case studies. Three of the case studies are in the Izmir city while three of the case studies are in the Aegean Region, Turkey. According to the results of this study, the minimization of carbon emission and maximization of service level are two conflicting objectives. As service level increases, the number of vehicles and carbon emissions also increase. As carbon emission increases and time windows violation decreases, more vehicles and alternative fuel stations are used. This shows that increasing service level by decreasing time windows violation requires not only increasing carbon emissions but also increasing total distance and cost. The problem can be solved effectively up to 20 nodes. After 20 nodes, no feasible solution is obtained within the predetermined solution time limit.

Anahtar Kelimeler

• Green Vehicle Routing Problem,Carbon Emission,Service Level,Alternative Fuel Vehicles,Epsilon Constraint,Multi-Objective Optimization

Karbon salınımını azaltan ve hizmet kalitesini arttıran iki amaçlı yeşil araç rotalama problemi

Öz

Bu makalede, optimizasyon literatüründe çok çalışılmış olan Araç Rotalama Probleminin bir genişletmesi olarak iki amaçlı Yeşil Araç Rotalama Problemi tasarlanmıştır. Yeşil Araç Rotalama Problemi, karbon salınımını azaltmak amacıyla Alternatif Yakıtlı Araçlar kullanan firmaların rotalama ile ilgili kararlarını en iyilemeyi amaçlar. Alternatif Yakıt İstasyonu sayısının yetersiz olması sebebiyle Alternatif Yakıtlı Araçların sürüş mesafeleri diğer araçlara göre daha kısıtlıdır. Bu sebeple, alternatif yakıtlı araçlarin rotalama kararları daha hassas ve zordur. Geliştirilmiş olan bu problem, karbon salınımını en aza indirgemek ve hizmet seviyesini en üst düzeye çıkarmak olmak üzere birbiriyle çelişen iki amaca sahiptir. Karbon salınımı toplam rota mesafesi ile orantılı olarak ele alınırken, kargo teslimlerinde müşterilerin zaman penceresi ihlalini bir hizmet seviyesi göstergesi olarak ele alınmıştır. Problem, Karışık Tamsayılı Doğrusal Programlama olarak modellenmiş ve çözümü için çok amaçlı en iyileme yöntemi olan epsilon-kısıtı (ε-kısıtı) yöntemi kullanılmıştır. Bu yöntem bir çok amaçlı en iyileme problebleminde tüm Pareto-optimal çözümleri bulduğundan, ele alınan model karar vericiye farklı karbon emisyonu ve hizmet düzeyindeki tüm en iyi sonuçları sunmaktadır. Hazırlamış olduğumuz model, gerçekçi olarak oluşturduğumuz varsayımsal 6 vaka çalışmasında test edilmiştir. Vaka çalışmalarının üçü İzmir şehir içi dağıtımı için oluşturulurken, üçü de Ege Bölgesi dağıtımı için oluşturulmuştur. Sonuçlara göre karbon salınımını en aza indirgemek ve hizmet seviyesini en üst düzeye çıkarmak çelişmekte olan iki amaçtır. Hizmet seviyesi arttıkça kullanılan araç sayısı ve karbon salınımı da artmaktadır. Karbon salınımı artıp, zaman penceresi ihlali azaldıkça daha çok araç alternatif yakıt istasyonu kullanılmaktadır. Bu, zaman penceresi ihlalini azaltarak müşteri memnuniyetini arttırmanın, sadece karbon salınımı amacından değil, toplam mesafe ve maliyet gibi amaçlardan da feragat etmek gerektiğini göstermektedir. Problem, 20 düğüme kadar etkili bir şekilde çözülmüştür, ancak 20 düğümden sonra belirlenen zaman kısıtı içinde olurlu çözüm bulunamamıştır.

Anahtar Kelimeler

• Yeşil Araç Rotalama Problemi,Karbon Salınımı,Hizmet Seviyesi,Alternatif Yakıtlı Araçlar,Epsilon Kısıtı,Çok Amaçlı Optimizasyon

Kaynakça

1. Beamon, B. M., Supply chain design and analysis: Models and methods, International Journal of Production Economics, 55 (3), 281-294, 1998.
2. Erdoğan, S. ve Miller-Hooks, E., A green vehicle routing problem, Transportation Research Part E: Logistics and Transportation Review, 48 (1), 100-114, 2012.
3. Bérubé, J. F., Gendreau, M. ve Potvin, J. Y., An exact ε-constraint method for bi-objective combinatorial optimization problems: Application to the traveling salesman problem with profits, European Journal of Operational Research, 194 (1), 39-50, 2009.
4. Savelsbergh, M. W., The Vehicle Routing Problem with Time Windows: Minimizing Route Duration, ORSA Journal on Computing, 4 (2), 146-154, 1992.
5. Dumas, Y., Desrosiers, J. ve Soumis, F., The pickup and delivery problem with time windows, European Journal of Operational Research, 54 (1), 7-22, 1991.
6. Mingyong, L. ve Erbao, C., An improved differential evolution algorithm for vehicle routing problem with simultaneous pickups and deliveries and time windows, Engineering Applications of Artificial Intelligence, 23 (2), 188-195, 2010.
7. Huang, Y., Shi, C., Zhao, L. ve Van Woensel, T., A study on carbon reduction in the vehicle routing problem with simultaneous pickups and deliveries, IEEE International Conference on Service Operations and Logistics, and Informatics, 302-307, July, 2012.
8. Ho, S. C. ve Haugland, D., A tabu search heuristic for the vehicle routing problem with time windows and split deliveries, Computers & Operations Research, 31 (12), 1947-1964, 2004.

9. Hiermann, G., Puchinger, J., Ropke, S. ve Hartl, R. F., The electric fleet size and mix vehicle routing problem with time windows and recharging stations, European Journal of Operational Research, 252 (3), 995-1018, 2016.
10. Niu, Y., Yang, Z., Chen, P., ve Xiao, J., Optimizing the green open vehicle routing problem with time windows by minimizing comprehensive routing cost, Journal of Cleaner Production, 171, 962-971, 2018.
11. Tang, J., Pan, Z., Fung, R. Y. ve Lau, H., Vehicle routing problem with fuzzy time windows, Fuzzy Sets and Systems, 160 (5), 683-695, 2009.
12. Figliozzi, M., Vehicle routing problem for emissions minimization, Transportation Research Record, 2197 (1), 1-7, 2010.
13. Zhang, J., Zhao, Y., Xue, W. ve Li, J., Vehicle routing problem with fuel consumption and carbon emission, International Journal of Production Economics, 170, 234-242, 2015.
14. Bektaş, T. ve Laporte, G., The pollution-routing problem, Transportation Research Part B: Methodological, 45 (8), 1232-1250, 2011.
15. Franceschetti, A., Honhon, D., Van Woensel, T., Bektaş, T. ve Laporte, G., The time-dependent pollution-routing problem, Transportation Research Part B: Methodological, 56, 265-293, 2013.
16. Koç, Ç., Bektaş, T., Jabali, O. ve Laporte, G., The fleet size and mix pollution-routing problem, Transportation Research Part B: Methodological, 70, 239-254, 2014.
17. Kwon, Y. J., Choi, Y. J. ve Lee, D. H., Heterogeneous fixed fleet vehicle routing considering carbon emission, Transportation Research Part D: Transport and Environment, 23, 81-89, 2013.
18. Elbouzekri, A., Elhassania, M. E. S. S. A. O. U. D. ve Alaoui, A. E. H., A hybrid ant colony system for green capacitated vehicle routing problem in sustainbale transport, Journal of Theoretical and Applied Information Technology, 54 (2), 2013.
19. Liu, W. Y., Lin, C. C., Chiu, C. R., Tsao, Y. S. ve Wang, Q., Minimizing the carbon footprint for the time-dependent heterogeneous-fleet vehicle routing problem with alternative paths, Sustainability, 6 (7), 4658-4684, 2014.
20. Kabadurmuş, Ö., Erdoğan, M. S., Özkan, Y., ve Köseoğlu, M., A Multi-Objective solution of green vehicle routing problem, Logistics & Sustainable Transport, 10 (1), 31-44, 2019.
21. Xiao, Y. ve Konak, A., The heterogeneous green vehicle routing and scheduling problem with time-varying traffic congestion, Transportation Research Part E: Logistics and Transportation Review, 88, 146-166, 2016.
22. Demir, E., Bektaş, T. ve Laporte, G., The bi-objective pollution-routing problem, European Journal of Operational Research, 232 (3), 464-478, 2014.
23. Zhong, Y. ve Cole, M. H., A vehicle routing problem with backhauls and time windows: a guided local search solution. Transportation Research Part E: Logistics and Transportation Review, 41 (2), 131-144, 2005.
24. Demir, E., Bektaş, T. ve Laporte, G., An adaptive large neighborhood search heuristic for the pollution-routing problem, European Journal of Operational Research, 223 (2), 346-359, 2012.
25. Keçeci, B., Altıparmak, F. ve Kara, İ., Heterojen eş-zamanli topla-dağit araç rotalama problemi: Matematiksel modeller ve sezgisel bir algoritma, Gazi Üniversitesi Mühendislik-Mimarlık Fakültesi Dergisi, 30 (2), 2015.
26. Deb, K., Multi-objective optimization using evolutionary algorithms, Cilt 16, John Wiley & Sons, New York, A.B.D., 2001.
27. Mavrotas, G., Effective implementation of the ε-constraint method in multi-objective mathematical programming problems, Applied Mathematics and Computation, 213 (2), 455-465, 2009.
28. McKinnon, A. C. ve Piecyk, M., Measuring and managing CO2 emissions in European chemical transport, CEFIC, 2010.