Penerapan algoritma Simulated Annealing untuk menyelesaikan Travelling Salesman Problem

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.