Gezgin satıcı problemlerinin çözümü için karınca kolonisi optimizasyonu tabanlı hibrit bir algoritma geliştirilmesi

Optimization is used to achieve the best result in scientific or industrial studies. By minimizing or maximizing the result output, the best result of optimization is achieved. Optimization problems are classified as discrete or continuous optimization problems according to the parameters. The traveling salesman problem is a discrete optimization problem that involves the seller who starts from a specific point, visits to the desired destination only once and returns to the starting point using the shortest route. There are many methods to solve travelling salesman problem. In these solutions, metaheuristic methods are more advantageous than the other methods in terms of solution time and achieving successful results. Ant colony optimization is a metaheuristic solution and often used to solve the travelling salesman problem. In this thesis study, the pheromone that used in ant colony optimization is modified as footprint and hybridized with neighborhood operators. Random insertion, random insertion of subsequences and reverse random insertion of subsequences operators as neighborhood operators are used to improve solutions. With these changes, it is aimed to get a new and more effective solution. In this study, the proposed hybrid approach applied to best-known travelling salesman problems, provinces of Turkey and districts of Konya. The results are compared with standard ant colony optimization. When the duration and lap length were evaulated, proposed hybrid approach acquires best results than ant colony optimization.

Optimizasyon, bilimsel veya endüstriyel çalışmalarda elde edilecek çıktıyı en iyi sonuca ulaştırmak için kullanılır. Sonuç çıktısının minimize veya maksimize edilmesiyle optimizasyonun hedeflediği en iyi sonuca ulaşılır. Optimizasyon problemleri, aldığı parametrelere göre ayrık ve sürekli olarak sınıflandırılmaktadır. Gezgin satıcı problemi, satıcının belirli bir noktadan başlayıp uğranması istenen hedeflere sadece tek sefer uğrayarak en kısa yolu kullanıp başladığı noktaya geri dönüşünü içeren ayrık bir optimizasyon problemidir. Gezgin satıcı problemi çözümünde kullanılan birçok çözüm metodu vardır. Bu çözümlerden metasezgisel çözümler, problemin çözüm süresi bakımından diğer metotlara göre daha avantajlıdır ve başarılı sonuçlar elde ederler. Karınca kolonisi optimizasyonu metasezgisel bir çözüm yöntemidir ve gezgin satıcı problemi çözümünde sıkça kullanılır. Bu tez çalışmasında, karınca kolonisi optimizasyonunda kullanılan feromon, ayak izi olarak değiştirilmiş ve algoritma, komşuluk operatörleri ile hibritlenmiştir. Komşuluk operatörleri olarak rastgele yerleştirme, altdizileri rastgele yerleştirme, altdizilerin rastgele yerleştirilmesini terse çevirme yöntemleri daha iyi sonuçların elde edilmesi amacıyla kullanılmıştır. Yapılan bu değişiklikler ile yeni ve daha etkili bir çözüm türü elde edilmesi amaçlanmıştır. Bu çalışmada önerilen hibrit yaklaşım çok bilinen gezgin satıcı problemlerine, Türkiye'nin illerine ve Konya'nın ilçelerine uygulanmıştır. Sonuçlar standart karınca kolonisi optimizasyonu ile kıyaslanmıştır. Süre ve tur uzunluğu göz önünde bulundurulduğunda, oluşturan bu hibrit yaklaşımla, karınca kolonisi algoritmasına göre daha iyi sonuçlar elde edilmiştir.