Combinatorial Optimization: Solution Methods of Traveling Salesman Problem

Abstract

ABSTRACT: Traveling Salesman Problem has been one of the most interesting and challenging problem in the literature. It is include a large area in combinatorial optimization problem. A variety of Exact and Heuristic Algorithms are usable algorithms for solving TSP. Branch and Bound Algorithm is an exact algorithm that is developed for solving TSP type problems. Furthermore, Genetic Algorithm is one of the extensively algorithm within the Heuristic Algorithm. In this work, we looked into symmetric and asymmetric matrices to solve TSP. We used Genetic and Branch-and-Bound Algorithms as the solution methods to get the shortest path. Keywords: Traveling Salesman Problem, Heuristic Algorithm, Exact Algorithm, Branch and Bound Algorithm, Genetic Algorithm.

……………………………………………………………………………………………………………………………………………………………………………………………………………………

ÖZ: Gezgin Satıcı Problemi, literatürdeki en ilginç ve en iddealı problem olarak çalışılan, kombinasyonel eniyileme problemlerinin başında gelmektedir. Çözümü için birçok Sezgisel ve Kesin Çözüm Yöntemleri geliştirilmektedir. Dal ve Sınır Algoritmaları, gezgin satıcı ve benzer yapıdaki problemlerin çözümü için geliştirilen Kesin Çözüm Yöntemi olmakla birlikte, Genetik Algoritmalar da Sezgisel Yöntemlerin başında gelmektedir. Bu çalışmada Gezgin Satıcı Problemlerinin çözümü için simetrik ve asimetrik matrisler ele alınmıştır. En kısa turları elde etmek için de Dal ve Sınır ve Genetik Algoritmaları kullanılmaktadır.

Anahtar Kelimeler: Gezgin Satıcı Problemi, Sezgisel Yöntem, Kesin Çözüm Yöntemi, Dal ve Sınır Algoritması, Genetik Algoritma.