Ulaştırma ve Lojistik Kongreleri

Gezgin Satıcı Probleminin Genetik Algoritma İle Çözümü

Oğuzhan Gökbayrak
Süleyman Demirel Üniversitesi, Isparta, Türkiye

Hakan Altunay
Dr. Öğr. Üyesi, Süleyman Demirel Üniversitesi, Isparta, Türkiye

Gezgin satıcı problemi, herhangi bir başlangıç noktasından başlanarak, aralarındaki mesafeleri bilinen şehirlerin her birisinden yalnızca bir kez geçilen ve başlangıç noktasına geri dönülen en kısa yolun bulunmasını amaçlamaktadır. Yıllardır araştırmacıların üzerinde çalıştığı gezgin satıcı problemi, NP-Hard problemler sınıfında değerlendirilmektedir. Dağıtım, planlama ve lojistik gibi birçok alanda örnekleri bulunan gezgin satıcı probleminin en iyi çözümünü belirlemek için çok sayıda matematiksel model geliştirilmiştir. Ancak geliştirilen bu modeller şehir sayısı arttıkça problemin çözümünde yetersiz kalmaktadır. Tüm bu sebepler araştırmacıları, problemin çözümünde kesin çözüm algoritmalarını kullanmak yerine; en iyi çözümü garanti etmeyen bazı metasezgisel algoritmalara yöneltmiştir. 1975 yılında John H. Holland tarafından geliştirilen Genetik Algoritma da gezgin satıcı probleminin çözümünde kullanılan en yaygın metasezgisel algoritmalardan birisidir. Bu çalışmada da gezgin satıcı probleminin çözümü için Genetik Algoritma yönteminden yararlanılmıştır. Çalışmanın ilk aşamasında seyahat noktalarının belirlenmesi sağlanarak problemin tanımı yapılmıştır. Ardından noktalar arasındaki mesafeler uzaklık matrisi şeklinde ifade edilmiştir. İlk olarak ele alınan örnek uygulamanın matematiksel model ile çözümlenmesi amaçlanmıştır. Sonraki aşamada ise Genetik Algoritma yöntemi kullanılarak elde edilen yeni rotalar analiz edilmiştir. Genetik algoritma çözümü ile ulaşılan rotalar, problemin çözümüne yönelik olarak geliştirilen modelin, kabul edilebilir süreler içerisinde başarılı sonuçlar ürettiğini göstermektedir.

Anahtar Kelimeler: Matematiksel Programlama, Genetik Algoritma, Gezgin Satıcı Problemi, Lojistik Yönetimi, Yöneylem Araştırması

Solving the Traveling Salesman Problem with Genetic Algorithm

The traveling salesman problem aims to find the shortest route starting from any initial node, visiting only once through each of the cities whose distances are known between them and returning to the initial node. The traveling salesman problem that has been studied by researchers for decades is one of the NP-Hard problems. Several mathematical models have been developed to determine the optimal solution to the problem used in many fields such as distribution, planning and logistics. However, these mathematical models fail to satisfy as the number of cities increases. Therefore, instead of using exact solution algorithms to solve the problem; some metaheuristic algorithms that do not guarantee the optimal solution are preferred. Genetic Algorithm developed by John H. Holland in 1975 is also one of the most common metaheuristic algorithms used to solve the traveling salesman problem. In this study, genetic algorithm method is used to solve the traveling salesman problem. Firstly, travel destinations are determined and the problem is identified. In the next stage, the distances between the nodes are expressed as distance matrix. Initially, the proposed mathematical model is used to solve the problem. Then, new routes obtained using the Genetic Algorithm method are analyzed. The routes obtained with the genetic algorithm show that the model developed for the problem generates remarkable results within acceptable time.

Keywords: Traveling Salesman Problem, Genetic Algorithm, Mathematical Programming, Logistics Management, Operations Research