Travelling Salesman Problem (TSP) adalah suatu permasalahan klasik mengenai pencarian
rute yang optimal untuk sejumlah n kota, dengan aturan bahwa setiap kota harus dikunjungi
tepat satu kali kecuali kota awal. Optimalisasi yang dimaksud disini yaitu dilihat dari sisi
jarak.
Banyak alternatif-alternatif rute yang mungkin yaitu berjumlah permutatif terhadap N
diperoleh dari persamaan (N-1)!/2. Misalnya jumlah kota yang akan didatangi sejumlah 15
kota (N=15) maka akan didapatkan rute alternatif sekitar 653.837.184.000 rute. Untuk N=70
maka rute alternatif yang akan diseleksi sekitar 8.556*1097 rute. Hal ini berarti bahwa untuk
N besar, ukuran masalah juga membesar secara supereksponensial.
Banyak metode heuristik yang dapat digunakan untuk menyelesaikan permasalahan TSP,
salah satunya yaitu Ant Colony System (ACS). ACS merupakan bagian dari Ant Colony
Optimization, yaitu algoritma yang terinspirasi dari tingkah laku semut di dunia nyata pada
saat proses pencarian makan.
Dalam proses perhitungannya, ACS terdiri dari tiga fase utama yaitu fase inisialisai,
pembentukkan tur, dan fase update global. Pada saat proses pemilihan ruas yang dilaluinya
semut sangat dipengaruhi oleh intensitas pheromone dan juga oleh jarak antar ruas. Dimana
pheromone tersebut digunakan sebagai alat komunikasi secara tidak langsung. Semakin
tinggi intensitas pheromone pada ruas tersebut maka semakin besar probabilitas ruas tersebut
untuk dilewati atau dipilih.
Karena metode ACS merupakan metode heuristik, maka tidak ada jaminan bahwa solusi yang
dihasilkan benar-benar optimal. Namun metode ini banyak dipilih karena waktu dan biaya
yang relatif lebih rendah dibandingkan dengan metode yang bukan heuristik.
Untuk hasil dari penyelesaian dengan menggunakan metode Ant Colony System juga akan
dibandingkan dengan hasil dari metode-metode yaitu Simulated Annealing, Teori Nearest
Neighbour by 2-Opt dan Teori Interaksi Gani.
ant colony, ACS, TSP