Skripsi

Algoritma genetika pada Split Delivery Vehicles Routing Problem (SDVRP) dan implementasinya / Farid Tri Rahayuningsih

Abstrak
ABSTRAK Rahayuningsih Farid Tri. 2015. Algoritma Genetika pada Split Delivery Vehicle Routing Problem dan Implementasinya. Skripsi Jurusan Matematika Fakultas Matematika dan Ilmu Pengetahuan Alam Universitas Negeri Malang. Pembimbing (I) Dra. Sapti Wahyuningsih M.Si (II) Mohamad Yasin S.Kom M.Kom Kata kunci Vehicle Routing Problem (VRP) Split Delivery Vehicle Routing Problem (SDVRP) Algoritma Genetika Partial-Mapped Crossover Vehicle Routing Problem(VRP) merupakan salah satu terapan dari teori graph yang banyak digunakan untuk menyelesaikan permasalahan pendistribusian yaitu pencarian rute kendaraan dengan jarak tempuh minimum untuk melayani sejumlah customer. Salah satu perluasan dari VRP adalah Split Delivery Vehicle Routing Problem (SDVRP)yaitu perluasan VRP dengan tiap customer dapat dilayani dengan kendaraan yang berbeda untuk meminimalkan biaya pendistribusian. Perluasan ini perlu dilakukan jika jumlah permintaan customer sama besar atau lebih besar dengan kapasitas dari kendaraan.Algoritma genetika pada Split Delivery Vehicle Routing Problem (SDVRP) yaitu menentukan rute pendistribusian dengan jarak minimum dimana proses pendistribusian berawal dan berakhir di depot tiap customer boleh dikunjungi lebih dari satu kali oleh lebih dari satu kendaraan tanpa melanggar batasan kapasitas yaitu dalam satu rute jumlah permintaan customer tidak melebihi kapasitas angkut kendaraan. Algoritma genetika adalah suatu jenis struktur pencarian nilai optimal berdasarkan peniruan proses evolusi biologi. Algoritma genetika pada SDVRP terdiri dari enam langkah yaitu teknik pengkodean pembangkitan populasi awal dengan permutasi Josephus yang dilanjutkan dengan pembentukan rute berdasarkan kendala kapasitas kemudian perhitungan nilai fitness. Proses genetika berikutnya yaitu seleksi dengan metode Roulette Wheel pindah silang dengan metode Partial-Mapped Crossover (PMX) danmutasi dengan Inversion Mutation. Pemilihan metode Roulette Wheel PMX dan Inversion Mutation sebagai metode seleksi pindah silang dan mutasi karena metode tersebut merupakan metode yang paling sederhana tetapi mampu mewakili semua metode yang ada dan memberikan solusi alternatif yang dapat membantu didapatkannya solusi dari algoritma genetika untuk SDVRP. Selanjutnya untuk mempermudah dalam menyelesaikan permasalahan SDVRP dengan algoritma genetika maka direpresentasikan dalam program computer menggunakan Borland Delphi 7. Program yang telah dibuat disimulasi 75 dan 100 titik tanpa mengalami masalah sehingga dapat membantu menyelesaikan SDVRP dengan algoritma genetika. Meskipun program sangat membantu mempermudah dalam menghitung jarak minimum pada permasalahan pendistribusian namun program ini memiliki kelemahan yaitu lama proses perhitungan dipengaruhi oleh banyak populasi dan maksimum generasi yang diberikan.

Informasi Detail

DDC

Rs 518.1 RAH a

Prodi

Universitas Negeri Malang. Program Studi Matematika, 2015.

Deskripsi Fisik

ix, 83 lembar : il. tab. ; 30 cm.

Bahasa

Indonesia

No Reg

04911/KI/15

Edisi

Skripsi (Sarjana). Universitas Negeri Malang. 2015

Subjek

1. ALGORITMA
2. ALGORITMS

Pembimbing

1. Sapti Wahyuningsih; 2. Mohamad yasin

Lampiran Berkas