Journals / Mehmet Akif Ersoy Üniversitesi İktisadi ve İdari Bilimler Fakültesi Dergisi / 2019 / Cilt: 6 - Sayı: 2
PRÜFER-KARAGÜL ALGORITHM: A NOVEL APPROACH FOR TRAVELLING SALESMAN PROBLEM
- Pages
- 452–470
- DOI
- —
Abstract
As it is a fundamental model in the field of combinatorial optimization, new heuristic methods are developed for effective and rapid solution of the travelling salesman problem, which is widely used in the literature. In this study, a new constructive approach called Prüfer-Karagül has been proposed for the traveling salesman problem. In order to evaluate the performance of the proposed method, analysis was made with travelling salesman problem test instances which are commonly used in the literature. The best solutions obtained as a result of the tests showed 2% deviation from the optimal solution and 2.50% deviation from the average solution values. As a result, the proposed method produces successful solutions in terms of solution performance and speed.
Özet
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.