EVALUASI ALGORITMA ANT COLONY SYSTEM: PERBANDINGAN DENGAN METODE EKSAK DAN METAHEURISTIK DALAM PENYELESAIAN TRAVELLING SALESMAN PROBLEM

Abstract

Salah satu permasalahan di bidang optimasi yang berfokus pada pencarian rute terpendek adalah Travelling Salesman Problem (TSP). TSP dikategorikan sebagai masalah NP-hard yang artinya tidak ada algoritma yang dapat menyelesaikannya secara optimal dalam waktu polinomial. Pada penelitian ini, TSP diselesaikan menggunakan metode pendekatan Ant Colony System (ACS) dan metode eksak Branch and Bound (BnB). Solusi akhir dibandingkan dengan metode pendekatan lainnya, yaitu Bee Colony Optimization (BCO), Ant Colony Optimization (ACO), Grey Wolf Optimization (GWO), dan Simulated Annealing (SA). Tiga kasus TSP dengan 20, 40, dan 60 kota diselesaikan menggunakan data hipotetik berupa koordinat kartesius. Hasil menunjukkan bahwa algoritma ACS memiliki kinerja lebih baik dengan solusi yang paling mendekati optimal dan waktu komputasi yang lebih cepat dibandingkan BCO, ACO, GWO, dan SA. Pada kasus 1 dan 2, ACS mencapai solusi global optimal; pada kasus 3, deviasi solusi ACS hanya sebesar 0,368%.