IMPLEMENTASI ALGORITMA GENETIKA DENGAN VARIASI SELEKSI DALAM PENYELESAIAN CAPACITATED VEHICLE ROUTING PROBLEM WITH TIME WINDOWS (CVRPTW) UNTUK OPTIMASI RUTE PENDISTRIBUSIAN RASKIN DI KOTA YOGYAKARTA
TUGAS AKHIR SKRIPSI Diajukan kepada Fakultas Matematika dan Ilmu Pengetahuan Alam Universitas Negeri Yogyakarta untuk Memenuhi Sebagian Persyaratan Guna Memperoleh Gelar Sarjana Sains
Oleh : Yan Anisa Dewi 13305141046
PRODI MATEMATIKA JURUSAN PENDIDIKAN MATEMATIKA FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM UNIVERSITAS NEGERI YOGYAKARTA 2017
i
ii
iii
HALAMAN PERNYATAAN Saya yang bertanda tangan di bawah ini : Nama
: Yan Anisa Dewi
NIM
: 13305141046
Program Studi
: Matematika
Jurusan
: Pendidikan Matematika
Fakultas
: Matematika dan Ilmu Pengetahuan Alam
Judul Skripsi
: Implementasi Algoritma Genetika dengan Variasi Seleksi dalam Penyelesaian Capacitated Vehicle Routing Problem with Time Windows (CVRPTW) untuk Optimasi Rute Pendistribusian Raskin di Kota Yogyakarta
Menyatakan bahwa skripsi ini adalah benar-benar karya saya sendiri. Sepanjang pengetahuan saya tidak terdapat karya atau pendapat yang ditulis atau diterbitkan orang lain kecuali sebagai acuan atau kutipan dengan mengikuti tata penulisan karya ilmiah yang telah lazim. Apabila tebukti pernyataan saya ini tidak benar, maka sepenuhnya menjadi tanggungjawab saya dan saya siap menerima sanksi sesuai dengan ketentuan yang berlaku.
Yogyakarta, 5 April 2017 Yang menyatakan,
Yan Anisa Dewi NIM. 13305141046
iv
HALAMAN MOTTO Allah tidak membebani seseorang itu melainkan sesuai dengan kesanggupannya (Q.S. Al-Baqarah: 286) Sesungguhnya Allah tidak akan mengubah nasib suatu kaum hingga mereka mengubah diri mereka sendiri (Q.S. Ar-Raβd: 11) Usaha akan membuahkan hasil setelah seseorang tidak menyerah (Napoleon Hill) Bermimpilah, karena Tuhan akan memeluk mimpi-mimpi itu (Arai, Edensor)
v
HALAMAN PERSEMBAHAN Dengan iringan rasa syukur Alhamdulillah, saya persembahkan karya kecil ini kepada: Bapak Sumaryo dan Ibu Kiryati. Terimakasih atas motivasi, doa serta dukungan semangat yang tiada henti diberikan.
Kakak dan adikku, Jendry Prasetya dan Muh. Mifta Hurizka. Terimakasih selalu bersedia menjadi tempat untuk berkeluh kesah.
Sahabat-sahabatku. Rizka Nur Pratiwi, Septia Eva Fradina, Peni Susanti serta Dita Mardiana. Terimakasih atas bantuan dan dukungan yang selalu diberikan.
vi
IMPLEMENTASI ALGORITMA GENETIKA DENGAN VARIASI SELEKSI DALAM PENYELESAIAN CAPACITATED VEHICLE ROUTING PROBLEM WITH TIME WINDOWS (CVRPTW) UNTUK OPTIMASI RUTE PENDISTRIBUSIAN RASKIN DI KOTA YOGYAKARTA Oleh : Yan Anisa Dewi 13305141046
ABSTRAK Raskin merupakan salah satu program pemerintah dalam peningkatan kesejahteraan masyarakat berpendapatan rendah. Keberhasilan program raskin diukur berdasarkan tingkat pencapaian indikator, salah satunya tepat waktu. Untuk mencapai ketepatan waktu, maka permasalahan pendistribusian raskin ini dapat diformulasikan dalam suatu model matematika dengan memperhatikan rentang waktu pendistribusian atau yang lebih dikenal dengan time windows. Tujuan dari penelitian ini yaitu diperoleh penyelesaian rute optimum pendistribusian raskin dengan memperhatikan time windows dan kapasitas. Salah satu algoritma yang dapat digunakan untuk menyelesaikan masalah tersebut yaitu algoritma genetika. Algoritma genetika merupakan suatu proses optimasi yang dikembangkan berdasarkan prinsip genetika dan proses seleksi alam. Penyelesaian permasalahan menggunakan algoritma genetika diawali dengan pembangkitan populasi awal, setelah itu proses evaluasi nilai fitness dari masing-masing individu. Selanjutnya akan dipilih induk secara acak melalui tahap seleksi. Dalam penelitian ini digunakan 2 metode seleksi yaitu roulette wheel selection dan seleksi turnamen. Setelah dipilih dua induk, selanjutnya dilakukan proses pindah silang dengan metode order crossover dan mutasi dengan metode swapping mutation dengan data yang digunakan diperoleh dari Bulog Divisi Regional Yogyakarta. Dari hasil percobaan yang telah dilakukan dengan bantuan software Matlab, untuk metode roulette wheel selection diperoleh total waktu pendistribusian selama 783 menit, sedangkan untuk metode seleksi turnamen diperoleh total waktu pendistribusian selama 772 menit. Dengan demikian dapat disimpulkan bahwa kedua metode seleksi memberikan solusi yang relatif sama, sehingga dalam penelitian ini metode seleksi tidak terlalu berpengaruh pada solusi yang dihasilkan.
Kata kunci : Capacitated vehicle routing problem with time windows (CVRPTW), algoritma genetika, roulette wheel selection, seleksi turnamen
vii
KATA PENGANTAR
Puji syukur penulis panjatkan kehadirat Allah SWT yang telah melimpahkan
rahmat
serta
hidayah-Nya,
sehingga
penulis
dapat
menyelesaikan tugas akhir skripsi ini dengan judul βImplementasi Algoritma Genetika dengan Variasi Seleksi dalam Penyelesaian Capacitated Vehicle Routing Problem with Time Windows (CVRPTW) untuk Optimasi Rute Pendistribusian Raskin di Kota Yogyakartaβ. Tujuan dari penulisan skripsi ini guna memenuhi salah satu syarat dalam memperoleh gelar Sarjana Sains (S.Si) pada Program Studi (Prodi) Matematika. Penulis menyadari bahwa penyusunan skripsi ini tidak lepas dari bimbingan, arahan, bantuan serta motivasi dari berbagai pihak. Oleh karena itu, penulis mengucapkan terima kasih yang sebesar-besarnya kepada: 1. Bapak Dr. Hartono selaku Dekan Fakultas Matematika dan Ilmu Pengetahuan Alam 2. Bapak Ali Mahmudi, S.Pd., M.Pd. selaku Ketua Jurusan Pendidikan Matematika 3. Bapak Dr. Agus Maman Abadi selaku Ketua Program Studi Matematika 4. Ibu Fitriana Yuli S., M.Si. selaku Dosen Pembimbing Skripsi yang telah meluangkan waktu, memberikan arahan, motivasi serta saran kepada penulis 5. Ibu Dwi Lestari S.Si., M.Sc. selaku Dosen Pembimbing Akademik yang senantiasa memberikan motivasi 6. Seluruh Bapak/Ibu Dosen Jurusan Pendidikan Matematika yang telah memberikan banyak ilmu yang bermanfaat 7. Bapak Sumaryo dan Ibu Kiryati serta kakak dan adikku yang telah memberikan doa, perhatian, dukungan, serta semangat yang tiada hentinya kepada penulis 8. Semua pihak yang tidak dapat disebutkan satu-persatu, yang telah berperan serta membantu dalam pembuatan tugas akhir skripsi ini viii
Penulis menyadari bahwa tugas akhir skripsi ini masih jauh dari sempurna, oleh karena itu penulis mengharapkan kritik dan saran yang sekiranya dapat membangun. Semoga skripsi ini dapat bermanfaat bagi penyusun maupun pihak lain yang menggunakannya. Demikian yang dapat penulis sampaikan, atas motivasi dan dukungan yang telah diberikan kepada penulis, penulis mengucapkan terimakasih. Yogyakarta, 5 April 2017 Penulis
Yan Anisa Dewi NIM. 13305141046
ix
DAFTAR ISI HALAMAN JUDUL................................................................................................ i HALAMAN PERSETUJUAN ................................................................................ ii HALAMAN PENGESAHAN ................................................................................ iii HALAMAN PERNYATAAN ............................................................................... iv HALAMAN MOTTO ..............................................................................................v HALAMAN PERSEMBAHAN ............................................................................ vi ABSTRAK ............................................................................................................ vii KATA PENGANTAR ......................................................................................... viii DAFTAR ISI ............................................................................................................x DAFTAR TABEL ................................................................................................ xiii DAFTAR GAMBAR ........................................................................................... xiv DAFTAR LAMPIRAN ..........................................................................................xv DAFTAR SIMBOL.............................................................................................. xvi
BAB I PENDAHULUAN A. Latar Belakang Masalah .................................................................................1 B. Identifikasi Masalah .......................................................................................7 C. Batasan Masalah .............................................................................................8 D. Rumusan Masalah...........................................................................................8 E. Tujuan Penelitian ............................................................................................8 F. Manfaat Penelitian ..........................................................................................9 BAB II KAJIAN PUSTAKA A. Graf ...............................................................................................................10 1. Definisi Graf...............................................................................................10 2. Jenis-Jenis Graf ..........................................................................................10 3. Keterhubungan ...........................................................................................12 B. Vehicle Routing Problem (VRP) ..................................................................14 C. Capacitated Vehicle Problem with Time Windows (CVRPTW) ..................16 1. Formulasi CVRPTW ..................................................................................16 x
D. Algoritma Genetika ......................................................................................19 1. Pengertian Algoritma Genetika ................................................................19 2. Karakteristik Algoritma Genetika.............................................................21 3. Langkah Optimasi dalam Algoritma Genetika .........................................23 4. Komponen dalam Algoritma Genetika .....................................................25 a. Teknik Pengkodean ............................................................................26 b. Membangkitkan Populasi Awal (Spanning) .......................................26 c. Evaluasi Nilai Fitness (Fitness Value) ...............................................27 d. Seleksi .................................................................................................28 1) Roulette Wheel Selection ..............................................................29 2) Seleksi Turnamen .........................................................................32 e. Pindah Silang (Crossover) ..................................................................34 f. Mutasi (Mutation) ...............................................................................37 g. Elitism .................................................................................................39 h. Pembentukan Populasi Baru ...............................................................39 E. Teknik Penarikan Kesimpulan......................................................................40 F. Penelitian yang Relevan ...............................................................................40 BAB III PEMBAHASAN A. Model Matematika CVRPTW pada Pendistribusian Raskin di Kota Yogyakarta ...................................................................................................42 B. Penyelesaian Masalah CVRPTW pada Pendistribusian Raskin di Kota Yogyakarta ...................................................................................................46 1.
Penyandian Gen (Pengkodean) ................................................................49
2.
Membangkitkan Populasi Awal (Spanning) ............................................50
3.
Evaluasi Nilai Fitnes (Fitness Value) ......................................................52
4.
Seleksi (Selection) ....................................................................................54 a. Roulette Wheel Selection .....................................................................54 b. Seleksi Turnamen .................................................................................54
5.
Pindah Silang (Crossover) .......................................................................55
6.
Mutasi (Mutation) ....................................................................................56
xi
7.
Pembentukan Populasi Baru ....................................................................58
C. Teknik Penarikan Kesimpulan......................................................................61 D. Perbandingan Rute Menggunakan Algoritma Genetika dengan Variasi Seleksi ...........................................................................................................72 BAB IV PENUTUP A. Kesimpulan ...................................................................................................74 B. Saran .............................................................................................................77 DAFTAR PUSTAKA ...........................................................................................78 LAMPIRAN ..........................................................................................................81
xii
DAFTAR TABEL Tabel 2.1 Pemetaan Proses Alamiah ke Proses Komputasi ...................................21 Tabel 2.2 Contoh Populasi Beserta Nilai Fitnessnya .............................................31 Tabel 2.3 Nilai Probabilitas dan Segmen untuk Masing-masing Kromosom ........31 Tabel 2.4 Hasil Kromosom yang Terpilih..............................................................32 Tabel 3.1 Representasi Gen....................................................................................49 Tabel 3.2 Pembagian Rute .....................................................................................51 Tabel 3.3 Nilai Fitness Generasi Awal ..................................................................52 Tabel 3.4 Hasil Percobaan......................................................................................59 Tabel 3.5 Test of Normality ...................................................................................62 Tabel 3.6 ANOVA .................................................................................................63 Tabel 3.7 Independent Sample Test .......................................................................64 Tabel 3.8 Pembagian Rute Metode Roulette Wheel Selection ...............................66 Tabel 3.9 Pembagian Rute Metode Seleksi Turnamen ..........................................69 Tabel 3.10 Perbandingan Rute yang Diperoleh dengan Variasi Seleksi ................72 Tabel 3.11 Total Waktu yang Dibutuhkan Setiap Truk .........................................73
xiii
DAFTAR GAMBAR Gambar 2.1 Graf Tak Berarah dan Graf Berarah ...................................................12 Gambar 2.2 Graf G .................................................................................................13 Gambar 2.3 Bagan Algoritma Genetika menurut Michalewich (1996) .................25 Gambar 2.4 Segmen Masing-masing Kromosom ..................................................32 Gambar 2.5 Mekanisme Seleksi Turnamen ...........................................................33 Gambar 2.6 Sistematika Proses Crossover ............................................................35 Gambar 2.7 Sistematika Proses Mutasi..................................................................38 Gambar 3.1 Peta Gudang Bulog Cupuwatu dan Kelurahan-kelurahan di Kota Yogyakarta .............................................................................................................47 Gambar 3.2 Graf Pendistribusian Raskin di Kota Yogyakarta ..............................48 Gambar 3.3 Grafik Metode Roulette Wheel Selection ...........................................65 Gambar 3.4 Rute Kendaraan Metode Roulette Wheel Selection ............................68 Gambar 3.5 Grafik Metode Seleksi Turnamen ......................................................69 Gambar 3.6 Rute Kendaraan Metode Seleksi Turnamen .......................................71
xiv
DAFTAR LAMPIRAN Lampiran 1 Tabel Data Pendistribusian Raskin di Wilayah Kota Yogyakarta ......81 Lampiran 2 Tabel Matriks Jarak Tempuh dalam Satuan Km ................................82 Lampiran 3 Tabel Waktu Tempuh dan Pelayanan dalam Satuan Menit ................83 Lampiran 4 Prosedur Penyelesaian Algoritma Genetika .......................................84 Lampiran 5 Populasi Generasi Awal......................................................................93 Lampiran 6 Individu Terpilih sebagai Induk .........................................................96 Lampiran 7 Individu Terpilih sebagai Anak ........................................................101 Lampiran 8 Individu Terpilih Hasil Mutasi .........................................................104 Lampiran 9 Populasi Baru....................................................................................107
xv
DAFTAR SIMBOL π, π = simpul/titik distribusi π§π = batas time windows ππ = waktu paling awal melakukan pelayanan (lower bound) ππ = waktu paling lambat melakukan pelayanan (upper bound) πΊ = graf π = vertex/simpul/titik distribusi πΈ = edges/sisi/rusuk ππ = sisi ke- π π£π = simpul ke- π π = banyaknya titik distribusi π = kapasitas truk pengangkut ππ = jumlah permintaan titik distribusi ke- π π π = lama waktu pelayanan titik distribusi ke- π πΎ = banyaknya truk pengangkut π‘ππ = waktu tempuh titik distribusi π ke titik distribusi π π₯πππ = perjalanan dari titik distribusi π ke titik distribusi π oleh kendaraan π πππ = waktu dimulainya pelayanan titik distribusi ke- π π0π = waktu saat kendaraan ke-π meninggalkan depot dan kembali ke depot π ππ = lamanya pelayanan di titik distribusi ke-π oleh kendaraan ke-π πππ = kapasitas total kendaraan ke-π setelah melayani titik distribusi ke-π π = nilai fitness β = nilai dari total waktu pendistribusian dijumlahkan dengan waktu pinalti π = konstanta ππ = nilai fitness titik distribusi ke- π ππ = Probabilitas seleksi pada saat ke-π Ts = tournament size Pc = Probability Crossover πππ = jarak tempuh titik distribusi π ke titik distribusi π
xvi