Penyelesaian Traveling Salesman Problem Menggunakan Algoritme Simulated Annealing

Abstract

Traveling Salesman Problem (TSP) sering kali dimanfaatkan untuk menyelesaikan berbagai permasalahan dalam kehidupan sehari-hari, salah satunya adalah kegiatan distribusi. TSP dapat diselesaikan dengan metode eksak maupun melalui metode pendekatan. Namun penyelesaian TSP berukuran besar dengan metode eksak cenderung memakan waktu yang sangat lama. Maka dari itu terdapat beberapa metode yang dikembangkan untuk permasalahan TSP ini. Pada karya ilmiah ini, akan dilakukan penyelesaian terhadap permasalahan TSP menggunakan metode pendekatan Simulated Annealing (SA) dan metode eksak Branch and Bound. Terdapat tiga permasalahan TSP yang akan diselesaikan. Permasalahan pertama terdiri dari 25 node, permasalahan kedua terdiri dari 40 node, dan permasalahan ketiga terdiri dari 68 node. Hasil yang diperoleh menunjukkan bahwa iterasi dan waktu eksekusi yang dibutuhkan metode SA jauh lebih sedikit dibandingkan dengan metode eksak. Namun selisih jarak yang dihasilkan metode SA dengan metode eksak masih relatif besar pada kasus II dan III yaitu 5,5% dan 7,6%.

Traveling Salesman Problem (TSP) is often used to solve various problems in daily life, one of which is distribution activities. TSP can be solved by an exact method or an approach method. However, the large cases tends to take a very long time to solve using the exact method. Therefore, there are several methods developed for this problem. In this manuscript, the exact method used to solve TSP is Branch and Bound and for the approach method using the metaheuristic Simulated Annealing (SA) method. There are three cases that will be resolved. The first case consists of 25 nodes, the second case consists of 40 nodes, and the third case consists of 68 nodes. The results obtained show that the iteration and the execution time required by the SA method is much less than the exact method. However, the difference between the distance produced by the SA method and the exact method was still relatively large in the second case and the third case, that is 5,5% and 7,6%.