Simulated Annealing Algorithm for Determining Travelling Salesman Problem Solution and Its Comparison with Branch and Bound Method

Abstract

Travelling Salesman Problem (TSP) is a problem where a person must visit some places, starting from one city and then moving on to the next city with the conditions that the places visited can only be passed precisely once and then back to the starting city. TSP is an NP-hard, an important problem in operations research. TSP problems can be solved by an exact method or an approximation method, namely the metaheuristic method. This research aims to solve the TSP problem with an approximation method called the Simulated Annealing (SA), and then compare the results of this approximation method with the exact Branch and Bound method. The results indicated that the SA method could accomplish TSP problems. However, like other metaheuristic methods, SA only accomplishes it using an approach to get good results. Still, it cannot be determined that SA has the most optimal results, but the time needed by the SA method is faster than the Branch and Bound method. In case I, the percentage difference between the distance generated using the SA method with the B-and-B method is 0%, in case II it is 7% and in case III it is 8%.

Keywords

• branch and bound
• integer linear programming
• simulated annealing
• travelling salesman problem