PRÜFER-KARAGÜL ALGORİTMASI: GEZGİN SATICI PROBLEMİ İÇİN YENİ BİR YAKLAŞIM

Authors : Kenan KARAGÜL

Pages : 452-470

Doi:10.30798/makuiibf.508842

View : 15 | Download : 16

Publication Date : 2019-08-29

Article Type : Research Paper

Abstract :Kombinatoryal optimizasyon alanında temel bir model olduğu için literatürde oldukça yaygın çalışılan gezgin satıcı probleminin etkin ve hızlı çözümü için yeni sezgisel yöntemler geliştirilmesine devam edilmektedir. Bu çalışmada, gezgin satıcı problemi için Prüfer-Karagül adı verilen yeni bir yapısal çözüm yaklaşımı önerilmiştir. Önerilen yöntemin performansını değerlendirmek için literatürde yaygın olarak kullanılan gezgin satıcı test problemleri ile analizler yapılmıştır. Yapılan testler sonucunda elde edilen en iyi çözümler optimal çözümden %2, ortalama çözüm değerleri ise %2,50 sapma göstermiştir. Sonuç olarak, önerilen yöntem çözüm performansı ve hızı açısından başarılı çözümler üretmektedir.
Keywords : Prüfer Karagül Algoritması, Gezgin Satıcı Problemi, En Yakın Komşu Sezgiseli, 2 Opt Algoritması, Prüfer Kod