SKRIPSI Jurusan Matematika - Fakultas MIPA UM, 2017

Ukuran Huruf:  Kecil  Sedang  Besar

Pemanfaatan Local Search pada Algoritma Modified Savings dan Algoritma Clarke-Wright dalam Penyelesaian Multiple Depot Vehicle Routing Problem with Time Window (MDVRPTW)

Ainul Fidia

Abstrak


ABSTRAK

 

Fidia, Ainul. 2017. Pemanfaatan Local Search pada Algoritma Modified Savings dan Algoritma Clarke-Wright dalam Penyelesaian Multiple Depot Vehicle Routing Problem with Time Window (MDVRPTW). Skripsi, Jurusan Matematika, Fakultas Matematika dan Ilmu Pengetahuan Alam, Universitas Negeri Malang. Pembimbing: Dra. Sapti Wahyuningsih, M.Si.

 

Kata kunci: Multiple Depot Vehicle Routing Problem with Time Windows (MDVRPTW), Algoritma Modified Savings, Algoritma Clarke- Wright, Local Search, Interchange Descent.

Dalam bidang pendistribusian penentuan rute distribusi merupakan salah satu aspek penting. Secara khusus, masalah penentuan rute pendistribusian tergolong dalam materi Vehicle Routing Problem (VRP). Dua diantara varian VRP adalah VRPTW dan MDVRP. Kedua varian VRP tersebut dapat diperluas menjadi MDVRPTW yaitu penambahan kendala depot yang lebih dari satu, dan terdapat batasan time window.

Algoritma Modified Savings dan Algoritma Clarke-Wright dalam menyelesaikan MDVRPTW dapat dikembangkan dengan pemanfaatan local search. Pada Algoritma Modified Savings pengkombinasian rute berdasarkan penghitungan savings yang dimodifikasi dengan metode Farthest Insertion. Setelahi solusi awal terbentuk maka dilanjutkan dengan perbaikan rute menggunakan Exchange Local Search. Sebagai pembanding digunakan Algoritma Clarke-Wright untuk membentuk solusi awal kemudian dilakukan perbaikan rute menggunakan Interchange Descent hingga diperoleh solusi akhir. Interchange Descent meliputi perbaikan inter route dan intra route.

Hasil Algoritma Modified Savings dengan Exchange Local Search menunjukkan solusi akhir dengan total jarak tempuh dan waktu tempuh yang lebih minimal dibandingkan Algoritma Clarke Wright dengan Interchange Descent. Hal ini disebabkan pada pencarian solusi awal, urutan customer yang dilayani ditentukan menggunakan metode FI. Sedangkan pada Algoritma Clarke Wright merupakan metode savings secara umum yang tidak menjamin diperoleh solusi yang paling minimal. Pemanfaatan local search pada kedua algoritma tersebut juga berhasil untuk mengurangi total jarak dan waktu tempuh. Namun dari analisa kedua algoritma, Algoritma Modified Savings dengan Exchange Local Search memberikan hasil yang lebih baik.