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.
This study suggests a new solution algorithm that benefits from the relationship between traveler seller and assignment problems, a famous problem in the combinatory optimization field. The Hungarian algorithm provides an optimal solution to the assignment problems and has achieved initial solutions for the symmetrical traveler seller problem. The initial solutions obtained were solved using the closest neighbor and 2-Opt (NNH_2-Opt) intuitives. The proposed approach was often used with traveler seller test problems analyzed and compared with the results of some studies in the scientific summer. As a result, it has been shown that the recommended method is good in comparison with the methods both in terms of solution speed and solution quality. In particular, as the problem size grows, the solution time of compared methods extends, the recommended method can also provide quick solutions to large-scale problems.
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.
Alan : Mimarlık, Planlama ve Tasarım; Mühendislik
Dergi Türü : Uluslararası
Benzer Makaleler | Yazar | # |
---|
Makale | Yazar | # |
---|