29
Dalam proses koding, partikel direpresentasikan sebagai sebuah array 2 dimensi
seperti tergambar
pada gambar 2.11.
Untuk CVRP dengan sejumlah N pelanggan
yang
akan
dilayani
oleh
sejumlah
K
kendaraan,
dimensi
pertama
dari
array
2
dimensi
dari
partikel adalah
vektor berdimensi N × K (s1, s2, ..., s
N
×
K
), di
mana
si (i = 1, 2, ..., N × K)
adalah
angka
yang
berada
pada
interval
[1,
N
×
K]
yang
tidak
sama
satu
dengan
yang
lainnya.
l
=
s
i
{(s
i
-
1)/N} × N
merepresentasikan
pelanggan
yang
ke-l
dan
k
=
{(s
i
-
1)/N}
+
1
merepresentasikan
kendaraan
ke-k.
Dimensi
kedua
juga
vektor
berdimensi
N
×
K,
di
mana
setiap
posisi
bernilai
0
atau
1.
Jika
bit
ke-(si)
bernilai
1,
itu
melambangkan kalau pelanggan ke-l (l = s
i
{(s
i
-
1)/N} × N) akan dilayani oleh
kendaraan ke-k (k = {(s
i
-
1)/N} + 1). Selain
itu, pelanggan ke-l tidak akan dilayani oleh
kendaraan ke-k.
Didasarkan oleh konstrain CVRP, harus dapat dipastikan bahwa setiap pelanggan
dilayani tepat sekali oleh
tepat
satu kendaraan, panjang
maksimum dari
setiap rute tidak
boleh melebihi
konstrain dan total
permintaan dari
rute
manapun tidak
boleh
melebihi
kapasitas dari kendaraan. Tetapi, DPSO tidak dapat memastikan syarat-syarat konstrain
tersebut
terpenuhi,
maka
perlu
dilakukan
pemeriksaan terhadap solusi setelah operasi
DPSO, sebagai berikut :
Periksa setiap partikel untuk
setiap rute.
Jika
nilai
lebih
dari
satu
posisi
dari
posisi-posisi
yang
bersangkutan
dalam partikel
bernilai
1,
pilih
secara
acak
satu
posisi
dari posisi-posisi tersebut dan jadikan nilainya 1 dan lainnya
bernilai 0. Jika nilai dari
semua posisi dari posisi-posisi
tersebut bernilai 0 maka pilih secara acak satu posisi dan
jadikan
nilainya 1 dan
yang
lain tidak berubah. Jika total jarak dari sebuah
rute
melebihi
nilai
yang
dibatasi
atau
total
permintaan
dari
setiap
rute
melebihi
kapasitas
dari
|