PERBANDINGAN METODE EKSAK, HEURISTIK DAN METAHEURISTIK DALAM PENYELESAIAN TRAVELING SALESMAN PROBLEM = COMPARISON OF EXACT, HEURISTIC, AND METAHEURISTIC METHODS FOR SOLVING THE TRAVELING SALESMAN PROBLEM

NOVANDA KEZIA AMELIA NATHALIA ROPI. Perbandingan Metode Eksak, Heuristik dan Metaheuristik dalam Penyelesaian Traveling Salesman Problem. (dibimbing oleh Prof. Agustinus Ribal, S.Si., M.Sc., PhD) Latar Belakang. Traveling Salesman Problem (TSP) merupakan salah satu permasalahan optimasi kombinatorial yang bertujuan untuk menentukan rute terpendek yang mengunjungi setiap kota tepat satu kali dan kembali ke titik awal. Tujuan. Penelitian ini membandingkan tiga pendekatan utama dalam penyelesaian TSP, yaitu metode eksak (Branch and Bound dan Cutting Plane), metode heuristik (Nearest Neighbor dan Cheapest Insertion), serta metode metaheurisik (Genetic Algorithm dan Ant Colony Optimization). Metode. Pengujian dilakukan pada dataset simetris dengan tiga kategori dataset: kecil (5 dan 10 kota), sedang (50 kota), dan besar (100 kota). Evaluasi kinerja dilakukan berdasarkan waktu komputasi dan kualitas solusi. Hasil. Hasil penelitian menunjukkan bahwa metode eksak memberikan solusi optimal namun memerlukan waktu komputasi yang signifikan pada dataset yang lebih besar. Metode heuristik menghasilkan solusi dalam waktu cepat, tetapi kualitasnya tidak selalu optimal. Sementara itu, metode metaheuristik mampu menyeimbangkan antara efisiensi waktu dan kualitas solusi, terutama pada dataset besar. Kesimpulan. Penelitian ini memberikan wawasan untuk memilih metode penyelesaian TSP yang sesuai berdasarkan kebutuhan operasional, terutama dalam konteks optimasi rute distribusi untuk mengurangi biaya dan meningkatkan efisiensi.