PRÜFER-KARAGÜL ALGORİTMASI: GEZGİN SATICI PROBLEMİ İÇİN YENİ BİR YAKLAŞIM
Journal Title: Mehmet Akif Ersoy Üniversitesi İktisadi ve İdari Bilimler Fakültesi Dergisi - Year 2019, Vol 6, Issue 2
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. EXTENDED SUMMARY Research Problem In this study, a new constructive approach, named Prüfer-Karagül, has been proposed to obtain reasonable and effective solutions for the Travelling Salesman Problem (TSP). Literature Review In the literature, there are limited number of studies on the application of the Prüfer code on the TSP. HajiaghaeiKeshteli (2011) and Anbuudayasankar et al. (2014) used Prüfer coding for gene design and gene structure. He et al. (2015) solved the TSP with genetic algorithm based on Prüfer coding. Methodology In this study, it is aimed to solve TSP by using the Prüfer code structure with the nearest neighbors heuristics and 2-Opt approach. The details of the solution method and comparisons with the traditional methods are demonstrated on a small TSP given in Table 1 and Figure 1. The flowchart of the Prüfer-Karagül algorithm is given in Appendix 1. Table 1: Proposed Approach: Solving KTSP1 Problem with Prüfer-Karagül Algorithm Production No Prüfer Code Prüfer Tree Prüfer-Karagül TSP Cost Time (sec) 1 [1,5,5,5,8,4,8,5,1] [2,3,6,7,9,10,4,8,5,1] [4,2,3,10,1,5,7,6,9,8] 27,01 0,003024 2 [2,8,5,2,4,7,2,8,3] [1,6,9,5,10,4,7,2,8,3] [7,5,1,10,3,2,4,8,9,6] 27,01 0,00063 3 [10,3,8,2,3,1,6,7,6] [4,5,9,8,2,3,1,10,7,6] [4,2,3,10,1,5,7,6,9,8] 27,01 0,000933 4 [5,7,7,7,7,10,3,8,3] [1,2,4,5,6,7,9,10,8,3] [7,5,1,10,3,2,4,8,9,6] 27,01 0,000783 5 [2,7,5,5,7,8,4,7,5] [1,2,3,6,9,10,8,4,7,5] [7,5,1,10,3,2,4,8,9,6] 27,01 0,002679 6 [9,9,3,7,6,6,9,3,4] [1,2,5,8,7,10,6,9,3,4] [7,5,1,10,3,2,4,8,9,6] 27,01 0,000813 7 [2,10,7,5,7,6,7,6,8] [1,2,3,4,5,9,10,7,6,8] [7,5,1,10,3,2,4,8,9,6] 27,01 0,000665 8 [6,10,3,2,2,1,5,5,4] [7,6,8,3,9,2,1,10,5,4] [7,6,9,8,4,2,3,10,1,5] 27,01 0,00094 9 [8,7,8,10,10,2,2,7,1] [3,4,5,6,8,9,10,2,7,1] [7,6,9,8,4,2,3,10,1,5] 27,01 0,0007 10 [6,6,9,5,4,7,8,6,4] [1,2,3,9,5,10,7,8,6,4] [7,5,1,10,3,2,4,8,9,6] 27,01 0,000671 ( a ) Prüfer TSP solution ( b ) Prüfer-Karagül TSP solution ( c ) Random NNH+2-Opt solution Figure 1: Prüfer, Prüfer-Karagül and NNH+2-Opt solutions for KTSP1 problem Results and Conclusions In this study, the comparisons are conducted on larger test intances. The best solutions obtained for the TSP test instances showed 2% deviation from the optimal solution and 2.50% deviation from the average solution values. Consequently, the proposed method produces successful solutions in terms of solution performance and speed.
Authors and Affiliations
Kenan KARAGÜL
Keywords
Related Articles
- EP ID EP637915
- DOI 10.30798/makuiibf.508842
- Views 136
- Downloads 0
RASYONEL EKONOMİ VE DAVRANIŞ İKTİSADINDAN DEĞERLER İKTİSADINA
İnsanının rasyonelliği üzerine kurgulanan Neoklasik iktisat teorisi bugün dünyada hâkim iktisat politikalarına yön vermektedir. Söz konusu politikaların neticesinde oluşan hali hazırdaki gelir ve servet dağılımı ise kabu...
TEDARİKÇİLERİN ETKİNLİKLERİNİN İYİLEŞTİRİLMESİNE YÖNELİK ANALİTİK HİYERARŞİ SÜRECİ VE VERİ ZARFLAMA ANALİZİ YÖNTEMLERİNE DAYANAN MODEL ÖNERİSİ VE BİR VAKA ÇALIŞMASI
Daha hızlı veri iletişimine izin veren ve büyük veri üzerinde çalışmaya fırsat sağlayan bilgi sistemlerinin sürekli gelişimi ile birlikte, işletmelerin karar alma süreçlerinde analitik yaklaşımları uygulamaları daha mümk...
TÜRKİYE EKONOMİSİNDE DÖVİZ KURU KANALININ ETKİNLİĞİ: 2003-2016 DÖNEMİ İÇİN VAR ANALİZİ
Merkez bankaları tarafından alınan para politikası kararlarının toplam talebi ve fiyatları etkilemesi parasal aktarım mekanizması kanalları üzerinden gerçekleşmektedir. Bu nedenle, para politikalarının ekonomi üzerindeki...
TÜRKİYE’DE FAALİYET GÖSTEREN MEVDUAT BANKALARININ PERFORMANS ANALİZİ: BÜYÜKLÜK VE SAHİPLİK YAPISI AYRIMIYLA BİR KARŞILAŞTIRMA
EXTENDED SUMMARY Background Today, since the competition in every kind of market intensifies, business entities must measure and review their performance regularly to survive in highly competitive environment. As competi...
THE ANALYSIS OF DAHIYA DOCTRINE IN THE CONTEXT OF ISRAEL’S FURTHER SECURITY CLAIM
This study aims to understand, determine and explain the Dahiya Doctrine that was adopted during the Lebanon War (2006), and that was applied as a deterrence model. In this frame, it deals with Israel’s dissuasive expect...