Journals / Mühendislik Bilimleri ve Tasarım Dergisi / 2019 / Cilt: 7 - Sayı: 3
A NOVEL SOLUTION APPROACH FOR SOLVING TRAVELLING SALESMAN PROBLEM BASED ON HUNGARIAN ALGORITHM
- Pages
- 561–571
- DOI
- —
Abstract
In this study, a novel solution algorithm which takes advantage of the relationship between traveling salesman and assignment problems which are famous problems of combinatorial optimization area is proposed. By using the Hungarian Algorithm, which provides the optimal solution for the assignment problems, initial solutions were obtained for the symmetric traveling salesman problem. The obtained initial solutions were solved using the Nearest Neighbor and 2-Opt (NNH_2-Opt) heuristics. The proposed approach has been analyzed with the frequently used traveling salesman test problems and compared with the results of some studies in the scientific literature. As a result, it has been shown that the proposed method is superior to the other methods with regard to solution speed and quality. In particular, as the size of the problem increases, the solution times of the compared methods are getting longer, while the proposed method can also provide fast solutions for large-scale problems.
Özet
Bu çalışmada kombinatoryal optimizasyon alanının ünlü problemlerinden olan gezgin satıcı ve atama problemleri arasındaki ilişkiden faydalanan yeni bir çözüm algoritması önerilmektedir. Atama problemleri için optimal çözümü veren Macar Algoritması ile simetrik gezgin satıcı problemi için başlangıç çözümleri elde edilmiştir. Elde edilen başlangıç çözümleri En Yakın Komşu ve 2-Opt (NNH_2-Opt) sezgiselleri kullanılarak çözülmüştür. Önerilen yaklaşım sıklıkla kullanılan gezgin satıcı test problemleri ile analiz edilmiş ve bilimsel yazında yer alan bazı çalışmaların sonuçları ile kıyaslama yapılmıştır. Sonuç olarak, önerilen yöntemin hem çözüm hızı hem de çözüm kalitesi bakımından kıyaslanan yöntemlere göre iyi olduğu gösterilmiştir. Özellikle, problem boyutu büyüdükçe kıyaslanan yöntemlerin çözüm süresi uzarken, önerilen yöntem büyük boyutlu problemler için de hızlı çözümler sunabilmektedir.