SKRIPSI Jurusan Matematika - Fakultas MIPA UM, 2017

Ukuran Huruf:  Kecil  Sedang  Besar

Algoritma ILS-RVND pada Capacitated Vehicle Routing Problem with Time Window (CVRPTW) dan Implementasinya

Indrasari Kurnia Darojati

Abstrak


ABSTRAK

 

Darojati, Indrasari Kurnia. 2017. Algoritma ILS-RVND pada Capacitated Vehicle Routing Problem with Time Window (CVRPTW) dan Implementasinya, Skripsi, Jurusan Matematika, Fakultas Matematika dan Ilmu Pengetahuan Alam, Universitas Negeri Malang. Pembimbing: (I) Dra. Sapti Wahyuningsih, M.Si. (II) Darmawan Satyananda, S.T, M.T.

 

Kata Kunci: Graph, Vehicle Routing Problem (VRP), Capacitated Vehicle Routing Problem with Time Window (CVRPTW), ILS-RVND, distribusi.

Distribusi merupakan proses penyaluran produk dari produsen sampai ke tangan masyarakat atau konsumen. Pemilihan rute distribusi merupakan hal penting untuk mendapat jarak terpendek dan biaya yang seminimal mungkin. Dalam matematika, kajian terapan graph yang membahas tentang pencarian rute terpendek dalam sistem distribusi adalah Vehicle Routing Problem (VRP).

Capacitated Vehicle Routing Problem with Time Window (CVRPTW) merupakan bagian dari VRP dengan tambahan kendala batasan waktu dan kapasitas kendaraan yang seragam. Tujuan utama dari CVRPTW adalah meminimalisasi jarak tempuh perjalanan dengan tetap memerhatikan kendala yang ada. Dalam skripsi ini algoritma ILS-RVND digunakan untuk menyelesaikan permasalahan CVRPTW. Algoritma ILS-RVND merupakan algoritma heuristik yang melakukan multi-start sebanyak maksimum iterasi yang diperbolehkan (MaxIter), dimana pada setiap iterasinya terdapat tiga langkah penting. Langkah pertama merupakan pembentukan solusi awal menggunakan algoritma Sequential Insertion. Langkah kedua dan ketiga secara berturut-turut adalah tahap perbaikan local search yang menggunakan prosedur Random Variable Neighborhood Descent (RVND) dan prosedur Peturbasi. Langkah kedua dan ketiga dilakukan secara berulang-ulang sebanyak maksimum iterasi local search yang diperbolehkan (MaxIterILS).

Implementasi dari algoritma ILS-RVND untuk CVRPTW dalam bahasa pemrograman Borland Delphi 7.0 yang berhasil dirancang secara terstruktur. Aplikasi diuji coba untuk kasus 13 titik, 31 titik, dan 51 titik dari CVRP Library tipe E. Secara umum, ILS-RVND memberikan solusi yang lebih baik daripada Clarke-Wright dengan Local Search yang dibahas pada kajian pustaka.