SOLUTION OF THE TRAVELING SALESMAN PROBLEM IN PACKAGE DISTRIBUTION WITH DRONE WITH GENETICS AND PARTICLE SWARM OPTIMIZATION ALGORITHMS

Yıl 2023, , 168 - 181, 31.08.2023

Enes Buğra Acar , Cumali Karabey , Bayram Köse

https://doi.org/10.54365/adyumbd.1249391

Öz

In this article, the use of emergency medicine and treatment kits in the field of health is solved using Genetic Algorithm (GA) and Particle Swarm Optimization (PSO) Algorithm as a traveling salesman problem among non-polynomial hard problems. This work is of significant value to researchers and industry professionals looking for new methods of cargo logistics and transportation. Effectively optimizing package delivery by UAV has the potential to increase the efficiency of the logistics industry. With the route results found, an optimal roadmap for drone package delivery was created. Firstly, EIL51 data from TSPLIB used as the data set. After that, the locations of the pharmacies in the Menemen district of İzmir were taken from real life. We evaluate the results, it was seen that GA took longer due to the algorithm content and GA provided a more optimized route than PSO.

Anahtar Kelimeler

Traveling Salesman Problem (GSP), Genetic Algorithm (GA), Particle Swarm Optimization Algorithm (PSO), Cargo Drone

İNSANSIZ HAVA ARACI İLE PAKET DAĞITIMINDA GEZGİN SATICI PROBLEMİNİN GENETİK VE PARÇACIK SÜRÜ OPTİMİZASYON ALGORİTMALARI İLE ÇÖZÜMÜ

Öz

Bu makalede kargo alanında kullanılmak üzere insansız hava aracının (İHA), polinom olmayan (Non-polynomial) zor problemler arasındaki gezgin satıcı problemi (GSP) Genetik Algoritma (GA) ve Parçacık Sürü Optimizasyonu (PSO) Algoritması ile çözülmüştür. Bu çalışma, kargo lojistiği ve taşımacılığında yeni yöntemler arayan araştırmacılar ve endüstri uzmanları için önemli bir değer taşımaktadır. İHA tabanlı paket dağıtımının etkin bir şekilde optimize edilmesi, lojistik sektörünün verimliliğini artırma potansiyeli taşımaktadır. Öncelikle veri seti olarak TSPLIB’den EIL51 verileri kullanılmıştır. Sonrasında gerçek hayattan kargo teslimatına örnek olarak sıhhi paket taşıması için İzmir ili Menemen ilçesindeki eczanelerin lokasyonları alınmıştır. Bulunan rota sonuçları ile İHA paket teslimatında optimal yol haritası çıkartılmıştır. Sonuçlara bakıldığında, GA’nın algoritma içeriğinden dolayı daha uzun sürdüğü ve GA’nın PSO’ya göre daha optimize edilmiş bir rota sağladığı görülmüştür.

Anahtar Kelimeler

Gezgin Satıcı Problemi (GSP), Genetik Algoritma (GA), Parçacık Sürü Optimizasyon Algoritma (PSO), Kargo İHA

Kaynakça

