PERBANDINGAN PENGGUNAAN ALGORITMA GREEDY DAN ALGORITMA GENETIKA DALAM PENYELESAIAN MASALAH PERJALANAN SALESMAN

Abstract

Masalah perjalanan salesman adalah sebuah persoalan optimasi untuk mendapatkan rute terpendek yang harus dilalui oleh seorang pedagang keliling (salesman). Salesman tersebut harus mengunjungi sejumlah kota tepat satu kali untuk tiap kota dan kembali ke kota asal dengan akumulasi biaya perjalanan (jarak, waktu, kenyamanan, dan lain-lain) yang minimum. Banyak metode telah dikembangkan untuk menyelesaikan masalah perjalanan salesman. Dalam skripsi ini dibahas dua metode (algoritma) yang akan dibandingkan dalam menyelesaikan masalah perjalanan salesman yaitu algoritma Greedy dan algoritma Genetika. Untuk mempermudah dalam melakukan perhitungan, langkah-langkah dari algoritma Greedy dan algoritma Genetika selanjutnya diimplementasikan dengan program komputer menggunakan software Matlab 6.5 Release 13. Adapun tujuan dari penulisan skripsi ini yaitu mengetahui perbandingan panjang cycle Hamilton yang dihasilkan dan waktu eksekusi program yang dibutuhkan oleh algoritma Greedy dan algoritma Genetika dalam menyelesaikan masalah perjalanan salesman. Pada penelitian ini diperoleh hasil bahwa untuk jumlah kota lebih dari 25, algoritma Greedy dapat menghasilkan cycle Hamilton yang lebih pendek dibandingkan algoritma Genetika. Akan tetapi jika ditinjau dari waktu eksekusi program yang dibutuhkan kedua algoritma dalam menyelesaikan masalah perjalanan salesman maka algoritma Genetika membutuhkan waktu yang lebih cepat dari pada algoritma Greedy.