Heterojen Filolu Yeşil Araç Rotalama Probleminin Tavlama Benzetimi Yöntemi ile Çözümü

Abstract

Araç rotalama problemi, müşterilere siparişlerini ulaştırmak için minimum maliyetli rota kümesinin belirlendiği optimizasyon problemidir. Son yıllarda çevresel duyarlılıktaki artışla beraber, uygulayıcılar ve araştırmacılar fosil yakıtların çevreye olan etkilerini azaltmak için taşıma faaliyetlerinin çevre ile ilgili özelliklerine odaklanmaya başlamıştır. Araç rotalama probleminin bu duyarlılığı dikkate alan türü ise yeşil araç rotalama problemi olarak adlandırılmaktadır. Yeşil araç rotalama problemi son yıllarda üzerinde oldukça yoğun çalışılan bir konudur. Çalışmanın ana motivasyonu, güncel hayatta doğal olarak karşılaşılan heterojen araç filoları için yük toplama/dağıtma rotalarının işlemesi sonucu ortaya çıkan emisyon gazlarının minimize edilmesi amacıyla bir yaklaşım geliştirmektir. Çalışmada, bölge distribütörü olarak faaliyet gösteren bir firmanın dağıtım faaliyetleri heterojen filolu yeşil araç rotalama problemi olarak ele alınmış ve tavlama benzetimi yöntemiyle daha düşük emisyon değerleri sağlayan çevreci çözümler elde edilmeye çalışılmıştır. Çözüm yaklaşımında heterojen bir filo için emisyon değerleri araçların taşıdığı yük miktarı ve yüklerin taşındığı mesafe üzerinden hesaplanmıştır. Yeşil Araç Rotalama çözümleri, standart araç rotalama problemi olarak elde edilen çözümler üzerinden hesaplanan emisyon değerleri ile kıyaslanmıştır. Sonuç olarak, yük miktarı, taşıma mesafesi ve emisyon salınımı ilişkileri nedeniyle önerilen yaklaşım bazı veri setlerinde daha yüksek dolaşım mesafesine karşın daha düşük emisyon miktarı içeren çözümler sağlamıştır. Bütün çözümlerin toplam değeri göz önüne alındığında, seyahat mesafesi bakımından %38,5 ve emisyon değeri bakımından ise %86,7 oranında daha iyi çözümler elde edilmiştir.

Keywords

• Heterojen filo
• Yeşil araç rotalama
• Tavlama benzetimi

Heterogeneous Fleet Green Vehicle Routing Problem with Simulated Annealing Method

Abstract

The vehicle routing problem is an optimization problem in which the minimum cost set of routes is determined to deliver the orders to the customers. With the increase in environmental awareness in recent years, practitioners and researchers have started to focus on the environmental aspects of transportation activities to reduce the environmental impact of fossil fuels. The type of vehicle routing problem that takes this sensitivity into account is called the green vehicle routing problem. The green vehicle routing problem is a subject that has been studied extensively in recent years. The main motivation of the study is to develop an approach in order to minimize the emission gases resulting from the operation of load collection/distribution routes for heterogeneous vehicle fleets that are naturally encountered in daily life. In the study, the distribution activities of a company operating as a regional distributor were handled as a green vehicle routing problem with a heterogeneous fleet and environmental solutions that provide lower emission values were tried to be obtained by the simulated annealing method. In the solution approach, emission values for a heterogeneous fleet are calculated based on the amount of load carried by the vehicles and the distance the loads are transported. The green vehicle routing solutions were compared with the emission values calculated over the solutions obtained as the standard vehicle routing problem. As a result, due to the relationships between load amount, transport distance and emission, the proposed approach provided solutions with lower emission amount despite higher travel distance in some datasets. Considering the total value of all solutions, 38.5% better solutions in terms of travel distance and 86.7% better in terms of emission value are obtained.

Keywords

• Heterogeneous fleet
• Green vehicle routing
• Simulated annealing

References

