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

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 algorithm
• traveling salesman problem
• nearest neighbor heuristic
• 2-opt algorithm
• prüfer code
• prüfer-karagül algoritması
• gezgin satıcı problemi
• en yakın komşu sezgiseli
• 2-opt algoritması
• prüfer kod