Perbandingan Algoritma Branch and Bound dan Simulated Annealing pada Travelling Salesman Problem

Abstract

This study aims to explain and solve the problem of determining the route that has the minimum distance or cost in the Traveling Salesman Problem (TSP). To overcome this, an approach using the Branch and Bound Algorithm and Simulated Annealing is carried out. Furthermore, it will be explained about the Traveling Salesman Problem using the Branch and Bound Algorithm and Simulated Annealing. The results will be compared to find out which approach is better to use. Based on this research , the results obtained are 16 nodes on the branch and bound method and 46 iterations on the Simulated Annealing algorithm . The shortest distance using the branch and bound method is 668 with routes 1 – 5 − 2 - 4 – 3 – 1 and using Simulated Annealing is 668 with routes 3 – 4 – 2 – 5 – 1 – 3. From the results obtained, it can be seen that distance using the Simulated Annealing algorithm is the same as using the branch and bound algorithm. So it can be concluded that in the case of the traveling salesman problem, the minimum distance generated by the Simulated Annealing algorithm is the same as the branch and bound algorithm. However, in the branch and bound processing process, the process is shorter than the simulated annealing algorithm. This can be seen from the execution time for the branch and bound method of 0.001 seconds while the simulated annealing algorithm is 0.258376 seconds. This shows that the branch and bound method is better in terms of time efficiency compared to the simulated annealing method.