ANALISIS ALGORITMA ANT SYSTEM (AS) PADA KASUS TRAVELLING SALESMAN PROBLEM (TSP)

Abstract

Traveling Salesman Problem (TSP) merupakan permasalahan optimasi yang mencari rute terpendek  dengan ruang pencarian yang besar. Ukuran ruang pencarian yang besar menjadi permasalahan dalam menentukan rute terpendek sehingga diperlukan metode Heuristik yang mampu menyelesaikan permasalahan TSP. Algoritma Ant System (AS) merupakan salah satu metode Heuristik yang terinspirasi terhadap makhluk hidup yaitu semut  yang dapat mencari rute terpendek dalam mencari makanan.  Sehingga pada penelitian ini mengaplikasikan algoritma AS untuk menyelesaikan permasalahan TSP. Langkah pertama adalah menginisialisasi parameter yang digunakan. Pada pengujian parameter didapat parameter yang memiliki kinerja yang baik dalam menghasilkan rute terpendek yaitu α=1, β=2,5 dan ρ=0,9. Langkah selanjutnya menentukan rute perjalanan dan memperbarui intensitas pheromone pada setiap edge yang dilewati. Hasil yang diperoleh untuk contoh kasus yang diambil yaitu panjang rute terpendek yang dilalui pengantar koran sebesar 18,814 km dengan rute terpendek dimulai dari Jalan Gusti Sulung Lelanang – Jalan A. Marzuki – Jalan M. Sohor – Jalan Prof. M. Yamin Gg Sederhana – Jalan Pangeran Natakusuma Gg Sekolah – Jalan Pangeran Natakusuma Gg Jambi – Jalan Alianyang Gg Kencana 2 – Jalan Bukit Barisan – Jalan Johar – Jalan Setia Budi – Jalan Wr. Supratman – Jalan Gusti Sulung Lelanang.

Kata Kunci : Algoritma Ant System, Traveling Salesman Problem