PENERAPAN ALGORITMA GENETIKA PADA TRAVELLING SALESMAN PROBLEM (TSP) (STUDI KASUS: PEDAGANG PERABOT KELILING DI KOTA KUPANG)

Abstract

Travelling Salesman Problem  (TSP) merupakan  salahsatu permasalahan optimasi yang terjadi di kehidupansehari-hari.  Permasalahan  pada  kasus  TSP  adalahbagaimana  membangun  rute  terpendek  yang  akandilalui salesman. Pemodelan kasus ini akan diterapkanpada pedagang perabot keliling di Kota Kupang dengan menerapkan metode algoritma genetika. Saat ini proses penjualan perabot masih dilakukan dengan cara lama dimana lokasi yang dipakai tidak menentu, sehingga belum dapat diputuskan bahwa rute perjalanan yang dihasilkan sudah optimal.

 Untuk membuat rute yang optimal pada TSP penulis menggunakan algoritma genetika. Dimana algoritma ini merupakan salah satu metode yang dipakai untuk pemecahan masalah optimasi. Algoritma ini mengikuti proses genetik dari kromosom – kromosom biologi yang berdasar pada teori evolusi Charles Darwin. Sesuai dengan studi kasus yang diambil dalam skripsi ini, maka akan diambil 10 titik kelurahan untuk menghasilkan sebuah perjalan yang akan dipakai sebagai jadwal perjalanan seorang pedagang. Dalam penelitian inipun akan diteliti bagaimana pengaruh angka acak yang dipakai pada proses pindah silang.

Hasil penerapan algoritma genetika dapat memberikan solusi yang optimal untuk studi kasus pedagang perabot keliling. Hasil pengujian inipun memberikan jadwal perjalanan yang tetap untuk pedagang perabot keliling di Kota Kupang dan jadwal sendiri berisi rute perjalanan dengan titik kelurahan yang berbeda bagi pedagang serta jarak tempuh. Dan untuk angka acak yang dipakai dalam proses pindah silang yaitu angka acak terbesar dan terkecil. Angka acak terkecil berpengaruh positif terhadap nilai fitness, maka disarankan untuk menggunakan angka acak yang kecil saat proses pindah silang.