Implementasi Algoritma Clarke-Wright dan Algoritma Simulated Annealing pada Multi Depot Vehicle Routing pRoblem

Linda Ramah Sopani

Informasi Umum

Kode

113070314

Klasifikasi

005.1 - Computer programming

Jenis

Karya Ilmiah - Skripsi (S1) - Reference

Subjek

Informatika Teori Dan Pemrograman

Dilihat

570 kali

Informasi Lainnya

Abstraksi

ABSTRAKSI: Vehicle Routing Problem (VRP) adalah permasalahan optimasi mengenai adanya sejumlah pelanggan di lokasi tertentu yang memerlukan sejumlah barang dan harus dilayani dengan menggunakan sejumlah kendaraan dengan kapasitas muat terbatas. Multiple Depot Vehicle Routing Problem (MDVRP) adalah salah satu jenis dari VRP. MDVRP adalah VRP dengan kondisi dimana terdapat banyak depot (tempat simpan barang) untuk menyuplai kebutuhan pelanggan. Tujuan dari penyelesaian MDVRP adalah untuk menentukan rute perjalanan yang optimal yang harus dilalui dalam memenuhi permintaan pelanggan. Pada tugas akhir ini, pencarian rute kasus MDVRP akan diimplementasikan menggunakan algoritma Clarke-Wright atau algoritma Saving dan algoritma Simulated Annealing (SA). Data kasus MDVRP yang digunakan adalah data dari Cordeau, didapat dari web: http://neo.lcc.uma.es/radiaeb/ WebVRP/ . MDVRP akan diselesaikan dengan cara mengelompokan pelanggan terhadap depot terlebih dahulu dengan menggunakan algoritma Parallel Assignment. Setelah itu akan dibentuk rute pendistribusian barang tiap depot dengan menggunakan algoritma Clarke-Wright. Algoritma Simulated Annealing digunakan untuk menghindari jebakan optimum lokal, sekaligus melakukan pencarian penyelesaian rute yang lebih baik dari hasil algoritma Clarke-Wright. Untuk mengetahui performansi metode Clarke-Wright dan SA, pada tahap pengujian, solusi dari metode ini akan dibandingkan dengan solusi terbaik yang pernah ada dan solusi dari Genetic Algorithm.Kata Kunci : : Pencarian rute, Multiple Depot Vehicle Routing Problem (MDVRP),Clarke-Wright, Simulated Annealing (SA)ABSTRACT: Vehicle Routing Problem (VRP) is an optimization problem of the existence of some customers in a specific location that require a certain number of goods and shall be served by a number of vehicle which load capacity is limited. Multiple Depot Vehicle Routing Problem (MDVRP) is one kind of VRP. MDVRP is VRP which the condition has some depots (storehouse) to supply customer’s goods. The purpose of MDVRP is to determine the optimal route in fulfilling customer’s request. In this final project, the route searching of MDVRP will be implemented using the Clarke-Wright or Saving algorithm and Simulated Annealing algorithm (SA). The instances of MDVRP that will be used is from Cordeau’s instances, from website : http://neo.lcc.uma.es/radi-aeb/WebVRP/. MDVRP will be resolved by grouping the customers to depot in advance using the Parallel Assignment algrithm. Aftar that, the route will be established for each depot using the Clarke-Wright algorithm. Simulated Annealing algorithm is used to avoid the trap of local optimum, as well as to search a better route from the Clarke-Wright algorithm’s solution. To determine the performance of the Clarke-Wright algorithm and SA algorithm, in the testing phase, the solution of these methods will be compared with the best solution ever known and the solution of Genetic Algorithm.Keyword: Route searching, Multiple Depot Vehicle Routing Problem(MDVRP), Clarke-Wright, Simulated Annealing (SA).