Perpustakaan Digital ITB

Travelling Salesman Problem (TSP) merupakan salah satu permasalahan optimasi kombinatorial yang bertujuan untuk menentukan rute optimal dengan mengunjungi setiap kota tepat satu kali dan kembali ke kota asal dengan nilai fungsi objektif minimum. Seiring bertambahnya jumlah kota yang digunakan, jumlah kemungkinan solusi meningkat secara eksponensial sehingga diperlukan metode optimasi yang mampu menghasilkan solusi mendekati optimal dalam waktu komputasi yang efisien. Salah satu metode yang banyak digunakan untuk menyelesaikan TSP adalah Genetic Algorithm (GA). Penelitian ini menerapkan Genetic Algorithm untuk menyelesaikan Travelling Salesman Problem pada 34 kota di Pulau Jawa. Fungsi objektif yang digunakan berupa minimisasi jarak tempuh dan waktu perjalanan antar kota. Data jarak dan waktu diperoleh dari Google Maps dengan asumsi perjalanan menggunakan kendaraan roda empat tanpa melalui jalan tol. Penelitian ini berfokus pada analisis pengaruh variasi operator crossover terhadap performa Genetic Algorithm. Enam operator crossover yang digunakan meliputi Partially Mapped Crossover (PMX), Cycle Crossover (CX), Modified Crossover, Order Crossover (OX), Order Based Crossover (OBX), dan Position Based Crossover (PBX). Kinerja masing-masing operator crossover dievaluasi berdasarkan kualitas solusi yang dihasilkan, nilai fitness terbaik, serta kemampuan konvergensi algoritma dalam menemukan rute optimal. Hasil penelitian diharapkan dapat memberikan informasi mengenai operator crossover yang paling efektif untuk menyelesaikan Travelling Salesman Problem dengan fungsi objektif berupa jarak dan waktu tempuh. Penelitian ini juga diharapkan dapat memberikan kontribusi dalam pengembangan Genetic Algorithm untuk permasalahan optimasi rute.