...

PENERAPAN METODE ALGORITMA GENETIK UNTUK

by user

on
Category: Documents
1

views

Report

Comments

Transcript

PENERAPAN METODE ALGORITMA GENETIK UNTUK
PENERAPAN METODE ALGORITMA GENETIK
UNTUK MEMECAHKAN MASALAH
PENENTUAN RUTE KENDARAAN BERKENDALA
KAPASITAS
Wijaya Satria 1
Manahan P Siallagan S. Si, M. T1
Santi Novani, S.Si1
1 Jurusan Teknik Informatika, FT UNIKOM, e-mail : ...........
JURUSAN TEKNIK INFORMATIKA
FAKULTAS TEKNIK DAN ILMU KOMPUTER
UNIVERSITAS KOMPUTER INDONESIA
2004
ABSTRAK
Masalah penentuan rute sering di jumpai dalam kejadian sehari-hari, baik
penentuan rute transportasi untuk orang atau kendaraan. Beberapa contoh dapat
disebutkan antara lain adalah penentuan rute bis sekolah, rute pengumpulan surat dari
kotak surat, rute kunjungan dokter, rute salesman dan sebagainya.
Dalam tugas akhir ini akan dibahas salah satu masalah penentuan rute yang
dikenal sebagai masalah penentuan rute kendaraan (Vehicle Routing Problem, VRP)
khususnya masalah penentuan rute kendaraan berkendala kapasitas (Capacitated
Vehicle Routing Problem, CVRP). Hal ini dilakukan karena hasil yang didapatkan dari
penentuan rute tersebut memiliki pengaruh yang besar terhadap perusahaan atau
lembaga yang berkepentingan.
Tugas akhir ini mengimplementasikan cara pendekatan Algoritma Genetik
yang merupakan salah satu algoritma pencarian umum. Pendekatan ini meniru prinsip
evolusi alam sebagai metode untuk memecahkan masalah optimasi parameter. Pada
algoritma genetik, obyek masalah terus diperbaiki dengan proses genetik seperti
terjadinya evolusi alam, yang terus diperbaiki terus-menerus. Algoritma genetik
diajukan dengan harapan diperolehnya suatu cara penyelesaian masalah penentuan rute
kendaraan berkendala kapasitas yang lebih baik. Sebagai algoritma pembanding
algoritma sweep disertakan disini untuk melihat performansi dari algoritma genetik
tersebut .
Hasil akhir pengujian pada beberapa data set penelitian, menunjukkan bahwa
algoritma genetik pada persoalan penentuan rute kendaraan berkendala kapasitas ini
dapat memperoleh solusi yang cukup baik. Walaupun hasilnya masih cukup jauh dari
solusi optimal. Algoritma genetik ini dapat diajukan sebagai salah satu alternatif
pemecahan dalam persoalan penentuan rute kendaran berkendala_kapasitas.
Kata kunci : Algoritma genetik, Algoritma Sweep, VRP, Vehicle Routing Problem,
CVRP, Capacitated Vehicle Routing Problem.
1
ABSTRACT
Routing problem is a common matter for people nowadays, in deciding
transportation route for people or vehicles. Several examples which can be decribe are
schoolbus problem, mail delivery routing problem, doctor visit routing, salesman
routing problem , etc.
This final project will be discuss about one of routing which is known as
Vehicle Routing Problem (VRP), especially Capacitated Vehicle Routing Problem
(CVRP). This problem were discuss because of its great influence for the people,
company or any asscociation involve.
This final project use genetic algorithm approach which is common is general
searching algorithm. This approach is using nature evolution principle as the method of
solving the parameter of optimation problem. In genetic algorithm, the problem are
continously improve by genetic process like in nature evolution. The genetic algorithm
were used by the writer in order to make a better capacitated vehicle routing problem.
As a comparator, the writer use sweep algorithm to see the performance of the genetic
algorithm.
The result shows that the genetic algorithm in capacitated vehicle routing
problem could serve as a good solution. Eventhough the result this far haven’t got the
optimal problem, this genetic algorithm can be of alternative solution in capacitated
vehicle routing problem.
Keywords : Genetic Algorithm, Sweep Algorithm, VRP, Vehicle Routing Problem,
CVRP, Capacitated Vehicle Routing Problem.
2
dimulai dan berakhir didepot dan
setiap pelanggan pada setiap rute
hanya dilayani sekali dan hanya oleh
satu kendaraan yang tidak melebihi
kapasitas yang sudah ditentukan.
Metode-metode
yang
dihasilkan untuk pemecahan CVRP
ini
secara
umum
dapat
dikelompokkan
dalam
dua
kelompok. Kelompok pertama adalah
menggunakan
metode
optimasi
(exact) yang menghasilkan jawaban
terbaik (optimal) dari persoalan.
Kelompok kedua adalah kelompok
yang menggunakan pendekatan
intuisi yang lebih dikenal dengan
metode heuristik. Dari kedua
kelompok metode di atas, tampaknya
metode-metode
yang
bersifat
heuristik mempunyai masa depan
penggunaan yang lebih luas.
Alasannya adalah bahwa metodemetode tersebut dalam proses
perhitungannya membutuhkan waktu
yang
relatif
lebih
singkat
dibandingkan metode-metode dari
kelompok pertama, karena lebih
sedikitnya strategi pemeriksaan yang
harus dilakukan, dengan kualitas
hasil yang cukup baik.
Beberapa metode heuristik
yang telah dikembangkan antara lain
adalah metode metaheuristik yang
meliputi algoritma genetik, simulated
annealing, tabu search dan lain-lain
Dalam tugas akhir ini penulis akan
menggunakan metode algoritma
genetik dimana algoritma genetik
adalah algoritma pencarian yang
berdasarkan pada mekanisme sistem
natural yakni genetik dan seleksi
alam. Untuk melihat performansi
algoritma
genetik
dalam
menyelesaikan
CVRP
maka
diperlukan
metode-metode
lain
I. PENDAHULUAN
1.1 Latar Belakang
Masalah
penentuan
rute
sering di jumpai dalam kejadian
sehari-hari. Salah satu diantara
sekian banyak persoalan penentuan
rute tersebut dikenal sebagai masalah
penentuan rute kendaraan (Vehicle
Routing Problem, yang selanjutnya
disingkat sebagai VRP). VRP adalah
suatu permasalahan distribusi dengan
kendaraan pengangkut yang diawali
dari suatu titik pusat tertentu (
disebut
depot),
yang
harus
mengunjungi – selama periode
tertentu – pelanggan-pelanggan yang
tersebar secara geografis, untuk
memenuhi kebutuhan pelangganpelanggan tersebut. Representasi graf
dari salah satu solusi VRP dapat
dilihat pada gambar 1 dibawah ini.
Gambar 1 : Representasi graf solusi VRP
Versi paling umum dari VRP
adalah (Capacitated Vehicle Routing
Problem -CVRP), yang dapat
dideskripsikan sebagai berikut: ada
sebuah
depot
utama,
yang
menggunakan sejumlah kendaran
pengiriman bebas, dengan kapasitas
pengiriman identik, untuk melayani
permintaan sejumlah pelanggan.
Tentukan kumpulan rute dengan
biaya rute minimum dengan semua
pelanggan dilayani. Semua rute
3
2. Algoritma
yang
akan
digunakan dalam pemecahan
CVRP
adalah
algoritma
genetik sedangkan algoritma
sweep
hanya
sebagai
pembanding
dari
hasil
pengujian data yang diujikan
pada program yang dibangun.
3. Data
penelitian
yang
digunakan untuk pengujian
diambil dari salah satu contoh
masalah CVRP yang diambil
dari internet.
dalam
menyelesaikan
CVRP
tersebut. Metode yang digunakan
adalah metode dua phase dimana
algoritma yang digunakan dalam
metode dua phase ini yaitu algoritma
sweep. Studi dilakukan dengan jalan
menguji
dan
membandingkan
beberapa set data penelitian pada
kedua algoritma tersebut.
1.2 Perumusan Masalah
Berdasarkan
pertimbangan
diatas, maka pada tugas akhir ini
akan dibahas suatu pendekatan
algoritma
genetik
untuk
menyelesaikan Capacitated Vehicle
Routing Prolem (CVRP) dengan
kriteria minimasi jarak dan waktu
komputasi. Sedangkan algoritma
sweep hanya sebagai pembanding
dari hasil pengujian data yang di
ujikan pada program yang dibangun
II. LANDASAN TEORI
2.1 VRP
VRP
merupakan
suatu
permasalahan distribusi dengan
kendaraan pengangkut yang diawali
dari suatu titik pusat tertentu (
disebut
depot),
yang
harus
mengunjungi – selama periode
tertentu – pelanggan-pelanggan yang
tersebar secara geografis, untuk
memenuhi kebutuhan pelangganpelanggan tersebut.
1.3 Tujuan
Tujuan dari penulisan ini
yaitu untuk :
1. Dapat
memahami
dan
memecahkan VRP khususnya
CVRP dengan menggunakan
algoritma genetik.
2. Dapat
membuat
prosedur
algoritma
genetik
untuk
memecahkan masalah CVRP dan
menerapkannya dalam sebuah
aplikasi.
3. Melakukan pengujian terhadap
beberapa set data penelitian
dengan
tujuan
untuk
mendapatkan
solusi
dari
algoritma tersebut.
2.2 CVRP
CVRP
merupakan
versi
paling umum dari VRP, yang dapat
dideskripsikan sebagai berikut: ada
sebuah
depot
central,
yang
menggunakan kendaran pengiriman
bebas, dengan kapasitas pengiriman
identik , untuk melayani permintaan
sejumlah pelanggan. Kendaraan
harus menyelesaikan pengiriman
dengan biaya total perjalanan
minimum, dimana biaya cij adalah
jarak dari pelanggan i ke pelanggan j,
dengan i,j ∈ [1,n]. Jarak antara
pelanggan adalah simetri, contoh
cij=cji dan juga cii=0. Solusi untuk
1.4 Batasan Masalah
1. Persoalan
yang
akan
dipecahkan adalah persoalan
CVRP dengan depot tunggal.
4
baru, yang disebut keturunan
(offspring) dibentuk dengan cara :
1. Penggabungan dua kromosom
dari
generasi
sekarang
menggunakan operator crossover
2. Modifikasi suatu kromosom
menggunakan operator mutasi
Setelah pembentukan keturunan,
generasi baru dibangun dengan cara :
1. Seleksi, sesuai dengan nilai
fitness, beberapa dari parental
dan keturunan
2. Menolak yang lain untuk
menjaga jumlah populasi agar
tetap
Algoritma Genetik melakukan proses
pencarian nilai optimal secara
pararel.
Dengan
menggunakan
operator, dia akan melakukan
rekombinasi antar kromosom.
masalah
CVRP
ini
haruslah
himpunan dari n pelanggan dan
setiap rute yang terbentuk tidak
melebihi kapasitas kendaraan yang
dioperasikan pada rute tersebut.
2.3 Algoritma Sweep
Algoritma sweep merupakan
salah satu algoritma metode dua
phase yang terdiri dari dua bagian
yaitu: phase pertama terdiri dari
clustering
pelanggan
dengan
menugaskan mereka pada kendaraan
yang ada, dan phase kedua adalah
membangun rute-rute untuk masingmasing cluster.
2.4 Algoritma Genetik
Algoritma genetik merupakan
algoritma
pencarian
yang
berdasarkan pada mekanisme sistem
natural yakni genetik dan seleksi
alam. Dalam aplikasi algoritma
genetik, variabel solusi dikodekan
kedalam struktur string yang
merepresentasikan barisan gen, yang
merupakan karakteristik dari solusi
problem.
Berbeda
dengan
teknik
searching konvensional, Algoritma
Genetik dimulai dengan sekumpulan
solusi random inisial yang disebut
populasi. Masing-masing individu
dalam populasi disebut kromosom
yang merepresentasikan suatu solusi
terhadap
permasalahan
yang
sebenarnya. Suatu kromoson adalah
simbol string, biasanya berbentuk
string bit biner. Kromosom terlibat
dalam suatu iterasi berkelanjutan
yang disebut generasi. Setiap
generasi,
semua
kromosom
dievaluasi, menggunakan beberapa
ukuran fitness. Untuk membuat
generasi selanjutnya, kromosom
Gambar 2 : Digram alir algoritma genetik
III ANALISIS MASALAH
3.1 Deskripsi Masalah
Masalah
rute
kendaran
(Vehicle Routing Problem -VRP)
adalah sebuah masalah optimasi
kombinatorial kompleks, yang dapat
dilihat sebagai gabungan dari dua
masalah populer yaitu: Travelling
Salesperson (TSP) dan Bin Packing
5
(BPP).
Masalah
VRP
dapat
dideskripsikan
sebagai
berikut:
diberikan satu armada kendaraan
dengan kapasitas seragam, sebuah
depot
umum,
dan
beberapa
permintaan
pelanggan
(yang
disajikan sebagai kumpulan poinpoin yang tersebar secara geografis .
Tentukan kumpulan rute dengan
biaya rute minimum dengan semua
pelanggan dilayani. Semua rute
dimulai dan berakhir didepot dan
mereka harus didesain dengan cara
dimana setiap pelanggan dilayani
hanya sekali dan hanya oleh satu
kendaraan.
kendaraan.
Jumlah
seluruh
permintaan pelanggan yang ada pada
setiap tur harus berada dalam batas
kapasitas kendaraan. Tujuannya
adalah untuk meminimalkan total
biaya perjalanan. Ini juga bisa berarti
jarak antar titik/node atau kuantitas
lainnya yang mana kualitas solusi
bergantung padanya, berdasarkan
pada VRP untuk dipecahkan. Mulai
sekarang akan disebut sebagai biaya.
Model
matematika
digambarkan pada sebuah graf
(N , A) . Sekumpulan titik/node N
mewakili sekumpulan pelanggan C
dari 1 sampai n dengan penambahan
depot sebagai titik 0. Kumpulan
busur A terdiri dari hubungan antar
titik/node yang mungkin. Sebuah
hubungan antara setiap dua titik/node
pada graf akan dimasukkan dalam A
ini. Setiap busur (i, j ) ∈ A memiliki
cij
yang
biaya
perjalanan
3.2 Pemodelan
Versi paling umum dari VRP
adalah CVRP. Pemodelan untuk
CVRP memiliki parameter-parameter
berikut:
n
adalah jumlah pelanggan,
K
menunjukkan kapasitas setiap
kendaraan,
di
menunjukkan
permintaan
pelanggan i (dalam unit yang
sama
sebagai
kapasitas
kendaraan) dan
cij
adalah biaya perjalanan dari
berhubungan
dengannya.
Diasumsikan biayanya simetris,
contoh cij = c ji , dan juga bahwa
cii = 0 .
Kumpulan
kendaraan
seragam adalah V . Kendaraankendaraan
tersebut
memiliki
kapasitas K dan semua pelanggan
mempunyai permintaan d i . Satusatunya variabel keputusan adalah
X ijv :
pelanggan i ke pelanggan j .
Semua parameter dianggap nilai
integer tidak negatif. Sekumpulan
kendaraan
homogen
dengan
kapasitas terbatas K dan sebuah
depot utama, dengan indeks 0,
melakukan
perngiriman
ke
pelanggan, dengan indeks 1 sampai
n.
Permasalahannya
adalah
menentukan rute pasti setiap
kendaraan dimulai dan diakhiri di
depot. Setiap pelanggan harus
dipasangkan dengan tepat satu
tur/rute, karena setiap pelanggan
hanya bisa dilayani oleh satu
Fungsi
obyektif
dari
matematika ini adalah:
min ∑ ∑ cij X ijv
(1)
bergantung pada :
∑ ∑ X ijv = 1 ∀i ∈ C
(2)
v∈V (i , j )∈ A
v∈V j∈N
6
model
∑d ∑ X
i∈C
i
j∈N
∑X
v
0j
∑X
v
ik
j∈C
v∈V
v
ij
=1
≤ K ∀v ∈ V
(3)
∀v ∈ V
(4)
Tabel 1 Jarak dan permintaan pelanggan
− ∑ X kjv = 0
j∈N
∀k ∈ C dan ∀v ∈ V
X ijv ∈ {0,1},
(5)
∀{i, j}∈ A dan ∀v ∈ V
(6)
Persamaan
2
untuk
memastikan
setiap
pelanggan
dipasangkan dengan tepat satu
kendaraan. Tepat satu busur dari
pelanggan i dipilih, tak peduli
apakah busur itu menuju pelanggan
lain atau menuju depot. Pada
persamaan 3 batasan kapasitas
dipastikan.
Jumlah
permintaan
pelanggan keseluruhan dalam setiap
kendaraan v harus lebih kecil atau
sama dengan kapasitas kendaraan.
Batasan alur ditunjukkan pada
persamaan 4 dan 5. Pertama, setiap
kendaraan hanya boleh keluar dari
depot
sekali.
Kedua,
jumlah
kendaraan memasuki setiap k
pelanggan dan depot harus sama
dengan jumlah kendaraan keluar.
Berdasarkan definisi diatas,
diperoleh
suatu
kesimpulan
mengenai input dari persoalan CVRP
:
1. Input persoalan CVRP adalah
daftar jarak pelanggan, daftar
permintaan tiap pelanggan dan
kapasitas kendaraan.
terminologi
graf,
2. Dalam
kumpulan pelanggan atau titik
pada persoalan CVRP adalah
sebuah graf lengkap dengan
bobot sisi adalah jarak antar
pelanggan.
Pada persoalan dalam dunia
nyata,
jarak
antar
pelanggan
mungkin tidak disediakan melainkan
dihitung
berdasarkan
posisi
koordinat tiap pelanggan, misal
jika pelanggan satu berada pada
koordinat (3.1) dan pelanggan dua
berada pada koordinat (8.6) maka
jarak antar pelanggan satu dan dua
adalah 7.07. Pada Tabel 3.1 disajikan
data jarak dan permintaan pelanggan
dengan kapasitas kendaran C=4500,
yang mana data tersebut nantinya
akan menjadi salah satu inputan
persoalan CVRP di dalam tugas
akhir ini.
3.3 Pemecahan Masalah dengan
Algoritma Sweep
Pada prosedur ini asumsikan
bahwa Capacitated Vehicle Routing
Problem adalah mengikuti teori
Euclidean dan para pelanggan
dilokasikan dengan koordinat polar
( ri ,θ i ) dengan depot r1 = 0 dan suatu
pelanggan i* yang berubah-ubah
7
pada θ i* = 0 . Urutkan pelanggan
individu mengandung beberapa rute,
setiap individu mengandung subset
pelanggan terurut dan semua
permintaan yang termasuk pada
masalah harus berada dalam salah
satu rute. Sebagai contoh, kromosom
pada gambar 3 mewakili solusi yang
disajikan pada gambar 1.
sehingga θ 2 ≤ K ≤ θ n .
Phase 1
Langkah 1 : Pilih kendaraan k
yang tidak digunakan
Langkah 2 : Mulai dari pelanggan
i yang bebas dengan
θi
terkecil
sudut
termasuk pelangganpelanggan
yang
berurutan i+1, i+2, ...
dalam rute sampai
pembatas
kapasitas
pada kendaraan k
tercapai
Langkah 3 : Jika semua pelanggan
telah “tersapu” atau
semua
kendaraan
telah terpakai, masuk
ke fasa 2, kalau tidak
kembali ke step 1r
Phase 2
Langkah 4 : Selesaikan
masalah
Traveling Salesman
Problem untuk setiap
set pelanggan yang
ditugaskan
pada
masing-masing
kendaraan
untuk
membentuk rute-rute
akhir
Gambar 3 : Representasi kromosom
3.4.2 Inisialisasi populasi
Pada awal proses Algoritma
Genetik perlu ditentukan terlebih
dahulu populasi awal yang akan
diproses. Populasi awal ini dipilih
secara
random.
Pada
tahap
inisialisasi perlu diketahui juga
berapa jumlah parameter yang akan
disusun menjadi string, lebar dari
tiap parameter dan ukuran populasi
dalam tiap generasi.
Semua populasi inisialisasi
untuk masalah CVRP didalam tugas
akhir ini dihasilkan secara acak
menurut algoritma berikut :
Prosedur Inisialiasasi
1. Bangun sekumpulan D dengan
permutasi
acak
untuk
semua
permintaan
2. While disana terdapat elemen dalam
D Repeat :
2.1. Buat satu rute baru dengan K
permintaan. K adalah nilai acak
antara 1 dan elemen D yang
sekarang
2.2. Hapus K elemen pertama dari D
dan tugaskan mereka sebagai
rute baru.
3.4 Pemecahan Masalah dengan
Algoritma Genetik
3.4.1 Representasi genetik
Untuk
merepresentasikan
kandidat solusi sebuah kumpulan
CVRP maka harus ditentukan
terlebih dahulu jumlah kendaraan
yang dibutuhkan, partisi permintaan
berdasarkan kendaraan dan juga
urutan pengiriman untuk setiap rute.
Dimana materi genetik sebuah
Gambar 4: Prosedur inisialisasi
8
menghasilkan
layak.
3.4.3 Modul evaluasi
Modul evaluasi berisi suatu
fungsi evaluasi yang mengukur nilai
kromosom terhadap permasalahan.
Fungsi evaluasi ini menggunakan
fitness,
yaitu
ukuran
relatif
kecocokkan terhadap permasalahan
yang ada. Langkah pertama dalam
tiap-tiap
generasi
adalah
mengevaluasi kromosom-kromosom
pada generasi saat itu. Masingmasing kromosom didekodekan,
diambil parameter-parameter solusi
dan dievaluasi untuk dilihat seberapa
tingkat
’kecocokan’
parameter
terhadap sistem yang dimodelkan.
Fungsi
evaluasi
fitness
yang
digunakan adalah :
fevaluasi = fitness =
∑ ( ∑) c
v∈V i , j ∈ A
ij
fobyektif= fitnessmin = min ∑
v∈V i , j ∈ A
ij
yang
3.4.4.1 Seleksi
Seleksi
berguna
untuk
menentukan suatu individu dalam
populasi yang akan menurunkan
semua atau sebagian dari materi
genetik yang dimilikinya pada
individu generasi berikutnya. Pada
tugas akhir ini metode seleksi yang
digunakan adalah metode ranking.
Pada metode ini kemungkinan
terpilihnya
suatu
kromosom
ditentukan
oleh
ranking
dari
kromosom tersebut. Sebagai contoh,
20 % kromosom terbaik akan terpilih
sebanyak 2 kali untuk masingmasing individu, 20 % populasi
ranking terbawah tidak terpilih sama
sekali, dan sisanya terpilih hanya
sekali untuk setiap individu. Dengan
metoda ini kromosom superior yang
mungkin hadir pada suatu generasi
tidak
dapat
dengan
cepat
mendominasi populasi tersebut,
sehingga tidak menghambat proses
eksplorasi pada generasi-generasi
berikutnya.
X ijv
∑c
( )
solusi-solusi
X ijv
3.4.4 Operator-operator genetik
Operator-operator genetik
(seleksi, crossover dan mutasi) pada
algoritma genetik untuk CVRP harus
mampu menyelesaikan penyajian dua
level. Sehingga, mereka mampu
mengubah urutan pengiriman dengan
rute spesifik dan memodifikasi
alokasi permintaan untuk kendaran.
Disamping itu operator-operator
tersebut tidak hanya dapat menukar
pelanggan dari satu rute ke rute
lainnya, tapi juga memodifikasi
jumlah kendaraan yang termasuk
dalam sebuah solusi (menambah dan
menghapus rute). Kebutuhan penting
lainnya, adalah bahwa operatoroperator genetik tersebut harus selalu
3.4.4.2 Crossover
Operator crossover yang
digunakan dalam pendekatan ini
tidak
memberikan
pertukaran
material genetik yang sama antar dua
parent. Tetapi, ketika satu idividu
dari set yang dipilih digunakan pada
operator ini, individu tersebut akan
menerima satu fragment material
genetik (lebih tepatnya disebut rute)
dari individu yang lain dan
memasukkannya pada rute pertama.
Setelah
dimasukkan,
proses
perbaikan akan memeriksa rute asli
dari
individu
penerima
dan
9
Prosedur mutasi swap
menghapus semua pelanggan yang
juga muncul pada rute asli. Hal ini
akan menjamin bahwa kromosom
baru yang terbentuk adalah sah,
karena tidak ada perulangan titik.
Selama operasi ini donor tidak akan
dirubah.
Prosedur
berikut
menunjukkan bagaimana operator
crossover tersebut diterapkan pada
individu dari kumpulan yang terpilih.
1. For setiap keturunan dari hasil
cossover Repeat :
1.1 Bankitkan sebuah nilai secara acak,
kemudian bandingkan nilai tersebut
terhadap probabilitas mutasi.
If nilai < probabilitas mutasi
then pilih dua pelangan secara
acak dari keturunan hasil
crossover
dan
swap
mereka. Kedua pelanggan
tersebut dapat berada pada
rute yang sama atau rute
yang berbeda
else not swap.
End
Prosedur crossover
1. For setiap individu I1 dari kumpulan S
yang terpilih Repeat :
1.1 Pilih secara acak individu I2 lainnya
dari S
1.2 Dari materi genetik individu I2 pilih
secara acak sebuah sub-rute
1.3 Masukkan sub-rute yang terpilih
dari individu I2 kedalam materi
genetik
individu I1 sebagai rute pertama
1.4 Dari materi genetik asal individu I1
hapus semua pelanggan yang juga
muncul pada subrute, menghasilkan
keturunan.
Gambar 6: Prosedur mutasi swap
IV.
IMPLEMENTASI
PENGUJIAN
DAN
4.1 Implementasi Perangkat lunak
Program dimplementasikan
kedalam perangkat lunak yang
disebut
dengan
Matlab
6.5.
Perangkat lunak yang dibuat terdiri
dari dua pilihan, yaitu pilihan
pertama
dengan
menggunakan
algoritma genetik dan pilihan yang
kedua
menggunakan
algoritma
sweep
Gambar 5: Prosedur crossover
3.4.4.3 Mutasi
Mutasi diaplikasikan untuk
setiap keturunan setelah crossover.
Operasi
ini
bekerja
dengan
mengubah bit dalam solusi dengan
beberapa
kemungkinan.
Dalam
CVRP,
operator
mutasi
mengidentifikasikan sebuah peran
dari mengubah jalan atau menukar.
Adapun operator mutasi yang akan
digunakan dalam tugas akhir ini
adalah operator mutasi swap.
Prosedur
berikut
menunjukkan
bagaimana operator mutasi swap
tersebut diterapkan pada keturunan
hasil crossover.
4.2 Hasil Pengujian
4.2.1 Pengujian dengan algoritma
genetik
Pengujian
terbaik
pada
program yang dibangun dengan
menggunakan metode algoritma
genetik dalam menyelesaikan CVRP
menggunakan parameter-parameter
sebagai berikut :
1. Banyaknya populasi = 400
2. Maksimum generasi = 100
10
3. Probabilitas crossover = 0.75
4. Probabilitas mutasi = 0.2
Hasil akhir pengujian terbaik
untuk data tabel 1 yang diperoleh
dengan algoritma genetik dapat
dilihat pada tabel 2 dibawah ini.
masing-masing kendaraan
tidak
melebihi kapasitas yang dizinkan
yaitu 4500. dan total jarak yang
dihasilkan yaitu 435.447 dan waktu
komputasi 2.093 detik.
Tabel 3 Hasil pengujian algoritma sweep
Tabel 2 Hasil pengujian terbaik algoritma
untuk data tabel 1
genetik untuk data tabel 1
V. KESIMPULAN
Berdasarkan hasil pengujian,
maka dapat dibuat suatu kesimpulan
sebagai berikut :
dari
pengujian
1. Hasil
menunjukkan bahwa algoritma
genetik dan algoritma sweep
dapat
diterapkan
dalam
memecahkan masalah CVRP.
2. Jika dilihat dari solusi yang
dihasilkan maka algoritma sweep
untuk sementara lebih baik dari
algoritma genetik. Hal ini
dikarenakan belum ditemukannya
penyetingan parameter yang tepat
untuk
pengujian
algoritma
genetik
tersebut,
alasannya
karena penyetingan parameter
pada algoritma genetik sangat
mempengaruhi
solusi
yang
dihasilkan.
3. Pencarian dengan menggunakan
algoritma genetik membutuhkan
waktu yang cukup lama untuk
menghasilkan solusi optimal jika
banyaknya populasi dan generasi
Dari hasil pengujian terbaik
untuk data tabel 1 diperoleh jumlah
kendaraan yang dibutuhkan untuk
data tabel 1 adalah 7 buah kendaraan
dengan
kapasitas masing-masing
kendaraan tidak melebihi kapasitas
yang dizinkan yaitu 4500 dan total
jarak yang dihasilkan yaitu 528.536
dan waktu komputasi 358.259 detik.
4.2.2 Pengujian_dengan algoritma
sweep
Pengujian pada program yang
dibangun dengan menggunakan
algoritma sweep untuk data tabel 1
yang diperoleh untuk algoritma
sweep dapat dilihat pada tabel 3.
Dari
hasil
pengujian
algoritma sweep untuk data tabel 1
diperoleh jumlah kendaraan yang
dibutuhkan untuk data tabel adalah 3
buah kendaraan dengan kapasitas
11
sangat besar.
4. Implementasi algoritma genetik
pada
program
matlab
membutuhkan waktu yang cukup
lama atau lambat dalam eksekusi
programnya. Hal ini dikarenakan
bahasa dalam program matlab
langsung diartikan.
desain Sistem Kontrol dengan
MATLAB,
Penerbit
ANDI
Yogyakarta.
6. Mitsuo Gen, Runwei Cheng,
Genetic
Algorithms
and
Engineering Design, John Willey
& Sons, 1997
7. Mustafa, Mempelajari Beberapa
Algoritma
Heuristik
untuk
masalah
Penentuan
Rute
Kendaraan
dengan
Depot
Tunggal, Tugas Akhir Jurusan
Teknik Industri,ITB, 1983
8. P. Machado, J. Tavares, F. B.
Pereira, and E. Costa, “Vehicle
Routing Problem: Doing it the
Evolutionary Way,” To appear at
GECCO-2002 Proceedings, 2002
9. S. Han, Y. Tabata, A hybrid
genetic Algorithm for the Vehicle
Routing
Problem
with
Controlling Lethal Gene
10. T.K. Ralphsy, L. Kopmanz, W.R.
Pulleyblankx, and L.E. Trotter, Jr,
On The Capacitated Vehicle
Routing Problem,
http://www.lehigh.edu/~tkr2/rese
arch/papers/VRP.pdf,
tanggal
akses 29 Juli 2004
Michalewicz,
Genetic
11. Z
Algorithms + Data Structure =
Evolution Programs, Third,
Revised and Extended Edition
DAFTAR PUSTAKA
1. A. S. Bjarnadottir, Solving the
Vehicle Routing Problem with
Genetic
Algorithms,
http://www.imm.dtu.dk/pubdb/vi
ews/edoc_download.php/3183/pd
f/imm3183.pdf , tanggal akses 29
Juli 2004
2. D. Hanselman, B. littlefield,
Matlab,
Penerbit
ANDI
Yogyakarta
Kuncicky,
Hull,
3. Etter,
Pengenalan Matlab 6. Penerbit
PT INDEKS
4. F. B. Pereira, J. Tavares, P.
Machado, and E. Costa, “GVR: a
New Genetic Representation for
the Vehicle Routing Problem,”
Submitted to AICS 2002 13 th
Irish Conference on Artificial
Intelligence
and
Cognitive
Science, Limerick, Ireland, 2002
5. Hartanto, Prasetyo, Analisis dan
12
Fly UP