Implementasi Algoritma Genetika untuk menyelesaikan Capacited Vehicle Routin Problem

RACHMAWATI, Dian, Prof.Drs. Subanar, Ph.D

2008 | Tesis | S2 Ilmu Komputer

Capacited Vehicle Routing Problem merupakan salah satu masalah yang lazim ditemui dalam kehidupan sehari – hari. Persoalan yang terpenting dalam menyelesaikan masalah ini adalah untuk menentukan rute dan jumlah kendaraan yang harus digunakan dalam memenuhi permintaan dari konsumen yang ada. Telah banyak algoritma yang dikembangkan untuk menyelesaikan masalah ini. Secara umum algoritma yang bekerja dengan transalasi deterministik, di mana setiap langkah diambil berdasarkan formula eksak dinilai kurang tanggguh untuk menyelesaikan masalah ini. Algoritma genetika merupakan salah satu alternatif solusi permasalahan Capacited Vehicle Routing Problem ini. Algoritma genetika ini terilhami dari teori seleksi alam yang diajukan oleh Charles Darwin. Ide utama dari algoritma ini adalah memilih individu terbaik dari sebuah populasi induk dan melakukan rekombinasi antar induk, untuk membangkitkan individu baru yang diharapkan lebih baik dari individu sebelumnya. Dengan cara kerja yang cenderung berbeda dengan algoritma lain, algoritma genetika dinilai mampu untuk membangkitkan solusi mendekati optimal untuk Capacited Vehicle Routing Problem.

Capacited Vehicle Routing Problem is one of the common problem which could happen in daily traffic at town. The most important solution to be offerred is to pre-defined a route and number of allocated vehicle to serve the customer. There are many algorithms has already developed in order to solve this problem. Generally, the algorithm with the deterministic transaltion method, where every step is taken based on exact formulas are not strong enough to solve the problem. Hence, another algorithm which can be used alternatively to solve the Capacited Vehicle Routing Problem is Genetic Algorithm. This idea of this algorithm comes from the Evolution Theory of Charles Darwin, which is only the best route was choosen. An individual was being choosen from a parent population and then recombined to another individual that has been choosen from another parent population to create a new individu. This new individual expected to be better from the rest individu at the population. With this method, the genetic algorithm found to be able to offer a best Capacited Vehicle Routing Problem.

Kata Kunci : Algoritma Gentika,Capacited Vehicle Routing Problem, Genetic Algorithm, Capacited Vehicle Routing Problem, Population, Selection