Penyelesaian Travelling Salesman Problem Menggunakan Algoritma Ant Colony System

Abstract

Proses distribusi memerlukan strategi perencanaan rute yang efektif dan efisien untuk meminimalkan biaya operasional dan waktu pengiriman. Salah satu permasalahan di bidang optimasi yang berfokus pada pencarian rute terpendek adalah Travelling Salesman Problem (TSP). TSP dapat diselesaikan menggunakan metode eksak dan metode pendekatan. Namun, penyelesaian TSP dalam kasus besar dengan metode eksak cenderung memakan waktu yang sangat lama. Maka dari itu berbagai metode pendekatan dikembangkan untuk menyelesaikan TSP ini. Pada penelitian ini, TSP diselesaikan menggunakan metode pendekatan Ant Colony System (ACS) dan metode eksak Branch and Bound (BnB). Kemudian solusi akhir yang diperoleh dibandingkan dengan metode pendekatan lainnya di antaranya adalah Bee Colony Optimization (BCO), Ant Colony Optimization (ACO), Grey Wolf Optimization (GWO) dan Simulated Annealing (SA). Hasil yang diperoleh menunjukkan bawah algoritma ACS memiliki kinerja yang lebih baik dengan solusi yang dihasilkan paling mendekati optimal dan waktu komputasinya lebih cepat dibandingkan dengan metode BCO, ACO, GWO, dan SA.

The distribution process requires an effective and efficient route planning strategy to minimize operational costs and delivery time. One of the optimization problems that focuses on finding the shortest route is the Travelling Salesman Problem (TSP). The TSP can be solved using exact methods and approximation methods. However, solving the TSP in large-scale cases using exact methods tends to be very time-consuming. Therefore, various approximation methods have been developed to solve the TSP. In this study, the TSP is solved using the Ant Colony System (ACS) as an approximation method and Branch and Bound (BnB) as an exact method. The final solution is then compared with other approximation methods, including Bee Colony Optimization (BCO), Ant Colony Optimization (ACO), Grey Wolf Optimization (GWO) and Simulated Annealing (SA). Three TSP cases are examined in this study. The result show that the ACS algorithm performs better with producing solutions that are closest to optimal with faster computation times compared to the BCO, ACO, GWO, and SA methods.