Abstract:
Travelling Salesman Problem (TSP) merupakan suatu permasalahan mencari jarak terpendek
ketika seorang salesman mengunjungi sejumlah n kota, dengan syarat salesman tersebut harus
mengunjungi seluruh kota tepat satu kali dan harus kembali ke kota awal. Secara umum, TSP
dibagi menjadi dua jenis yaitu TSP simetris dan TSP asimetris. Pada TSP simetris jarak
antara kota i ke kota j sama dengan jarak kota j ke kota i. Sedangkan pada TSP asimetris
jarak antara kota i ke kota j belum tentu sama dengan jarak antara kota j ke kota i. Untuk
menyelesaikan dan menemukan solusi dari permasalahan tersebut digunakan suatu metode
yaitu metode Metaheuristik. Salah satu metode Metaheuristik yang dapat digunakan adalah
Algoritma Simulated Annealing. Metode ini merupakan metode yang terinspirasi dari proses
fisika yaitu tentang proses pendinginan cairan logam yang berubah menjadi padat. Prinsip
kerjanya yaitu pada saat temperatur tinggi partikel cairan logam mempunyai tingkat energi
yang tinggi sehingga relatif mudah bergerak terhadap partikel lainnya. Kemudian pada saat
temperatur diturunkan partikel tersebut secara perlahan mengatur dirinya untuk membentuk
sebuah konfigurasi sehingga diperoleh suatu keadaan stabil dengan tingkat energi minimum.
Energi yang minimum ini merupakan jarak terpendek apabila dikaitkan dalam permasalahan
TSP. Berdasarkan percobaan yang telah dilakukan menggunakan Algoritma Simulated Annealing
pada permasalahan TSP asimetris didapatkan hasil analisis sensitivitas, bahwa parameter T
(parameter kontrol) dan parameter r (faktor pengendali parameter kontrol) memiliki pengaruh
pada solusi yang dihasilkan.
