Yeşil zaman pencereli ve eş zamanlı topla dağıt araç rotalama problemlerinin metasezgisel yöntemlerle çözümü

Year 2024, Volume: 39 Issue: 2, 757 - 770, 30.11.2023

Esra Boz Ahmet Çalık Yusuf Şahin

https://doi.org/10.17341/gazimmfd.1180965

Abstract

Araç rotalama problemi, merkezi bir depodan farklı koordinatlarda yer alan müşterilere belirli kapasiteye sahip araçlarla yapılacak dağıtım için en kısa dağıtım rotasının belirlendiği bütünleşik bir optimizasyon problemidir. Artan çevresel duyarlılık ve problemin gerçek hayata daha uygun hale getirilmesi için zaman, eş zamanlı toplama ve dağıtım, rota uzunluğu, çoklu depo, teslimat bölme, yakıt tüketimi ve karbon emisyonu gibi kısıtlar probleme eklenerek yeni varyantlar ortaya konmuştur. Bu çalışmada, çevresel duyarlılığın ön plana çıktığı yeşil araç rotalama problemi, zaman pencereli ve eş zamanlı topla dağıt araç rotalama problemleri bütünleşik olarak ele alınmaktadır. Bu noktada, toplama ve dağıtım talepleri, siparişlerin teslim zamanları ve dağıtım esnasında sürdürülebilirliğin sağlanabilmesi için çevresel faktörler de önemli bir etken olarak göz önüne alınmıştır. Çalışma kapsamında Yeşil Zaman Pencereli ve Eş Zamanlı Topla Dağıt Araç Rotalama Problemi (YZPETDARP) için yeni karma tamsayılı doğrusal olmayan matematiksel model oluşturulmuş, belirli şartlar altında model doğrusallaştırılarak farklı yöntemler ile çözüm aranmıştır. YZPETPARP’nin çözümü için metasezgisel arama algoritmaları olan Genetik Algoritma (GA) ve Ağırlıklı Süperpozisyon Çekim Algoritması (ASÇA) önerilmiş, literatürdeki ilgili veriler entegre edilerek test verileri oluşturulmuştur. Deneysel çalışmalar sonucunda çözüm uygunluk değeri ve çözüm süresi bakımından GA ile daha iyi sonuçlara ulaşılmış, or-opt sezgiseli ile entegre edilen ASÇA ise GA ile elde edilen sonuçlara yakın ve tatmin edici sonuçlar vermiştir.

Keywords

Yeşil araç rotalama, Eş zamanlı topla dağıt araç rotalama, Zaman pencereli araç rotalama, genetik algoritma

Solution of green simultaneous pickup and delivery vehicle routing problem with time window using metaheuristic methods

Abstract

The vehicle routing problem is an integrated optimization problem in which the shortest distribution route is determined for the distribution to be made from a central depot to customers located at different coordinates, with vehicles with a certain capacity. Increasing environmental awareness and constraints such as time, simultaneous pickup and delivery, route length, multiple depots, load division, fuel consumption, and carbon emissions have been added to the problem. New variants have been introduced to make the problem more suitable for real life. In this study, the green vehicle routing problem, in which environmental sensitivity is at the forefront, and the simultaneous pickup and delivery vehicle routing problems with time windows are discussed in an integrated manner. At this point, environmental factors are also considered important factors to ensure sustainability during collection and distribution demands, delivery times of orders, and distribution. Within the scope of the study, a new mixed integer nonlinear mathematical model was proposed for the green and simultaneous pickup and delivery vehicle routing problem with time window (GSPDVRP-TW), and a solution was sought with different methods by linearizing the model under certain conditions. For the solution of GSPDVRP-TW, the metaheuristic search algorithms Genetic Algorithm (GA) and Weighted Superposition Attraction Algorithm (WSA) were proposed, and test data were created by integrating the relevant data in the literature. As a result of the experimental studies, better results were obtained with GA in terms of solution fitness value and solution time, and WSA integrated with the or-opt heuristic gave satisfactory results close to the results obtained with GA.

Keywords

Genetic algorithm

References

