Year 2019, Volume 6 , Issue 2, Pages 452 - 470 2019-08-29

PRÜFER-KARAGÜL ALGORITHM: A NOVEL APPROACH FOR TRAVELLING SALESMAN PROBLEM
PRÜFER-KARAGÜL ALGORİTMASI: GEZGİN SATICI PROBLEMİ İÇİN YENİ BİR YAKLAŞIM

Kenan Karagül [1]


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.
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.



  • 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.
Primary Language tr
Subjects Social
Journal Section Research Articles
Authors

Orcid: 0000-0001-5397-4464
Author: Kenan Karagül (Primary Author)
Institution: PAMUKKALE ÜNİVERSİTESİ
Country: Turkey


Dates

Publication Date : August 29, 2019

APA Karagül, K . (2019). PRÜFER-KARAGÜL ALGORİTMASI: GEZGİN SATICI PROBLEMİ İÇİN YENİ BİR YAKLAŞIM. Mehmet Akif Ersoy Üniversitesi İktisadi ve İdari Bilimler Fakültesi Dergisi , 6 (2) , 452-470 . DOI: 10.30798/makuiibf.508842