PERBANDINGAN ALGORITMA GREEDY , ALGORITMA CHEAPEST INSERTION HEURISTICS DAN DYNAMIC PROGRAMMING DALAM PENYELESAIAN TRAVELLING SALESMAN PROBLEM

Abstract

Travelling Salesman Problem is one of problems to find shortest route from travelling a salesman from first city and then to destination cities and finally back to first city, but one city just only once visited. There are some algorithms to solving travelling salesman problem,such as Greedy Algorithm, Artificial Bee Colony Algorithm, Cheapest Insertion Heuristics Algorithm, Genetic Algorithm and many more. In this paper, only greedy algorithm, cheapest insertion heuristics algorithm and dynamic programming are discussed. After compared using an example case with 5 cities and solved by third of algorithm, shortest route is same but the way to solving is different. They have advantages and disadvantages of each, and has the characteristics of each. Greedy algorithm is more suitable when used for a number of cities that are not too much because  the process is more simple, but cheapest insertion heuristics algorithm is more suitable to case with more city throught the process more complicated than greedy algorithm. Counting in Dynamic programming must be right because it will be influence for the next counting result.