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

Year 2019, Volume: 6 Issue: 2, 452 - 470, 29.08.2019

Kenan Karagül

https://doi.org/10.30798/makuiibf.508842

Cited By: 3

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

PRÜFER-KARAGÜL ALGORITHM: A NOVEL APPROACH FOR TRAVELLING SALESMAN PROBLEM

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.

Keywords

Prüfer-Karagül Algorithm, Traveling Salesman Problem, Nearest Neighbor Heuristic, 2-Opt Algorithm, Prüfer Code

References

• ANBUUDAYASANKAR, S. P., GANESH, K., MOHAPATRA, S. (2014), Models for Practical Routing Problems in Logistics: Design and Practices. Springer International Publishing. 43-68.
• DEO, N., MICIKEVICIUS, P. (t.y.), Prüfer-Like Codes for Labeled Trees, 16 Aralık 2018 tarihinde, https://pdfs.semanticscholar.org/52be/20fcdc9ed956fc686c4492f59ea51ca537a7.pdf adresinden alındı.
• DORIGO, M., GAMBARDELLA, L. M. (1997), Ant Colony System: A Cooperative Learning Approach to the Travelling Salesman Problem. IEEE Transactions on Evolutionary Computation, 1 (1), 53-66.
• ERDEM, Y , KESKİNTÜRK, T . (2011), Kanguru Algoritmasi ve Gezgin Satici Problemine Uygulanması. İstanbul Ticaret Üniversitesi Fen Bilimleri Dergisi, 10 (19). Retrieved from http://dergipark.gov.tr/ticaretfbd/issue/21359/229115
• GENDREAU, M., LAPORTE, G., SEMET, F. (1998), A Tabu Search Heuristic for the Undirected Selective Travelling Salesman Problem. European Journal of Operational Research, 106 (2-3), 539-545.
• HAJIAGHAEI-KESHTELI, M. (2011). The Allocation of Customers to Potential Distribution Centers in Supply Chain Networks: GA and AIA Approaches. Applied Soft Computing, 11, 2069-2078.
• HE, R., MA, C., ZHANG, W., XIAO, Q. (2015). Optimisation Algorithm for Logistics Distribution Route Based on Prufer Codes. Int. J. Wireless and Mobile Computing. 9 (2), 205–210.
• KARAGÜL, K., Guguk Kuşu Algoritması: Bir Plastik Atık Toplama Uygulaması. 15th International Symposium on Econometrics, Operations Research and Statistic, Isparta, Turkey, 15, 775-784, 2014.
• KARAGUL, K., AYDEMİR, E., TOKAT, S. (2016). Using 2- Opt Based Evolution Strategy for Travelling Salesman Problem. An International Journal of Optimization and Control: Theories & Applications (IJOCTA), 6, 103–113.
• MAVROVOUNIOTIS, M., YANG, S. (2013), Ant Colony Optimization with Immigrants Schemes for the Dynamic Travelling Salesman Problem with Traffic Factors. Applied Soft Computing, 13(10), 4023-4037, 2013.
• NURİYEVA, F., KIZILATEŞ, G. (2016), Gezgin Satıcı Problemi İçin Merkezden Kenarlara Hipersezgisel Yöntem. Süleyman Demirel Üniversitesi Fen Bilimleri Enstitüsü Dergisi, 20 (2),319-323.
• ODILI, J. (2018), The Dawn Of Metaheuristic Algorithms. International Journal of Software Engineering and Computer Systems, 4(2), 49-61. Retrieved from http://journal.ump.edu.my/ijsecs/article/view/703.
• ODILI, J. B., KAHAR, M. N., NORAZIAH, A., ZARINA, M., UL HAQ, R. (2017), Performance Analyses of Nature-Inspired Algorithms on the Traveling Salesman’s Problems for Strategic Management. https://doi.org/10.1080/10798587.2017.1334370.
• PALA, O , AKSARAYLI, M . (2018), Asimetrik Gezgin Satıcı Problemine Bulanık Karınca Kolonisi Optimizasyon Algoritmasi ile Çözüm Yaklaşımı. Journal of Transportation and Logistics, 3 (1), 25-34. Retrieved from http://dergipark.gov.tr/jtl/issue/37196/366856.
• PAULDEN, T., SMITH, D. K. (2007). Developing New Locality Results for the Prüfer Code Using a Remarkable Linear-Time Decoding Algorithm. The Electronic Journal of Combinatorics, 14.
• SÜRAL, H. (2003), Gezgin Satıcı Problemi. Matematik Dünyası, 10 Aralık 2018 tarihinde http://www.matematikdunyasi.org/arsiv/PDF/03_3_37_40_GEZGIN.pdf adresinden alınmıştır.
• ŞAHİN, Y., KARAGÜL, K. (2019). Gezgin Satıcı Probleminin Melez Akışkan Genetik Algoritma (MAGA) Kullanarak Çözümü. doi: 10.5505/pajes.2018.81084, Retrieved https://www.journalagent.com/pajes/pdfs/PAJES-81084-RESEARCH_ARTICLE-SAHIN.pdf.
• WANG, X., WANG, L., WU, Y. (2009). An Optimal Algorithm for Prufer Codes. J. Software Engineering & Applications. 2: 111-115. doi:10.4236/jsea.2009.22016.
• THOMPSON, E., PAULDEN, T., SMITH, D. K. (2007), The Dandelion Code: A New Coding of Spanning Trees for Genetic Algorithms. IEEE Transactions On Evolutionary Computation, 11 (1). 91-100.
• KOUNALAKIS, E., KAPELONIS, K. (2002), Chapter 10: Travelling Salesman Problem, In HY-583 Chart Algorithms Student Notes: Autumn 2002, (eds. Ioannis Tollis).
• ZHAO, F, LI, S., SUN J, MEI, D. (2009), Genetic Algorithm for the One-Commodity Pickup-and-Delivery Traveling Salesman Problem. Computers & Industrial Engineering, 56(4), 1642-1648.
• Web-1: Wikipedia (t.y), Prüfer Sequence, 15 Aralık 2018 tarihinde, http://www.wikizeroo.net/index.php?q=aHR0cHM6Ly9lbi53aWtpcGVkaWEub3JnL3dpa2kvUHLDvGZlcl9zZXF1ZW5jZQ adresinden alındı.
• Web-2: CP-Algorithms (t.y.), Prüfer Code, 15 Aralık 2018 tarihinde, https://cp-algorithms.com/graph/pruefer_code.html adresinden alınmıştır.
• Web-3: Prüfer Codes (t.y.), 15 Aralık 2018 tarihinde, https://ptwiddle.github.io/Graph-Theory-Notes/s_graphalgorithms_prufer.html adresinden alınmıştır.
• Web-4: Heuristic Method for the Travelling Salesman Problem (TSP) in Matlab (t.y.), 1 Ağustos 2018 tarihinde, http://freesourcecode.net/matlabprojects/65173/heuristic-method-for-the-traveling-salesman-problem-%28tsp%29--in-matlab adresinden alınmıştır.
• Web-5: TSPLIB - IWR, Heidelberg - Universität Heidelberg, 1 Ağustos 2018 tarihinde, https://www.iwr.uni-heidelberg.de/groups/comopt/software/TSPLIB95/ adresinden alınmıştır.