• [1] Li, J., Wang, D., Zhang, J., Heterogeneous fixed fleet vehicle routing problem based on fuel and carbon emissions, J. Clean. Prod., 201, 896-908, 2018.
• [2] Karagul, K., Sahin, Y., Aydemir, E., Oral, A. A simulated annealing algorithm based solution method for a green vehicle routing problem with fuel consumption, Lean and Green Supply Chain Management. International Series in Operations Research & Management Science, Springer, Cilt 273, Editör: Paksoy, T., Weber, GW., Huber, S., Springer Nature Switzerland, Cham, Switzerland, 161-187, 2019.
• [3] Zhou, Y., Sheu, J.B., Wang, J., Robustness assessment of urban road network with consideration of multiple hazard events, Risk Anal., 37 (3), 1477–1494, 2017.
• [4] Zhang, W., Gajpal, Y., Appadoo, S., Wei, Q., Multi-depot green vehicle routing problem to minimize carbon emissions. Sustainability, 12(8), 3500, 2020.
• [5] Tokat, S., Karagul, K., Sahin, Y., Aydemir, E., Fuzzy c-means clustering-based key performance indicator design for warehouse loading operations, J. King Saud Univ. - Comput. Inf. Sci., 34(8), 6377-6384, 2022.
• [6] Waters, D., Logistics: An Introduction to Supply Chain Management, Palgrave Macmillan, Basingstoke, England, 2003.
• [7] Kay, M. G., Karagul, K., Şahin, Y., Gunduz, G., Minimizing Total Logistics Cost for Long-Haul Multi-Stop Truck Transportation. Transp. Res. Rec., 2676(2), 367-378, 2022.
• [8] Dayıoğlu, E. G., Karagül, K., Şahin, Y., Kay, M. G. (2020). Route planning methods for a modular warehouse system, Int. J. Optim. Control: Theor. Appl., 10(1), 17-25, 2020.
• [9] Karagül, K., Güngör, İ., A case study of heterogeneous fleet vehicle routing problem: Touristic distribution application in Alanya, Int. J. Optim. Control: Theor. Appl., 4(2), 67-76, 2014.
• [10] Zhang, M., Pratap, S., Zhao, Z., Prajapati, D., Huang, G.Q., Forward and reverse logistics vehicle routing problems with time horizons in B2C e-commerce logistics, Int. J. Prod. Res., 59(20), 6291-6310, 2021.
• [11] Cordeau, J. F., Laporte, G., Modelling and optimization of vehicle routing problems, Handbook on Modelling for Discrete Optimization, Cilt 1, Appa G., Pitsoulis, L., Williams, H.P., Springer, New York , A.B.D., 151-181,2006.
• [12] Şahin, Y., Eroğlu, A., Kapasite Kısıtlı Araç Rotalama Problemi İçin Metasezgisel Yöntemler: Bilimsel Yazın Taraması. Süleyman Demirel Üniversitesi İktisadi ve İdari Bilimler Fakültesi Dersi, 19(4), 337-355, 2014.
• [13] Aydemir, E., Karagül, K., Tokat, S., Kapasite Kısıtlı Araç Rotalama Problemlerinde Başlangıç Rotalarının Kurulması İçin Yeni Bir Algoritma, Mühendislik Bilimleri ve Tasarım Dergisi, 4(3), 215-226, 2016.
• [14] Belgin, Ö., Karaoğlan, İ., Altıparmak, F., İki aşamalı eş zamanlı topla-dağıt araç rotalama problemi için matematiksel programlama tabanlı sezgisel yaklaşım, Gazi Üniversitesi Mühendislik Mimarlık Fakültesi Dergisi, 36(3), 1565-1580, 2021.
• [15] Marinakis, Y., Marinaki, M., Migdalas, A., A multi-adaptive particle swarm optimization for the vehicle routing problem with time Windows, Information Sciences, 481, 311-329, 2019.
• [16] Dantzig, G.B., Ramser, J.H., The truck dispatching problem, Management science, 6(1), 80-91, 1959.
• [17] Çetin, S., Gencer, C., Kesin Zaman Pencereli-Eş Zamanlı Dağıtım Toplamalı Araç Rotalama Problemi: Matematiksel Model, Gazi Üniversitesi Mühendislik Mimarlık Fakültesi Dergisi, 25(3), 579-585, 2010.
• [18] Clarke, G., Wright, J.W., Scheduling of vehicles from a central depot to a number of delivery points, Operations research, 12(4), 568-581, 1964.
• [19] Christofides, N., Mingozzi, A., Toth, P., State space relaxation procedures for the computation of bounds to routing problems, Networks, 11, 145-164, 1981.
• [20] Christofides, N., Vehicle scheduling and routing. Paper presented in 12th International Symposium on Mathematical Programming, Massachusetts Institute of Technology, Massachusetts, 1985.
• [21] Fisher, M. L., Optimal Solution of Vehicle Routing Problems Using Minimum K-trees, Operations Research, 42, 626-642, 1994.
• [22] Miller, D. L., A matching based algorithm for capacitated vehicle routing problems, ORSA Journal on Computing, 7 (1), 1-9, 1995.
• [23] Fukasawa, R., Longo, H., Lysgaard, J., Poggi de Aragao, M., Reis, M., Uchoa, E., Werneck, R. F., Robust branch-and-cut-and-price for the capacitated vehicle routing problem, Mathematical Programming, 106, 491-511, 2006.
• [24] Baldacci, R., Christofides, N., & Mingozzi, A., An exact algorithm for the vehicle routing problem based on the set partitioning formulation with additional cuts, Mathematical Programming, 115 (2), 351-385, 2008.
• [25] Hadjiconstantinou, E., Christofides, N., An exact algorithm for general, orthogonal, two-dimensional knapsack problems, European Journal of Operational Research, 83 (1), 39-56, 1995.
• [26] Bramel, J., Simchi-Levi, D., Set-Covering-Based Algorithms for the Capacitated VRP. In P. Toth & D. Vigo (Edt.), The Vehicle Routing Problem (pp. 85-108). Philadelphia: SIAM, 2002.
• [27] Erdoğan, S., Miller-Hooks, E., A green vehicle routing problem, Transportation research part E: logistics and transportation review, 48(1), 100-114, 2012
• [28] Demir, E., Bektaş, T., Laporte, G., A review of recent research on green road freight transportation. European journal of operational research, 237(3), 775-793, 2014.
• [29] Demir, E., Bektas, T., Laporte, G., A comparative analysis of several vehicle emission models for road freight transportation. Transportation Research Part D: Transport and Environment, 6(5), 347–357, 2011.
• [30] Bektaş, T., Laporte, G., The pollution-routing problem, Transportation Research Part B: Methodological, 45(8), 1232-1250, 2011.
• [31] Demir, E., Bektaş, T., Laporte, G., An adaptive large neighborhood search heuristic for the pollution-routing problem, European journal of operational research, 223(2), 346-359, 2012.
• [32] Schneider, M., Stenger, A., Goeke, D., The electric vehicle-routing problem with time windows and recharging stations, Transportation science, 48(4), 500-520, 2014.
• [33] Lin, C., Choy, K. L., Ho, G.T., Ng, T.W., A genetic algorithm-based optimization model for supporting green transportation operations, Expert systems with applications, 41(7), 3284-3296, 2014.
• [34] Majidi, S., Hosseini-Motlagh, S. M., Yaghoubi, S., Jokar, A., Fuzzy green vehicle routing problem with simultaneous pickup–delivery and time Windows, RAIRO-operations research, 51(4), 1151-1176, 2017.
• [35] Majidi, S., Hosseini-Motlagh, S.M., Ignatius, J., Adaptive large neighborhood search heuristic for pollution-routing problem with simultaneous pickup and delivery, Soft Computing, 22(9), 2851-2865, 2018.
• [36] Madankumar, S., Rajendran, C., Mathematical models for green vehicle routing problems with pickup and delivery: A case of semiconductor supply chain, Computers & Operations Research, 89, 183-192, 2018.
• [37] Yu, Y., Wang, S., Wang, J., Huang, M., A branch-and-price algorithm for the heterogeneous fleet green vehicle routing problem with time Windows, Transportation Research Part B: Methodological, 122, 511-527, 2019.
• [38] Xu, Z., Elomri, A., Pokharel, S., Mutlu, F., A model for capacitated green vehicle routing problem with the time-varying vehicle speed and soft time Windows, Computers & Industrial Engineering, 137, 106011, 2019.
• [39] Li, Y., Soleimani, H., Zohal, M., An improved ant colony optimization algorithm for the multi-depot green vehicle routing problem with multiple objectives. Journal of cleaner production, 227, 1161-1172, 2019.
• [40] Macrina, G., Pugliese, L.D.P., Guerriero, F., Laporte, G., The green mixed fleet vehicle routing problem with partial battery recharging and time Windows, Computers & Operations Research, 101, 183-199, 2019.
• [41] Yu, Z., Zhang, P., Yu, Y., Sun,w., Huang, M., An Adaptive Large Neighborhood Search for the Larger-Scale Instances of Green Vehicle Routing Problem with Time Windows, Complexity, 14 pages, 2020.
• [42] Utama, D. M., Fitria, T.A., Garside, A.K., Artificial bee colony algorithm for solving green vehicle routing problems with time windows. Journal of Physics: Conference Series, 1933 (1), 012043, 2021.
• [43] Dengiz, A.Ö., Atalay, K., Altıparmak, F., Evde sağlık hizmetlerinde çok amaçlı, çok turlu ve zaman pencereli rotalama problemi için hedef programlama yaklaşımı, Gazi Üniversitesi Mühendislik Mimarlık Fakültesi Dergisi, 36(4), 2167-2182, 2021.
• [44] Sadat Hosseini Khajouei, M. H., Pilevari, N., Developing an environmental vehicle routing problem with simultaneous pickup and delivery: Mathematical model and a discrete invasive weed optimization approach, Journal of Industrial Engineering and Management Studies, 8(1), 202-217, 2021.
• [45] Fakhrzad, M., Hoseini Shorshani, S., Hosseininasab, H., Mostafaeipour, A., 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., (In Press), doi: 10.22075/ijnaa.2021.23209.2493, 2022.
• [46] Prajapati, D., Chan, F.T., Daultani, Y., Pratap, S., Sustainable vehicle routing of agro-food grains in the e-commerce industry. International Journal of Production Research, 1-26, 2022.
• [47] Toth, P., Vigo, D. (2002). An overview of vehicle routing problems. Toth, P., & Vigo, D. (Edt.), The Vehicle Routing Problem içinde (s. 1-26). Philadelphia: SIAM.
• [48] Laporte G., The Vehicle Routing Problem: An overview of exact and approximate algorithms, European Journal of Operational Research, 59, 345 – 358, 1992.
• [49] Keçeci, B., Altıparmak, F., Kara, İ., Heterojen Eş-Zamanli Topla-Dağit Araç Rotalama Problemi̇: Matemati̇ksel Modeller ve Sezgi̇sel Bi̇r Algori̇tma. Gazi Üniversitesi Mühendislik Mimarlık Fakültesi Dergisi, 30(2), 185-195, 2015.
• [50] Chen, G., Wu, X., Li, J., Guo, H., Green vehicle routing and scheduling optimization of ship steel distribution center based on improved intelligent water drop algorithms, Math. Probl. Eng., 2020, 13 pages, 2020.
• [51] Yağmur, E., Kesen, S.E., Multi-trip heterogeneous vehicle routing problem coordinated with production scheduling: Memetic algorithm and simulated annealing approaches, Comput Ind Eng., 161, 107649, 2021.
• [52] Baykasoğlu, A., Akpinar, Ş., Weighted superposition attraction (WSA): a swarm intelligence algorithm for optimization problems–part 2: constrained optimization, Appl. Soft Comput., 37(2015), 396-415, 2015.
• [53] Holland, John H (1975) Adaptation in Natural and Artificial Systems. University of Michigan Press, Ann Arbor, 207s.
• [54] Baykasoğlu, A., Akpinar, Ş., Weighted superposition attraction (WSA): a swarm intelligence algorithm for optimization problems– part 1: Unconstrained optimization, Appl. Soft Comput., 56(2017), 520-540, 2017.
• [55] Baykasoğlu, A., Ozsoydan, F.B., Dynamic optimization in binary search spaces via weighted superposition attraction algorithm, Expert Syst. Appl., 96, 157-174, 2018.
• [56] Baykasoğlu, A., Ozsoydan, F.B., Senol, M.E., Weighted superposition attraction algorithm for binary optimization problems, Operational Research, 20(4), 2555-2581, 2020.
• [57] Baykasoğlu, A., Şenol, M.E., Weighted superposition attraction algorithm for combinatorial optimization, Expert Syst. Appl., 138(2019), 112792, 2019.
• [58] Gen, M., & Cheng, R., (1997), "Genetic Algorithms and Engineering Design", Amerika Birleşik Devletleri, John Wiley & Sons, Inc.
• [59] Şahin, Y., & Kulak, O. (2013). Depo Operasyonlarının Planlanması İçin Genetik Algoritma Esaslı Modeller. Uluslararası Alanya İşletme Fakültesi Dergisi, 5 (3), 141-153.
• [60] Şahin Y. Depo Operasyonları ve Sipariş Dağıtım Faaliyetlerinin Sezgisel Yöntemler Kullanarak Eş Zamanlı Optimizasyonu. Doktora Tezi, Süleyman Demirel Üniversitesi, Isparta, Türkiye, 2014.
• [61] Şen, Z., (2004). Genetik Algoritmalar ve En İyileme Yöntemleri. İstanbul: Su Vakfı Yayınları.
• [62] Solomon, M. M. (1987). Algorithms for the vehicle routing and scheduling problems with time window constraints. Operations research, 35(2), 254-265.
• [63] Dethloff, J. (2001). Vehicle routing and reverse logistics: the vehicle routing problem with simultaneous delivery and pick-up. OR-Spektrum, 23(1), 79-96.
• [64] Prins, C. (2004). A simple and effective evolutionary algorithm for the vehicle routing problem. Computers & operations research, 31(12), 1985-2002.
• [65] Talbi, E. G. (2009). Metaheuristics: from design to implementation (Vol. 74). John Wiley & Sons.
• [66] Rylander, S.G.B., Gotshall, B. (2002). Optimal population size and the genetic algorithm. Population, 100(400), 900.