1. [1] A. Rushton, P. Croucher, and P. Baker, The Hand Book of Logistics and Distribution Management, 3rd ed., London, United Kingdom: Kogan Page Limited, 2006, pp. 6-7.
2. [2] R. Mason-Jones, and D.R. Towill, “Total cycle time compression and the agile supply chain,” International Journal of Production Economics, vol. 62, no.1-2, pp. 61-73, 1999.
3. [3] E.G., Dayıoğlu, K. Karagül, Y. Şahin, and M.G. Kay, “Route planning methods for a modular warehouse system,” An International Journal of Optimization and Control: Theories & Applications, vol. 10, no. 1, pp. 17-25, 2020.
4. [4] Y. Şahin, A. Eroğlu, “Hierarchical solution of order picking and capacitated vehicle routing problems,” Suleyman Demirel University Journal of Engineering Sciences and Design, vol. 3, no. 1, pp. 15-28, 2015.
5. [5] K. Karagul, Y. Sahin, E. Aydemir, and A. Oral, “A simulated annealing algorithm based solution method for a green vehicle routing problem with fuel consumption,” in Lean and Green Supply Chain Management, 1st ed., vol. 273, Cham, Switzerland: Springer Nature Switzerland AG, 2019, pp. 161-187.
6. [6] F. Daneshzand, “The vehicle-routing problem”, in Logistics Operations and Management Concepts and Models, 1st ed., Waltham, USA: Elsevier Insights, 2011, pp. 127-145.
7. [7] C. Lin, K.L. Choy, G.T. Ho, S.H. Chung, and H.Y. Lam, “Survey of green vehicle routing problem: past and future trends,” Expert Systems with Applications, vol. 41, no. 4, pp. 1118-1138, 2014.
8. [8] S. Belbağ, “Yeşil kapasite kısıtlı araç rotalama problemi: bir literatür taraması,” Gazi Üniversitesi İktisadi ve İdari Bilimler Fakültesi Dergisi, c. 19, s. 1, ss. 345-366, 2017.

