Gezgin Satıcı Probleminin Çözümü için Guguk Kuşu Arama Algoritma Tabanlı Yeni Bir Hibrit Metasezgisel Yöntem

Abstract

Bu tez çalışmasında, Gezgin Satıcı Problemi (GSP) çözümü için hibrit bir metasezgisel yöntem önerilmiştir. GSP, n tane şehrin bulunduğu ve bu şehirlerin birbirleri arasındaki uzaklıkların belli olduğu, her bir şehrin bir sefer ziyaret edildiği bir problemdir. Problemde en kısa turun bulunarak başlangıç şehrine dönülmesi hedeflenir. Şehir sayısının artması ile problemin optimum çözümü kabul edilebilir sürelerde bulunamamaktadır. Metasezgisel yöntemler, GSP'de kabul edilebilir iyi sonuçlar elde edilebilmesine olanak sağlamaktadır. Önerilen yöntem, 3-Opt yöntemi ve umut vadeden sonuçlar vererek çeşitli çalışmalarla başarısını kanıtlamış Guguk Kuşu Arama algoritmasının birleştirilmesi ile geliştirilmiş hibrit bir yöntemdir. Önerilen yöntemin performansı, GSP için sıkça kullanılan TSPLIB kütüphanesindeki 41 farklı test problemi ile ölçülmüş ve sonuçları literatürdeki son yıllarda geliştirilmiş yöntemler ile kıyaslanmıştır. Önerilen yöntem, 150 şehirden daha küçük boyutlu problemlerin tümünde optimum sonucu bulmuştur. Buna ek olarak, problem boyutu arttıkça diğer yöntemlere kıyasla, elde edilen sonuçların optimuma daha fazla yaklaştığı görülmüştür. Literatürde yer alan çalışmalar ile aynı problem kullanılarak karşılaştırıldığında benzer veya daha üstün sonuçlar elde edilmiştir.

In this thesis, a hybrid metaheuristic method is proposed to solve the Traveling Salesman Problem (TSP). TSP is a problem in which there are n cities and the distances between these cities are known, and each city is visited once. In the problem, it is aimed to find the shortest tour by returning to the starting city. With the increase in the number of cities, the optimum solution to the problem cannot be found in an acceptable time. Metaheuristic methods allow obtaining acceptable good results in TSP. The proposed method is a hybrid method developed by combining the 3-Opt method and the Cuckoo Search algorithm, which has proven its success in various studies with promising results. The performance of the proposed method was measured with 41 different test problems in the TSPLIB library, which is frequently used for TSP, and the results were compared with the methods developed in the literature in recent years. The proposed method found the optimum result for all problems with a size smaller than 150 cities. In addition, as the problem size increases, it has been observed that the obtained results get closer to the optimum compared to other methods. When compared with the studies in the literature using the same problem, similar or superior results are obtained.