• Çalişkan F., Yüksel H., Dayik M., Genetik Algoritmaların Tasarım Sürecinde Kullanılması, 2016
• Yildirim T., Simetrik Gezgin Satici Problemi Için Yeni Bir Meta-Sezgisel: Kör Fare Algoritmasi, Denizli, Şubat - 2014
• Pulat M., Kocakoç D., Gezgin Satici Probleminin Genetik Algoritmalarla Çözümünde Başlangiç Popülasyonun Belirlenmesi, July 2017
• Kuzu S., Önay O., Şen U., Tunçer M., Yildirim B. F., Keskintürk T., Gezgin satıcı problemlerinin metasezgiseller ile çözümü, Cilt/Vol:43, Sayı/No:1, 2014, 1–27
• Turğut, M. ve Şeker, B. (2022). İnsansiz Hava Araçlarinin (İha) Taşimacilikta Kullanimina Yönelik Keşfedici Bir Araştirma: Drone Taşimaciliği Ve Uygulamalari. Akıllı Ulaşım Sistemleri Ve Uygulamaları Dergisi, 5 (2), 169-187. Doi: 10.51513/Jitsa.1146992
• Nakiboğlu, G. (2020), Drone Taşımacılığı ve Son-Adım Teslimatta Kullanımı, Çukurova Üniversitesi İİBF Dergisi Cilt:24. Sayı:2, ss.285-298
• Uslu, F., Tekin, Z. (2021), Pandemi Sürecinde Drone Kullanımı: Geleceğin Lojistik Teknolojileri, Uluslararası İktisadi ve İdari Bilimler Kongresi: Krizler, Belirsizlikler ve Arayışlar, 165
• Yetiş, H., Güngör, Z. ve Karaköse, M. (2021). Araç-İHA İş birliği ile Kargo Teslimatları İçin Ortak Rota Optimizasyonu. Fırat Üniversitesi Fen Bilimleri Dergisi, 33 (2), 135-144. Retrieved from https://dergipark.org.tr/en/pub/fufbd/issue/64918/878774
• Angeniol, B., Vaubois, G. D. L. C., & Le Texier, J. Y. (1988). Self-organizing feature maps and the travelling salesman problem. Neural Networks, 1(4), 289-293.
• Somhom, S., Modares, A., & Enkawa, T. (1997). A self-organising model for the travelling salesman problem. Journal of the Operational Research Society, 48(9), 919-928.
• Ellabib, I., Calamai, P., & Basir, O. (2007). Exchange strategies for multiple ant colony system. Information Sciences, 177(5), 1248-1264.
• Nguyen, H. D., Yoshihara, I., Yamamori, K., & Yasunaga, M. (2007). Implementation of an effective hybrid GA for large-scale traveling salesman problems. IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics), 37(1), 92-99.
• Sauer, J. G., & dos Santos Coelho, L. (2008, September). Discrete differential evolution with local search to solve the traveling salesman problem: Fundamentals and case studies. In 2008 7th ieee international conference on cybernetic intelligent systems (pp. 1-6). IEEE.
• Shi, X., Wang, L., Zhou, Y., & Liang, Y. (2008, October). An ant colony optimization method for prize-collecting traveling salesman problem with time windows. In 2008 Fourth International Conference on Natural Computation (Vol. 7, pp. 480-484). IEEE.
• Xie, X. F., & Liu, J. (2008). Multiagent optimization system for solving the traveling salesman problem (TSP). IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics), 39(2), 489-502.
• Yi, J., Bi, W., Yang, G., & Tang, Z. (2008, November). A fast elastic net method for traveling salesman problem. In 2008 Eighth International Conference on Intelligent Systems Design and Applications (Vol. 1, pp. 462-467). IEEE.
• Chien, C. Y., & Chen, S. M. (2009, July). A new method for handling the traveling salesman problem based on parallelized genetic ant colony systems. In 2009 International Conference on Machine Learning and Cybernetics (Vol. 5, pp. 2828-2833). IEEE.
• Cheng, C. B., & Wang, K. P. (2009). Solving a vehicle routing problem with time windows by a decomposition technique and a genetic algorithm. Expert systems with applications, 36(4), 7758-7763.
• Liu, F., & Zeng, G. (2009). Study of genetic algorithm with reinforcement learning to solve the TSP. Expert Systems with Applications, 36(3), 6995-7001.
• Naimi, H. M., & Taherinejad, N. (2009). New robust and efficient ant colony algorithms: Using new interpretation of local updating process. Expert Systems with Applications, 36(1), 481-488.
• Marinakis, Y., & Marinaki, M. (2010). A hybrid genetic–Particle Swarm Optimization Algorithm for the vehicle routing problem. Expert Systems with Applications, 37(2), 1446-1455.
• Chang, T. K., Huang, C. H., Huang, C. H., Chen, H. C., & Cheng, C. K. (2010). The influence of long-term treadmill exercise on bone mass and articular cartilage in ovariectomized rats. BMC Musculoskeletal Disorders, 11(1), 1-7.
• Chen, S. M., & Chien, C. Y. (2011). Solving the traveling salesman problem based on the genetic simulated annealing ant colony system with particle swarm optimization techniques. Expert Systems with Applications, 38(12), 14439-14450.
• Çolak S, Genetik Algoritmalar Yardimi Ile Gezgin Satici Probleminin Çözümü Üzerine Bir Uygulama, Ç.Ü. Sosyal Bilimler Enstitüsü Dergisi, Cilt 19, Sayı 3, 2010, Sayfa 423-438
• Gerşil M., Alkaya A., Gezgin Satici Problemi Için Sezgisel Metotlarin Performans Analizi, XI. Üretim Araştırmaları Sempozyumu, 23-24 Haziran 2011
• Dikmen Ha., Dikmen Hü., Elbir A., Ekşi Z., Çelik F., Gezgin Satıcı Probleminin Karınca Kolonisi ve Genetik Algoritmalarla Eniyilemesi ve Karşılaştırılması, 18(1), 8-13, 2014
• Cevre U., Özkan B., Uğur A., Gezgin Satıcı Probleminin Genetik Algoritmalarla Eniyilemesi ve Etkileşimli Olarak İnternet Üzerinde Görselleştirilmesi, Ege Üniversitesi, Bilgisayar Mühendisliği Bölümü, İzmir
• Eberhart, R., & Kennedy, J. (1995, October). A new optimizer using particle swarm theory. In MHS'95. Proceedings of the sixth international symposium on micro machine and human science (pp. 39-43). Ieee.
• Kennedy J., Elbarth R. (August 2002), Particle swarm optimization, Purdue School of Engineereing and Technology
• Gencal, M. C. & Oral, M. (2022). Evrimsel algoritmalar için yeni bir meta-iyileştirici: bipolar eşleşme eğilimi . Pamukkale Üniversitesi Mühendislik Bilimleri Dergisi, 28 (2) , 313-323 . Retrieved from https://dergipark.org.tr/en/pub/pajes/issue/69632/1110433
• Onwubolu, G. C., Babu, B. V., & Clerc, M. (2004). Discrete particle swarm optimization, illustrated by the traveling salesman problem. New optimization techniques in engineering, 219-239.
• http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/ (erişim: 15.02.2023)
• https://www.yeniakit.com.tr/haber/turkiyenin-uzerinden-gecen-paralel-ve-meridyenler-hangileridir-1539841.html (erişim:15.08.2021)
• https://www.matematiklezzeti.com/post/meridyenler (erşim:15.08.2023)