Implementasi Algortima Genetika dalam Penentuan Rute Terbaik Pendistribusian BBM Pada PT. Pertamina Berbasis Android

Traveling Salesman Problem (TSP) adalah kasus seorang salesman yang akan mengunjungi sejumlah n poin, dimana semua poin harus dikunjungi tepat satu kali kecuali poin awal sehingga solusi optimal akan diambil dalam bentuk perjalanan rute dengan jarak minimum ke semua kemungkinan yang ada. Ada beberapa algoritma yang biasa digunakan untuk menyelesaikan traveling salesman problem, salah satunya adalah algoritma genetika. Algoritma Genetika adalah algoritma heuristik yang digunakan untuk menyelesaikan masalah dengan mengoptimalkan masalah yang ada dengan meniru proses evolusi makhluk hidup. Tujuan penulisan skripsi ini adalah untuk menguji kemampuan dan mengetahui bagaimana algoritma genetika bekerja dalam menemukan solusi optimal dalam menyelesaikan TSP dengan memanfaatkan fitur Google Maps pada perangkat telepon genggam berbasis android. Dalam skripsi ini terdapat 96 titik SPBU tujuan yang direpresentasikan sebagai simpul dan ada 1 titik Kantor Distribusi Suplai PT. Pertamina sebagai simpul awal dan akhir. Rute perjalanan direpresentasikan sebagai grafik terhubung (connected graph) dan grafik berbobot (weighted graph) dan kategori TSP yang digunakan adalah TSP asimetris. Penelitian ini menggunakan nilai Pc sebesar 0.5, Pm 0.01, MaxGen 1000 generasi, dan PopSize sebesar 20 kromosom. Dimisalkan jumlah titik yang ingin dikunjungi sebesar 6 titik, yaitu SPBU 51.601.65, SPBU 51.601.66, SPBU 51.601.77, SPBU 54.601.03, SPBU 54.601.05, dan Kantor PT. Pertamina sebagai titik awal dan titik akhir rute. Telah didapatkan urutan rute terpendek awal dengan jarak minimum sebesar 45.80 Km yang kemudian dioptimalkan dengan menggunakan algoritma genetika sehingga didapatkan jarak minimal sebesar 42.20 Km.