Esra BOZ, Ahmet ÇALIK, Yusuf ŞAHİN

606668

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

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.
Anahtar Kelimeler:

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

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,

PDF

___

  • [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.
Gazi Üniversitesi Mühendislik Mimarlık Fakültesi Dergisi-Cover
  • ISSN: 1300-1884
  • Yayın Aralığı: 4
  • BaÅŸlangıç: 1986
  • Yayıncı: OÄŸuzhan YILMAZ
ArÅŸiv
Sayıdaki Diğer Makaleler

Üç duygu ile etiketlenmiş Türkçe ses kayıt verilerinin makine öğrenim algoritmalarıyla analizi

Abdülkadir TEPECİK, Engin DEMİR

Dersliklerde kabul edilebilir COVID-19 enfeksiyon riskine dayalı belirlenen havalandırma oranlarının ısıtmadan kaynaklanan enerji tüketimine etkisi

Hasan Murat ÇETİN

Süperkapasitör: Temelleri ve malzemeleri

Çağatay ÖZADA, Merve ÜNAL, Murat YAZICI

Puzolinik malzemelerin (dip külü ve zeolit) tane boyutunun harcın alkali-silika reaksiyonuna ve basınç dayanımına etkisi

Bahri ERSOY, Fahri YENTÃœRK, Zeyni ARSOY, Tayfun UYGUNOÄžLU

Destek vektör makinesi ile elde edilen olasılık çıktılarına dayalı yeni bir istatistiksel süreç izleme yöntemi

Zümre ÖZDEMİR GÜLER, M. Akif BAKIR, Filiz KARDİYEN

Ergiyik filament ile imalat yönteminde kullanılan PLA ve çelik katkılı PLA filament malzemelerin mekanik ve fiziksel özelliklerinin incelenmesi

Ali Osman ER, Osman Muhsin AYDINLI

Eklemeli imalat yönteminde polilaktik asit (PLA)/peroksit kompozitinin in-situ olarak çapraz bağlama tekniği ile üretilebilirliğinin araştırılması

Musa YILMAZ, Necip Fazıl YILMAZ, Ali KILIÇ, Hidayet MAZI

Atık sulardan boyar madde giderimi için çeltik artıklarından karbon esaslı sorbentlerin hazırlanması

Zeynep Cansu ULUTAŞ, Dilşad Dolunay ESLEK KOYUNCU, Müjgan OKUR

Tektürel zaman pencereli araç rotalama problemi için eniyilenmiş altın oran sarmalı başlangıç çözümlü uyarlanmış büyük komşuluk arama algoritması

Alperen Ekrem ÇELİKDİN

Geleneksel ahşap çerçeve sistem konut yapılarında dış duvarların higrotermal performansının değerlendirilmesi: Safranbolu ve Zeyrek örneği

Seda Nur ALKAN, Fatih YAZICIOÄžLU