Aplikasi Algoritma Genetika Pada Kasus Vehicle Routing Problem with Time Windows

Abstract

Vehicle Routing Problem (VRP) adalah salah satu jenis masalah penentuan rute distribusi dimana terdapat sejumlah pelanggan yang dilayani oleh suatu depot, rute pengiriman harus dimulai dan berakhir di depot, dan pengiriman dilakukan dengan beberapa kendaraan yang memiliki kpaasitas tertentu. Semua pemintaaan pelanggan harus terpenuhi dan setiap pelnggan dilayani oleh satu kendaraan tepat satu kali. Vehicle Routing Problem with Time Wondows (VRPTW) adalah perluasan permasalahan dari VRP dengan tambahan time window disetiap depo dan pelanggan. Tujuan dari penulisan tugas akhir ini adalah mencari solusi yang terbaik dengan memanfaatkan algoritma Genetika sebagai metode pendekatan solusinya, sehingga dapat menghasilkan rute terpendek dan waktu yang ditempuh, serta mengetahui pengaruh parameter (probabilitas crossover, probabilitas mutasi, dan banyaknya generasi) terhadap solusi optimal yang didapatkan. Penelitian dilakukan melalui beberapa langkah, yaitu diawali dengan study literature, pengambilan dan pengumpulan data yang diperoleh dari skripsi Fatimah (2016) tentang pendistribusian barang dari PT. Amita Bara Sejahtera Jember, kemudian menerapkan Algoritma Genetika sebagai metode pencarian dan metode perhitungan. Selanjutnya membuat program sesuai algoritma yang digunakan dengan menggunakan software MATLAB. Kemudian membuat kesimpulan dari hasil yang didapat dari penerapan algoritma tersebut.Hasil penelitian yang diperoleh adalah total jarak yang ditempuh pada pengiriman 5 April 2016 sebesar 224,52 km dan total waktu 11 jam 21 menit 35 detik dikirimkan menggunakan 3 kendaraan. Pengiriman 14 April 2016, dihasilkan rute dengan total jarak tempuh adalah 126,342 km dan total waktu 6 jam 54 menit 28 detik dikirimkan menggunakan 3 kendaraan. Jika time windows yang digunakan semakin kecil, maka semakin banyak kendaraan yang dibutuhkan untuk pendistribusian. Pengaruh parameter probabilitas crossover (Pc) dan probabilitas mutasi (Pm)terhadap total jarak tempuh kasus VRPTW ini kurang terlihat. Pengaruh terhadap iterasi konvergen yaitu relatif semakin cepat konvergen jika nilai Pc atau Pm semakin besar. Pengaruh terhadap waktu komputasi yaitu semakin besar nilai Pc atau Pm, maka semakin lama waktu komputasi yang dibutuhkan.