Optimasi Genetic Algorithm dengan Simulated Annealing untuk Multiple Depot Capacitated Vehicle Routing Problem

Aditya Permana

Informasi Umum

Kode

113090291

Klasifikasi

518.172 - Algorithm-Research Methods

Jenis

Karya Ilmiah - Skripsi (S1) - Reference

Subjek

Algorithm Analysis

Dilihat

34 kali

Informasi Lainnya

Abstraksi

Multiple Depot Vehicle Routing Problem (MDCVRP) adalah salah satu jenis permasalahan dari Vehicle Routing Problem (VRP) yang merupakan permasalahan dalam optimasi pengaturan rute suatu kendaraan dari beberapa depot mengunjungi semua pelanggan. Dimana tujuan objektifnya adalah untuk mencari biaya termurah untuk melayani semua pelanggan tanpa melewati berat angkut maksimum dari tiap kendaraan. Secara matematis MDCBRP ini merupakan permasalahan kombinatorial.<br> Sebagai permasalahan yang termasuk ke dalam kelas NP-hard (non-deterministic polynomial-time hard), MDCVRP ini akan diselesaikan dengan menggunakan algoritma Genetic Algorithm yang dioptimasi dengan algoritma Simulated Annealing, yang merupakan salah satu algoritma heuristik yang mampu memecahkan permasalahan NP-hard secara cepat dengan melakukan beberapa pendekatan solusi secara matematis, sehingga solusi yang didapat mampu mendekati solusi optimum global.<br> Pada dasarnya optimasi Genetic Algorithm dengan Simulated Annealing (GASA) ini merupakan hybrid dari 2 jenis algoritma yaitu Genetic Algorithm (GA) dan Simulated Annealing (SA). Penentuan nilai dari parameter-parameter GA dan SA adalah faktor-faktor yang akan diobservasi karena sangat menentukan solusi optimal yang didapatkan.<br> Dari hasil percobaan yang telah dilakukan menunjukan bahwa Simulated Annealing mampu meningkatkan nilai fitness dari Genetic Algorithm sekitar 1 % untuk semua dataset. Multiple Depot Vehicle Routing Problem, Vehicle Routing Problem, non-deterministic polynomial-time hard, Optimasi Genetic Algorithm dengan Simulated Annealing, Genetic Algorithm , Simulated Annealing.