Concentric Tabu Search Algorithm for Solving Traveling Salesman Problem

Abstract

In this research one of the local search algorithms called the Concentric tabu search (CTS) is used to solve the traveling salesman problem (TSP). One of the well known NP-hard problems in combinatorial optimization is the TSP Problem and it is one of the most competently studied problems in the area of combinatorial optimization. Two different implementations of the Concentric tabu search (CTS): ring moves (RM) and all moves (AM) are used and compared with the traditional tabu search. For searching global optimal solutions for given TSP problems, Concentric tabu search was hybridized with Genetic Algorithm. Computational experiments showed that Concentric tabu search gives better performance than the traditional tabu search and also improves the execution of the Genetic Algorithm (GA) for the solutions of TSP problems. Keywords: Concentric Tabu Search, Tabu Search, Genetic Algorithm, Traveling Salesman Problem.

ÖZ: Bu araştırmada yerel arama algoritmalarından biri olan Ortak Merkezli tabu arama (OMTA) yöntemi seyyar satıcı problemini (TSP) çözmek için kullanılmıştır. NP-Zor problemlerinden biri olan TSP için en iyi çözümlerin bulunması ile ilgili literatürde pekçok çalışmalar bulunmaktadır. Ortak Merkezli tabu algoritması için iki farklı yöntem bulunmaktadır : Halka Hamle (HH) ve Tüm Hamle (TH), bu çalışmada bu iki yöntem geleneksel tabu arama ile TSP çözümleri üzerinden karşılaştırılmıştır. Ayrıca OMTA Genetik Algoritma ile birleştirilerek TSP problemlerine en iyi çözümler bulunmaya çalışılmıştır. Yapılan deneyler ile OMTA geleneksel TS yönteminden daha iyi sonuçlar verdiği gösterilmiştir. Ayrıca Genetik Algoritma ile kullanıldığında TSP problemlerinin çözümünde Genetik Algoritma sonuçlarını iyleştirdiği gözlemlenmiştir. Anahtar Kelimeler: Ortak Merkezli Tabu Arama, Tabu Arama, Genetik Algoritma, Seyyar Satıcı Problemini.