17
menghasilkan
beberapa
rute
sesuai
jumlah
kendaraan
seperti
pada
gambar
2.10.
Kasus
ini
sama
dengan
Travelling Salesman
Problem
(TSP),
hanya
saja
untuk
Travelling
Salesman
Problem
hanya
memiliki
satu
rute,
di
mana
perbaikan
rute
dilakukan
dalam
satu
rute
itu
sendiri,
sedangkan dalam
Vehicle
Routing
Problem memiliki
banyak
rute
yang
jumlahnya sesuai
kendaraan
yang
akan
dipakai
walaupun
tujuan
keduanya
sama
yaitu untuk mencari jarak minimum dengan melewati semua node sekali.
Jika VRP direpresentasikan dalam sebuah
graf G = (V,E). Notasi yang digunakan
adalah :
•
V= {v
0
,v1,v2,...,v
n
}
adalah himpunan verteks, di mana :
o
Asumsikan depot terletak di verteks v
0
o
Misalkan V’ = V tanpa elemen {v
0
}
digunakan sebagai himpunan n kota
•
A
=
{(v
i
,v
j
)
| v
i
,
v
j
?
V
;
i
?
j} adalah himpunan edge
•
C
adalah
matriks jarak
atau
biaya c
ij
antara pelanggan v
i
dan
v
j
yang
bernilai
non-
negatif
•
d adalah vektor dari permintaan / demand dari pelanggan
•
R
i
adalah rute dari kendaraan ke-i
•
k
adalah jumlah kendaraan (semua identik). Satu rute untuk tiap kendaraan.
Dengan setiap
verteks v
i
dalam V’ diasosiasikan dengan sejumlah barang q
i
yang
akan
diantarkan oleh
satu
kendaraan. Maka
VRP
bertujuan
untuk
menentukan
sejumlah
k
rute
kendaraan dengan
total
biaya
yang
minimum,
bermula
dan
berakhir
di
sebuah
depot, yang
setiap
verteks dalam V’ dikunjungi tepat sekali oleh satu kendaraan.
k
Akhirnya, biaya dari solusi masalah ini S adalah : F
VRP
(S) =
?
C(Ri)
i
=¹
 |