PENERAPAN ALGORITMA GENETIKA DAN ALGORITMA SWEEP PADA PENYELESAIAN CAPACITATED VEHICLE ROUTING PROBLEM (CVRP) UNTUK OPTIMASI PENDISTRIBUSIAN GULA
SKRIPSI
Diajukan kepada Fakultas Matematika dan Ilmu Pengetahuan Alam Universitas Negeri Yogyakarta Untuk Memenuhi Sebagian Persyaratan Guna Memperoleh Gelar Sarjana Sains
Oleh Septia Eva Fradina NIM 13305144005
PROGRAM STUDI MATEMATIKA JURUSAN PENDIDIKAN MATEMATIKA FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM UNIVERSITAS NEGERI YOGYAKARTA 2017
i
ii
iii
iv
MOTTO “Jadikanlah sabar dan sholat sebagai penolongmu, Sesungguhnya Allah bersama orang-orang yang sabar” (Q.S Al-Baqarah: 153)
“Dimana ada usaha disitu ada jalan, semua akan indah jika keberhasilan yang diraih diimbangi dengan sebuah proses kerja keras yang tak mengenal letih”
“Banyak kegagalan dalam hidup ini dikarenakan orang-orang tidak menyadari betapa dekatnya mereka dengan keberhasilan saat mereka menyerah” (Thomas Alva Edison)
v
PERSEMBAHAN Dengan mengucapkan syukur kehadirat Allah SWT, atas berkat dan hidayahnyaNya skripsi ini dapat diselesaikan. Tidak terlupa shalawat dan salam kepada Rasullulah Nabi Muhammad SAW atas petunjuk jalan kebenaran bagi umat manusia di muka bumi. Ku persembahkan karya kecilku ini kepada : Ibukku, Ibu Tri Wahati, terima kasih atas semua pengorbanan, dukungan, doa, motivasi serta kasih sayang yang tak terhingga. Kakakku, Yuli Hermawan, terima kasih selama ini sudah menjadi sosok kakak yang begitu baik yang selalu memberi dorongan, semangat, dan motivasi kepada adikmu ini. Sahabat-sahabatku. Rizka Nur Pratiwi, Yan Anisa Dewi, serta Azyan khusnul Chotimah. Terimakasih atas bantuan dan dukungan yang selalu diberikan.
vi
PENERAPAN ALGORITMA GENETIKA DAN ALGORITMA SWEEP PADA PENYELESAIAN CAPACITATED VEHICLE ROUTING PROBLEM (CVRP) UNTUK OPTIMASI PENDISTRIBUSIAN GULA
Oleh Septia Eva Fradina 13305144005
ABSTRAK Capacitated Vechile Routing Problem (CVRP) merupakan suatu permasalahan yang berkaitan dengan penentuan rute yang optimal dengan memperhatikan kendala setiap kendaraan memiliki kapasitas tertentu. Masalah CVRP yang akan dibahas adalah menentukan rute pendistribusian gula agar diperoleh rute pendistribusian terbaik atau meminimumkan total jarak tempuh semua kendaraan. Tujuan dari penelitian ini adalah untuk menyelesaikan masalah CVRP dengan algoritma genetika dan algoritma sweep yang selanjutnya dilakukan analisis perbandingan untuk melihat algoritma yang lebih baik dalam menentukan rute optimum pendistribusian. Proses Algoritma Genetika dimulai dengan membangkitkan populasi awal, kemudian dihitung nilai fitness setiap individu. Individu pada populasi, diseleksi dengan menggunakan metode Roulette Wheel selection dan dilakukan crossover dengan metode order cross over. Generasi baru hasil crossover dikenai proses mutasi dengan metode swapping mutation. Proses terakhir yaitu menyusun populasi baru dan mengulangi proses seleksi, crossover, dan mutasi sampai dengan jumlah iterasi yang diinginkan. Sedangkan untuk menentukan rute terpendek menggunakan algoritma sweep dilakukan dua tahap yaitu tahap pengelompokan (clustering) dan tahap pembentukan rute menggunakan metode Nearest Neighbour. Berdasarkan perhitungan yang diperoleh menggunakan algoritma genetika, diperoleh total jarak tempuh kendaraan 147,95 km dengan waktu tempuh 175 menit. Hasil yang diperoleh dari perhitungan menggunakan algoritma sweep diperoleh total jarak tempuh kendaraan 156,4 km dengan waktu tempuh 202 menit.. Dengan demikian dapat dikatakan bahwa solusi yang dihasilkan algoritma genetika lebih baik dari segi jarak maupun waktu jika dibandingkan algoritma sweep dalam menyelesaikan capacitated vehicle routing problem (CVRP).
Kata Kunci : Algoritma Genetika, Algoritma Sweep, CVRP, Pendistribusian Gula
vii
KATA PENGANTAR Puji syukur penulis panjatkan kehadirat Allah SWT yang telah melimpahkan rahmat dan hidayah-Nya, sehingga penulis dapat menyelesaikan tugas akhir skripsi dengan judul “Penerapan Algoritma Genetika dan Algoritma Sweep pada Penyelesaian Capacitated Vehicle Routing Problem (CVRP) untuk Optimasi Pendistribusian Gula”. Penulisan skripsi ini guna memenuhi salah satu syarat dalam memperoleh gelar Sarjana Sains (S.Si) pada program Studi Matematika. Penyusunan skripsi ini tidak lepas dari doa, bimbingan, bantuan, serta dorongan dari berbagai pihak. Oleh karena itu, penulis mengucapkan terima kasih kepada : 1. Bapak Dr. Hartono, M.Si selaku Dekan Fakultas Matematika dan Ilmu Pengetahuan Alam Universitas Negeri Yogyakarta yang telah memberi izin penulisan skripsi ini. 2.
Bapak Dr. Ali Mahmudi, M.Pd selaku Ketua Jurusan Pendidikan Matematika yang telah memberi kelancaran dalam pengurusan administrasi selama penyusunan skripsi.
3. Bapak Dr. Agus Maman Abadi, M,Si selaku Ketua Program Studi Matematika yang telah mendukung dan memberi kelancaran dalam penulisan skripsi ini. 4. Ibu Fitriana Yuli Saptaningtyas, M.Si, selaku dosen pembimbing yang telah memberikan arahan, motivasi, serta saran kepada penulis. 5. Dewan penguji yang telah memberikan kritik serta saran dalam perbaikan skripsi ini.
viii
ix
DAFTAR ISI HALAMAN JUDUL .......................................................................................
i
HALAMAN PERSETUJUAN .........................................................................
ii
HALAMAN PERNYATAAN .........................................................................
iii
HALAMAN PENGESAHAN .........................................................................
iv
HALAMAN MOTTO ......................................................................................
v
HALAMAN PERSEMBAHAN ......................................................................
vi
ABSTRAK .......................................................................................................
vii
KATA PENGANTAR .....................................................................................
vii
DAFTAR ISI ....................................................................................................
x
DAFTAR GAMBAR .......................................................................................
xiv
DAFTAR TABEL ............................................................................................
xvi
DAFTAR LAMPIRAN .................................................................................... xvii DAFTAR SIMBOL ......................................................................................... xviii BAB I PENDAHULUAN A. Latar Belakang .....................................................................................
1
B. Batasan Masalah ..................................................................................
5
x
C. Rumusan Masalah ................................................................................
6
D. Tujuan Penelitian .................................................................................
6
E. Manfaat Penelitian ...............................................................................
6
BAB II KAJIAN TEORI A. Masalah Optimasi ................................................................................
8
B. Graf ......................................................................................................
9
1. Definisi Graf ..................................................................................
9
2. Jenis-Jenis Graf ..............................................................................
10
3. Keterhubungan ...............................................................................
13
C. Travelling Salesman Problem (TSP) ...................................................
16
1. Pengertian Travelling Salesman Problem (TSP) ...........................
16
2. Penyelesaian Travelling Salesman Problem (TSP) .......................
17
D. Vehicle Routing Problem (VRP) ..........................................................
19
E. Capacitated Vehicle Routing Problem (CVRP) ..................................
21
F. Algoritma Sweep ..................................................................................
24
1. Tahap Pengelompokkan .................................................................
25
2. Tahap Pembentukan Rute ..............................................................
26
G. Algoritma Genetika ..............................................................................
27
1. Definisi Algoritma Genetika ..........................................................
28
2. Skema Alur Algoritma Genetika ...................................................
31
3. Komponen Algoritma Genetika .....................................................
32
xi
a. Penyandian Permasalahan ........................................................
32
b. Membangkitkan Populasi Awal ...............................................
33
c. Evaluasi Nilai Fitness ..............................................................
34
d. Seleksi (Selection) ....................................................................
35
e. Pindah Silang (Crossover) .......................................................
37
f. Mutasi (Mutation) ....................................................................
41
g. Elitism ......................................................................................
43
h. Pembentukan Populasi Baru ....................................................
43
H. Penelitian Yang Relevan ......................................................................
44
BAB III PEMBAHASAN A. Model CVRP Untuk Optimasi Distribusi Gula Di Pabrik Gula Yogyakarta B. Penyelesaian Model CVRP Menggunakan Algoritma Sweep .............
46
1. Matriks Jarak Dan Matriks Jarak Tempuh .....................................
51
2. Tahap Penyelesaian Model CVRP Dengan Algoritma Sweep .......
51
a. Tahap Pengelompokkan ...........................................................
52
b. Tahap Pembentukan Rute ........................................................
56
c. Rute yang Diperoleh Menggunakan Algoritma Sweep ............
76
C. Penyelesaian Model CVRP Menggunakan Algoritma Genetika .........
79
1. Penyandian Gen (Pengkodean) ......................................................
79
2. Membangkitkan Populasi Awal (Spanning) ..................................
81
3. Evaluasi Nilai Fitness ....................................................................
82
xii
4. Seleksi (Selection) ..........................................................................
83
5. Pindah Silang (Crossover) .............................................................
84
6. Mutasi ............................................................................................
86
7. Pembentukan Populasi Baru ..........................................................
87
D. Perbandingan Rute yang Diperoleh Menggunakan Algoritma Sweep dengan Algoritma Genetika ..............................................................................
98
BAB IV PENUTUP A. Kesimpulan .......................................................................................... 100 B. Saran .................................................................................................... 107 DAFTAR PUSTAKA ..................................................................................... 109 LAMPIRAN .................................................................................................... 112
xiii
DAFTAR GAMBAR Gambar 2.1 Graf Nol dengan 2 Simpul ..............................................................
10
Gambar 2.2 Graf Lengkap ..................................................................................
11
Gambar 2.3 Graf Bipartit ....................................................................................
11
Gambar 2.4 Graf Tidak Sederhana .....................................................................
11
Gambar 2.5 Graf Teratur .....................................................................................
12
Gambar 2.6 Graf Tidak Teratur ..........................................................................
12
Gambar 2.7 Simpul Terhubung dari graf N ........................................................
14
Gambar 2.8 Sirkuit dan Lintasan Hamilton ........................................................
16
Gambar 2.9 Diagram Alir Algoritma Sweep .......................................................
27
Gambar 2.10 Skema Algoritma Genetika oleh David Golderg ..........................
32
Gambar 2.11 Skema Algoritma Genetika oleh Michalewichz ...........................
33
Gambar 2.12 Sistematika Proses Crossover .......................................................
38
Gambar 2.13 Ilustrasi OX Operator ....................................................................
39
Gambar 2.4 Sistematika Proses Mutasi ..............................................................
42
Gambar 3.1 Koordinat Kartesius Agen Pendistribusian Gula ............................
52
Gambar 3.2 Peta Agen Pendistribusian Gula di Yogyakarta ..............................
56
xiv
Gambar 3.3 Peta Agen Cluster 1 ........................................................................
57
Gambar 3.4 Peta Agen Cluster 2 ........................................................................
57
Gambar 3.5 Peta Agen Cluster 3 ........................................................................
58
Gambar 3.6 Graf Pendistibusian Rute I Menggunakan Algoritma Sweep ..........
77
Gambar 3.7 Graf Pendistibusian Rute II Menggunakan Algoritma Sweep ........
78
Gambar 3.8 Graf Pendistibusian Rute III Menggunakan Algoritma Sweep .......
78
Gambar 3.9 Grafik Generasi ke-1000 .................................................................
91
Gambar 3.10 Graf Pendistibusian Rute I Menggunakan Algoritma Genetika ...
93
Gambar 3.11 Graf Pendistibusian Rute II Menggunakan Algoritma Genetika ..
94
Gambar 3.12 Graf Pendistibusian Rute III Menggunakan Algoritma Genetika .
96
xv
DAFTAR TABEL Tabel 3.1 Hasil Perhitungan Koordinat Polar ..................................................... 53 Tabel 3.2 Hasil Penentuan Rute I Menggunakan Algoritma Sweep ................... 64 Tabel 3.3 Hasil Penentuan Rute II Menggunakan Algoritma Sweep .................. 69 Tabel 3.4 Hasil Penentuan Rute III Menggunakan Algoritma Sweep ................ 75 Tabel 3.5 Rute Menggunakan Algoritma Sweep ................................................ 76 Tabel 3.6 Representasi Gen ................................................................................ 79 Tabel 3.7 Pembagian Rute .................................................................................. 82 Tabel 3.8 Hasil Evaluasi Fitness Generasi Awal ................................................ 82 Tabel 3.9 Hasil Uji Coba Menggunakan Software Matlab ................................. 88 Tabel 3.10 Pembagian Rute pada Percobaan ke-10 ............................................ 92 Tabel 3.11 Hasil Penentuan Rute I Menggunakan Algoritma Genetika ............. 93 Tabel 3.12 Hasil Penentuan Rute II Menggunakan Algoritma Genetika ........... 95 Tabel 3.13 Hasil Penentuan Rute III Menggunakan Algoritma Genetika .......... 97 Tabel 3.14 Perbandingan Rute Algoritma Sweep dan Algoritma Genetika ........ 98
xvi
DAFTAR LAMPIRAN Lampiran 1 Matriks Jarak Tempuh Asal dan Tujuan Distribusi Gula ................ 112 Lampiran 2 Matriks Waktu Tempuh Asal dan Tujuan Distribusi Gula.............. 113 Lampiran 3 Data Permintaan Harian Gula di Yogyakarta .................................. 114 Lampiran 4 Langkah-langkah Menggambar Koordinat dengan Geogebra ........ 115 Lampiran 5 Surat Izin Penelitian ........................................................................ 121 Lampiran 6 Prosedur Algoritma Genetika .......................................................... 122 Lampiran 7 Populasi Generasi Awal Menggunakan Software Matlab ............... 134 Lampiran 8 Induk yang Terpilih Menggunakan Software Matlab ...................... 136 Lampiran 9 Hasil Crossover dengan Software Matlab ....................................... 139 Lampiran 10 Hasil Mutasi dengan Software Matlab .......................................... 142 Lampiran 11 Hasil Populasi Baru pada Generasi Selanjutnya ........................... 145 Lampiran 12 Nilai Fitness Generasi Selanjutnya ............................................... 147 Lampiran 13 Hasil Populasi Baru Generasi Ke-1000 ......................................... 148 Lampiran 14 Nilai Fitness Generasi Ke-1000 .................................................... 150
xvii
DAFTAR SIMBOL 𝐺(𝑉, 𝐸)
: Suatu graf G dengan titik V dan rusuk E
𝑉(𝐺)
: Himpunan titik tidak kosong dari suatu graf G
𝐸(𝐺)
: Himpunan rusuk dari suatu garf G
𝐶𝑖𝑗
: Jarak tempuh perjalanan dari agen i ke agen j
𝑋𝑖𝑗𝑘
: Variabel keputusan dan merupakan variabel biner
V
: Himpunan titik-titik lokasi depot dan agen
K
: Himpunan kendaraan
q
: Kapasitas kendaraan
𝑑𝑖
: Jumlah permintaan untuk titik i
𝑡𝑖𝑗
: Waktu tempuh kendaraan termasuk pelayanan
f
: Nilai fitness
xviii
