SEZGİSEL VE METASEZGİSEL YÖNTEMLERİN GEZGİN SATICI PROBLEMİ ÇÖZÜM PERFORMANSLARININ KIYASLANMASI

COMPARING THE SOLUTION PERFORMANCES OF THE HEURISTIC AND METAHEURISTIC ALGORITHMS IN TRAVELLING SALESMAN PROBLEM

Özet

Bu çalışmanın amacı, sezgisel ve metasezgisel yöntemlerin Gezgin Satıcı Problemi çözüm performanslarının çözüm değeri ve süresi bakımından değerlendirilmesidir. Çalışma kapsamında, sezgisel yöntem olarak bütünleşik En Yakın Komşu (EYK) ve 2-Opt sezgiseli, metasezgisel yöntem olarak ise karınca kolonisi optimizasyon, tabu arama, benzetilmiş tavlama ve genetik algoritma yöntemleri kullanılmıştır. 16 adet veri seti ile yapılan deneyler, ortalama çözüm değerleri ve süreleri bakımından EYK+2-Opt bütünleşik yönteminin en iyi çözümleri sağladığını göstermiştir. Sonuç olarak, EYK+2-Opt yönteminin Gezgin Satıcı Probleminin çözümünde hızlı ve etkin çözümler üretebilen kullanışlı bir yöntem olduğu ortaya konmuştur.

Abstract

The Traveling Salesman Problem is the problem of identifying a route that will enable a salesman to visit all the cities only once in the list where the cities are located, to start and to return the city where he lives by traveling the shortest distance. In this study, the solution performances of a series of heuristic and metaheuristic methods in Travelling Salesman Problem is compared. Within the scope of the study, the nearest neighbor and 2-Opt methods were used as heuristic methods, and the Ant Colony Optimization, Tabu Search, Simulated Annealing and Genetic Algorithm methods were used as metaheuristic methods. As a result of the experiments conducted with 16 data sets, it was determined that the integrated method consisting of the Nearest Neighbor and 2-Opt heuristics provide the best solutions in terms of average solution values and times.