20
2.3.2
Teknik Penyelesaian Vehicle Routing Problem
Ada
beberapa
teknik
penyelesaian
yang
telah
dipakai
untuk
Vehicle
Routing
Problem ini, seperti :
1. Dynamic Programming
Dynamic
Programming
adalah
implicit
enumerative
search
method yang
dapat
dilihat
sebagai
teknik Divide and Conquer. Untuk menyelesaikan masalah yang
besar,
dilakukan
pemecahan
masalah
tersebut
menjadi
bagian-bagian kecil
yang
serupa dan independen di mana bagian-bagian tersebut dapat dipecahkan dengan
metode yang serupa dengan masalah induk. Setelah bagian-bagian kecil tersebut
diselesaikan
maka hasil-hasil yang diperoleh digabung kembali dengan suatu
metode tertentu untuk memberi solusi yang sebenarnya pada masalah tersebut.
2. Branch and Bound
Pendekatan branch and bound terdiri dari dua prosedur dasar. Branching adalah
proses mempartisi masalah yang besar menjadi dua atau lebih masalah kecil dan
bounding adalah proses menghitung batas bawah pada solusi optimal dari
masalah
kecil
tersebut. Bounding
function
yang
digunakan
yaitu,
pemrosesan
hanya
dilakukan
pada branch
yang
baik
dan
branch
yang
buruk
tidak
akan
diproses dengan
harapan branch yang baik akan memberikan hasil yang optimal
di proses selanjutnya.
3. Branch and Cut
Pendekatan
branch
and
cut
merupakan
pendekatan
yang
menggunakan
branch
and
bound
dengan
penambahan
algoritma
pemotongan
atau cutting
pada
solusi
yang didapatkan. Proses yang dilakukan adalah dengan mengaplikasikan branch
and
bound
pada
masalah
yang
akan
menghasilkan
suatu
solusi
yang
nantinya
 |