9. [9] Ç. Koç, ve E. Özceylan, “Yeşil ve elektrikli araç rotalama problemleri üzerine bir literatür taraması ve araştırma öngörüleri” Gaziantep University Journal of Social Sciences, c. 17, s. 3, ss. 1041-1053, 2018.
10. [10] M. Asghari, and S. M. J. M. Al-e-hashem, “Green vehicle routing problem: a state-of-the-art review,” International Journal of Production Economics, vol. 231, pp. 107899, 2021.
11. [11] R. Moghdani, K. Salimifard, E. Demir, and A. Benyettou, “The green vehicle routing problem: a systematic literature review,” Journal of Cleaner Production, vol. 279, pp. 123691, 2021.
12. [12] M. Afshar-Bakeshloo, A. Mehrabi, H. Safari, M. Maleki, and F. Jolai “A green vehicle routing problem with customer satisfaction criteria” Journal of Industrial Engineering International, vol. 12, no. 4, pp. 529-544, 2016.
13. [13] M. Bruglieri, S. Mancini, F. Pezzella, and O. Pisacane, “A new mathematical programming model for the green vehicle routing problem,” Electronic Notes in Discrete Mathematics, vol. 55, no. 2016, pp. 89-92, 2016
14. [14] Ç. Koç, and I. Karaoglan, “The green vehicle routing problem: a heuristic based exact solution approach,” Applied Soft Computing, vol. 39, pp. 154-164, 2016.
15. [15] V. Leggieri, and M. Haouari, “A practical solution approach for the green vehicle routing problem,” Transportation Research Part E: Logistics and Transportation Review, vol. 104, pp. 97-112, 2017.
16. [16] Y. Zhou, and G.M. Lee, “A Lagrangian relaxation-based solution method for a green vehicle routing problem to minimize greenhouse gas emissions,” Sustainability, vol. 9, no. 5, pp. 776, 2017.
17. [17] J. Andelmin, and E. Bartolini, “An exact algorithm for the green vehicle routing problem,” Transportation Science, vol. 51, no. 4, pp. 1288-1303, 2017.
18. [18] E. Aydemir and K. Karagül, “Solving a periodic capacitated vehicle routing problem using simulated annealing algorithm for a manufacturing company,” Brazilian Journal of Operations Production Management, vol. 17, no. 1, pp. 1–13, 2020.
19. [19] Y. Şahin ve A. Eroğlu, “Kapasite kısıtlı araç rotalama problemi için metasezgisel yöntemler bilimsel yazın taraması,” Süleyman Demirel Üniversitesi İktisadi ve İdari Bilimler Fakültesi Dergisi, c. 9, s. 4, ss. 337–355, 2014.
20. [20] S. Erdoğan, and E. Miller-Hooks, “A green vehicle routing problem,” Transportation Research Part E: Logistics and Transportation Review, vol. 48, no. 1, pp. 100-114, 2012.
21. [21] J. Jemai, M. Zekri, and K. Mellouli, “An NSGA-II algorithm for the green vehicle routing problem,” in 12th European Conference (EvoCOP), 2012, pp. 37-48.
22. [22] E. Jabir, V. V. Panicker, and R. Sridharan, “Multi-objective optimization model for a green vehicle routing problem,” Procedia-Social and Behavioral Sciences, vol. 189, pp. 33-39, 2015.
23. [23] E. Jabir, V. V. Panicker, and R. Sridharan, “Design and development of a hybrid ant colony-variable neighbourhood search algorithm for a multi-depot green vehicle routing problem,” Transportation Research Part D: Transport and Environment, vol. 57, pp. 422-457, 2017.
24. [24] A. Tiwari and P. C. Chang, “A block recombination approach to solve green vehicle routing problem,” International Journal of Production Economics, vol. 164, pp. 379-387, 2015.
25. [25] İ. Küçükoğlu, S. Ene, A. Aksoy, and N. Öztürk, “A memory structure adapted simulated annealing algorithm for a green vehicle routing problem,” Environmental Science and Pollution Research, vol. 22, no. 5, pp. 3279-3297, 2015.
26. [26] A. Montoya, C. Guéret, J. E. Mendoza, and J. G. Villegas, “A multi-space sampling heuristic for the green vehicle routing problem,” Transportation Research Part C: Emerging Technologies, vol. 70, pp. 113-128, 2016.
27. [27] S. Zhang, Y. Gajpal, and S.S. Appadoo, “A meta-heuristic for capacitated green vehicle routing problem,” Annals of Operations Research, vol. 269, pp. 753–771, 2018.
28. [28] M. Yavuz, “An iterated beam search algorithm for the green vehicle routing problem,” Networks, vol. 69, no. 3, pp. 317-328, 2017.
29. [29] G. Poonthalir, and R. Nadarajan, “A fuel efficient green vehicle routing problem with varying speed constraint (F-GVRP),” Expert Systems with Applications, vol. 100, pp. 131-144, 2018.
30. [30] P.R.D.O. da Costa, S. Mauceri, P. Carroll, and F. Pallonetto, “A genetic algorithm for a green vehicle routing problem,” Electronic Notes in Discrete Mathematics, vol. 64, pp. 65-74, 2018.
31. [31] M. Affi, H. Derbel, and B. Jarboui, “Variable neighborhood search algorithm for the green vehicle routing problem,” International Journal of Industrial Engineering Computations, vol. 9, no. 2, pp. 195-204, 2018.
32. [32] A. Sruthi, S. P. Anbuudayasankar, and G. Jeyakumar, “Energy-efficient green vehicle routing problem,” International Journal of Information Systems and Supply Chain Management (IJISSCM), vol. 12, no. 4, pp. 27-41, 2019.
33. [33] Y. Li, M. K. Lim, and M. L. Tseng, “A green vehicle routing model based on modified particle swarm optimization for cold chain logistics,” Industrial Management & Data Systems, vol. 119, no. 3, pp. 473-494, 2019.
34. [34] B. Peng, Y., Zhang, Y., Gajpal, and X. Chen, “A memetic algorithm for the green vehicle routing problem,” Sustainability, vol. 11, no. 21, pp. 6055, 2019.
35. [35] N. M. E. Normasari, V. F. Yu, and C. Bachtiyar, “A simulated annealing heuristic for the capacitated green vehicle routing problem,” Mathematical Problems in Engineering, vol. 2019, pp. 1-18, 2019.
36. [36] Y. Li, H. Soleimani, and M. Zohal, “An improved ant colony optimization algorithm for the multi-depot green vehicle routing problem with multiple objectives,” Journal of Cleaner Production, vol. 227, pp. 1161-1172, 2019.
37. [37] D. Utama, D. Widodo, M. F. Ibrahim, and S. K. Dewi, “A new hybrid butterfly optimization algorithm for green vehicle routing problem,” Journal of Advanced Transportation, vol. 2020, pp.1-14, 2020.
38. [38] W. Zhang, Y. Gajpal, S. Appadoo, and Q. Wei, “Multi-depot green vehicle routing problem to minimize carbon emissions,” Sustainability, vol. 12, no. 8, pp. 3500, 2020.
39. [39] M. E. H. Sadati, and B. Çatay, “A hybrid variable neighborhood search approach for the multi-depot green vehicle routing problem,” Transportation Research Part E: Logistics and Transportation Review, vol. 149, pp. 102293, 2021.
40. [40] S. K. Dewi, and D. M. Utama, “A new hybrid whale optimization algorithm for green vehicle routing problem,” Systems Science & Control Engineering, vol. 9, no. 1, pp. 61-72, 2021.
41. [41] C. Blum, and A. Roli, “Metaheuristics in combinatorial optimization: Overview and conceptual comparison,” ACM computing surveys (CSUR), vol. 35, no. 3, pp. 268-308, 2003.
42. [42] A. T. Murray and R. L. Church, “Applying simulated annealing to location-planning models,” Journal of Heuristics, vol. 2, no. 1, pp. 31-53, 1996.
43. [43] D. Karaboğa, Yapay Zeka Optimizasyon Algoritmaları, 2. Baskı, Ankara, Türkiye: Nobel Akademik Yayıncılık, 2011, böl. 2, ss. 21-46.
44. [44] S. Kirkpatrick, C. D. Gelatt, and M. P. Vecchi, “Optimization by simulated annealing,” Science, vol. 220, no. 4598, pp. 671-680, 1983.
45. [45] N. Metropolis, R. Bivins, M. Storm, A. Turkevich, J. M. Miller, and G. Friedlander, “Monte Carlo calculations on intranuclear cascades. I. Low-energy studies,” Physical Review, vol. 110, no. 1, pp. 185-203, 1958.
46. [46] D. S. Johnson, C. R. Aragon, L. A. McGeoch, and C. Schevon, “Optimization by simulated annealing: an experimental evaluation; part I, graph partitioning,” Operations Research, vol. 37, no. 6, pp. 865-892, 1989.
47. [47] R. Tavakkoli-Moghaddam, N. Safaei, M. M. O. Kah, and M. Rabbani, “A new capacitated vehicle routing problem with split service for minimizing fleet cost by simulated annealing,” Journal of the Franklin Institute, vol. 344, no. 5, pp. 406-425, 2007.
48. [48] S. C. Leung, J. Zheng, D. Zhang, and X. Zhou, “Simulated annealing for the vehicle routing problem with two-dimensional loading constraints,” Flexible Services and Manufacturing Journal, vol. 22, no. 1-2, pp. 61-82, 2010.
49. [49] M. R. Wilhelm, and T. L. Ward, “Solving quadratic assignment problems by simulated annealing,” IIE transactions, vol. 19, no. 1, pp. 107-119, 1987.
50. [50] A. T. Murray, and R. L. Church, “Heuristic solution approaches to operational forest planning problems,” Operations-Research-Spektrum, vol. 17, no. 2, pp. 193-203, 1995.
51. [51] N. İnak, S. Tokat ve K. Karagül, “Alt sınır temeline dayalı ağırlıklı tavlama yöntemi ile kutulama probleminin çözümü,” Mehmet Akif Ersoy Üniversitesi İktisadi ve İdari Bilimler Fakültesi Dergisi, c. 5, s. 3, ss. 549-567, 2018.
52. [52] M. D. C. Cunha, and J. Sousa, “Water distribution network design optimization: simulated annealing approach,” Journal of Water Resources Planning and Management, vol. 125, no. 4, pp. 215-221, 1999.
53. [53] M. H. Correia, J. F. Oliveira, and J. S. Ferreira, “Cylinder packing by simulated annealing,” Pesquisa Operacional, vol. 20, no. 2, pp. 269-286, 2000.
54. [54] S. Z. Selim, and K. Alsultan, “A simulated annealing algorithm for the clustering problem,” Pattern Recognition, vol. 24, no. 10, pp. 1003-1008, 1991.
55. [55] B. Türkay, F. Küçüktezcan, ve A. Bulut, “Elektrik enerjisinin bölgeler arası alışverişinin optimizasyonu,” EMO Bilimsel Dergi, c. 1, s. 1, ss. 31-38, 2011.
56. [56] Y. Şahin, “Sezgisel ve metasezgisel yöntemlerin gezgin satıcı problemi çözüm performanslarının kıyaslanması,” Bolu Abant İzzet Baysal Üniversitesi Sosyal Bilimler Enstitüsü Dergisi, c. 19, s. 4, ss. 911-932, 2019.
57. [57] A. G. Nikolaev, and S. H. Jacobson, “Simulated annealing,” in Handbook of Metaheuristics, 2nd ed., vol. 146, Boston, USA: Springer, 2010, pp. 1-39.
58. [58] D. Henderson, S. H. Jacobson, and A. W. Johnson, “The Theory and Practice of Simulated Annealing,” in Handbook of Metaheuristics, 1st ed., Dordrecht, Netherlands: Kluwer Academic Publishers, 2003, pp. 287-319.
59. [59] L. Lin, and C. Fei, “The simulated annealing algorithm implemented by the MATLAB,” International Journal of Computer Science Issues (IJCSI), vol. 9, no. 6, pp. 357-360, 2012.
60. [60] Y. Eren, İ. B. Küçükdemiral, and İ. Üstoğlu, “Introduction to optimization,” in Optimization in Renewable Energy Systems, Oxford, U.K.: Butterworth-Heinemann, 2017, pp. 27-74.