Skripsi a.n Zhafier Zulfiqar (G54190031) Ant Colony Optimization untuk Traveling Salesman Problem: Perbandingan Kinerja dengan Mixed Integer Linear Programming.

Abstract

Traveling Salesman Problem (TSP) merupakan permasalahan optimisasi yang bertujuan menentukan rute terpendek dengan mengunjungi setiap lokasi tepat satu kali dan kembali ke titik awal. Peningkatan jumlah lokasi menyebabkan kompleksitas permasalahan semakin tinggi sehingga diperlukan metode penyelesaian yang efisien. Penelitian ini menerapkan Ant Colony Optimization (ACO), yaitu algoritma metaheuristik yang terinspirasi dari perilaku semut dalam menemukan jalur terpendek berdasarkan jejak feromon, untuk menyelesaikan TSP. Kinerja ACO diuji pada beberapa skenario jumlah node dan dibandingkan dengan metode eksak Mixed Integer Linear Programming (MILP). Hasil penelitian menunjukkan bahwa ACO mampu menghasilkan solusi yang mendekati optimal dengan waktu komputasi yang lebih cepat, terutama pada permasalahan dengan jumlah node yang besar. MILP menghasilkan solusi optimal, namun membutuhkan waktu komputasi yang lebih lama seiring bertambahnya ukuran permasalahan.