Keflin Regina Willa Pengarang ADRIANA FANGGIDAE Dosen Pembimbing 1 Adriana Fanggidae Ketua Penguji Arfan Yeheskiel Mauko Penguji 2 Bertha Selviana Djahi Penguji 1

Traveling Salesman Problem (TSP) merupakan permasalahan optimasi yang sering ditemui dalam pencarian rute terpendek. Permasalahan ini dapat diselesaikan dengan berbagai macam algoritma, salah satunya adalah algoritma genetika. Algoritma genetika merupakan algoritma heuristik yang berdasar pada mekanisme evolusi biologis dan efisiensinya bergantung pada operator seleksi, kawin silang (crossover), dan mutasi. Penelitian ini menganalisis penerapan algoritma optimasi greedy pada metode kawin silang Single-Point Crossover (SPX) untuk menyelesaikan permasalahan TSP. Parameter yang digunakan adalah probabilitas crossover = 0.25, probabilitas mutasi = 0.01, jumlah generasi = 1000, threshold konvergensi populasi = 80%, jumlah kota (25, 50, 75, 100), dan ukuran populasi (30, 60, 90, 120). Hasil pengujian menunjukkan bahwa Greedy Single-Point Crossover (GrSPX) mampu memberikan rata-rata nilai fitness minimum sebesar 36% lebih baik dibandingkan metode SPX, rata-rata generasi yang dibutuhkan 73% lebih baik dari SPX, dan dari 16 percobaan, 13 diantaranya menunjukkan rata-rata waktu komputasi SPX 88% lebih baik dari GrSPX sedangkan sisanya menunjukkan rata-rata waktu komputasi GrSPX 51% lebih baik dari SPX.