Penerapan algoritma simulated annealing untuk menyelesaikan Asymmetric Travelling Salesman Problem

Abstract

Travelling Salesman Problem (TSP) merupakan suatu permasalahan pencarian jarak terpendek ketika seorang salesman mengunjungi sejumlah n kota, dengan syarat setiap kota dikunjungi tepat satu kali dan kemudian 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 terinspirasi dari 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 diperoleh hasil bahwa parameter T (parameter kontrol) dan parameter r (faktor pengendali parameter kontrol) memiliki pengaruh pada solusi yang dihasilkan.