EVALUASI KINERJA METODE-METODE HEURISTIK UNTUK PENYELESAIAN TRAVELLING SALESMAN PROBLEM

Abstract

Traveling Salesman Problem (TSP) is known as one of optimization problems that has taken great attention of researchers in this last two decades. Since TSP is included as an NP-Complete problems, most researchers researched on the development of heuristic method to get optimal/near optimal solutions of the problem. In this research, we developed and compared the effectiveness and the efficiency of several heuristic methods given in the literature. We tested those heuristics methods by using Benchmark test problems. It is shown that heuristic methods can give the optimal/near optimal solution of the problem within reasonable time. It is also shown, for relatively large size problems, that Lin-Kernighan is the most effective algorithm followed by Hybrid Genetic Algorithm (HGA)

Keywords: Traveling Salesman Problem, Heuristic Method, combinatorial optimization