Penerapan Algoritma Genetika untuk Optimasi Vehicle Routing Problem with Time Window (VRPTW) Studi Kasus Air Minum Kemasan

Jurnal Pengembangan Teknologi Informasi dan Ilmu Komputer Vol. 1, No. 2, Februari 2017, hlm. 100-107

e-ISSN: 2548-964X http://j-ptiik.ub.ac.id

Penerapan Algoritma Genetika untuk Optimasi Vehicle Routing Problem with Time Window (VRPTW) Studi Kasus Air Minum Kemasan Dita Sundarningsih1, Wayan Firdaus Mahmudy, Sutrisno Program Studi Teknik Informatika, Fakultas Ilmu Komputer, Universitas Brawijaya Email: [email protected] Abstrak Salah satu permasalahannya dalam bidang optimasi yaitu penentuan rute distribusi air minum kemasan. Air merupakan salah satu kebutuhan pokok bagi manuasia, sehingga banyak sekali permintaan untuk pemasokan air minum kemasan . Penentuan rute terpendek sangat penting karena pengiriman barang harus dilakukan dengan singkat dan tepat waktu dengan memaksimalkan penggunaan alat transportasi untuk mengurangi biaya transportasi. Vehicle Routing Problem (VRP) cenderung menyelsaikan permasalahan dengan meminimalkan biaya yang direpresentasikan oleh total jarak tempuh dan jumlah kendaraan yang digunakan. Oleh karena itu untuk menyelsaikan masalah lebih tepat menggunkan (Vehicle Routing Problem With Time Window) VRPTW, dengan tujuan menentukan optimasi rute yang dipengaruhi dengan Time window. Time window yang merupakan waktu pelayanan khusus yang disediakan oleh pelanggan. Algoritma Genetika merupakan salah satu algoritma yang dapat diterapkan untuk menyelesaikan Optimasi Distribusi Air Minum Kemasan dengan mendapatkan rute terbaik. Pencarian solusi dilakukan dengan mengkombinasikan kromosom kemudian diproses dengan operator genetika (crossover, mutasi dan seleksi) dengan menginisialisasi parameter genetika (ukuran Populasi, probabilitas crossover, probabilitas mutasi dan jumlah generasi). Dari hasil pengujian diperoleh hasil terbaik dengan nilai fitness tertinggi pada ukuran populasi 100, jumlah generasi 2500 nilai probabilitasi crossover 0,3 dan probabilitas mutasi 0,7. Kata kunci: algoritma genetika, optimasi rute, distibusi, VRPTW, time window Abstract One of the problems in the optimization is determination of distribution of bottled water. Water is one of the basic needs for humans, so a lot of demand for the supply of bottled water from customer. Determination of the shortest route is very important for the delivery of goods to be done with a short and timely to maximize the use of means of transport to reduce transport costs. Vehicle Routing Problem (VRP) tend to solve problem by minimizing the cost of which represented by total mileage and the number of vehicles used. Therefore, to solve the problem more precisely using the Vehicle Routing Problem with Time Windows (VRPTW), with the aim of determining the route optimization that is affected by the Time window. Time window is a special service that is provided by the customer. Genetic Algorithm is one of the algorithms that can be applied to complete the Drinking Water Distribution Optimization Packaging to get the best route. Search for Solutions will do by combining the chromosomes then processed by the genetic operators (crossover, mutation and selection) to initialize the genetic parameters (population size, crossover probability, mutation probability and the number of generations). From the test results obtained the best results with the highest fitness value in population size of 100, the number of generations of 2500 probabilitasi crossover value of 0.3 and mutation probability 0.7. Keywords: genetic algorithm, optimation route, distibution, VRPTW, time window banyak permintaan dari pelanggan untuk pemasokan air minum kemasan. Adanya permintaaan yang cukup banyak dari pelanggan yang tersebar diberbagai titik mengakibatkan

1. PENDAHULUAN Air minum merupakan salah satu kebutuhan pokok bagi manusia, sehingga Fakultas Ilmu Komputer Universitas Brawijaya

100

Jurnal Pengembangan Teknologi Informasi dan Ilmu Komputer

terjadi beberapa kendala dalam distribusi air minum keamasan. Kendala distribusi yang dipengaruhi oleh beberapa faktor yaitu jarak masing-masing pelanggan dan waktu tempuh kendaraan. Kendala ini bisa dikatakan sebagai permasalahan Vehicle Routing Problem (VRP) (Yeun, dkk. 2008; Wati, 2011). Selain adanya kendala waktu tempuh dan jarak terdapat kendalalain yang bisa mempengaruhi optimasa penentuan rute yaitu waktu ketersediaan pelanggan, kapan pelanggan tersebut dapat dilayani. Waktu yang dimiliki oleh masingmasing pelanggan tersebut disebut dengan time window. Penentuan rute kendaraan yang dipengaruhi oleh, jarak , waktu tempuh serta time window dapat dikatan sebagai permasalahan Vehicle Routing Problem with Time Window (VRPTW) (Mahmudy, 2014). Dengan andanya beberapa kendala dalam distribusi sehingga untuk saat ini distribusi Air Minum Kemasan belum dilakukan secara maksimal. Oleh karena itu dibuatlah sistem untuk optimasi penentuan rute distribusi air minum kemasan. Telah terdapat banyak penelitian mengenai pencarian rute transportasi optimal dengan kendala time window dengan menerapkan algoritma genetika. Salah satunya seperti penelitian Suprayogi dan Mahmudy (2015) yang menerapkannya untuk masalah antar jemput jasa pencucian pakaian (laundry). Algoritma Genetika dipilih karena dapat diguankan untuk menyelesaikan masalah optimasi yang kompleks untuk mencari rute paling optimum dengan memeperhatikan jarak tempuh, kepadatan lalu lintas, arah dan lainlain. Sehingga dengan menggunakan Algoritma Genetika diharapkan dapat meningkatan Pelayanan kepada Pelanggan. 2. AIR MINUM KEMASAN Air minum kemasan merupakan air yang diproses dengan standart tertentu sehingga menghasilkan kualitas air yang lebih terstandar dari waktu ke waktu. Dalam proses memiliki syarat dan pengawasan yang jauh lebih ketat. Air minum kemasan ini setelah diolah dan melalui berbagai pengujian selanjutnya dikemas dalam botol yang kemudian dipasarkan ke berbagai pelanggan. Dewasa ini jumlah permintaan air minum kemasan di berbagai daerah terus meningkat, karena dengan menggunakan air minum kemasan lebih praktis Fakultas Ilmu Komputer, Universitas Brawijaya

101

dan mudah. 3. ALGORITMA GENETIKA Algoritma genetika berawal dari himpunan solusi yang dihasilkan secara acak, dari himpunan acak tersebut dihasilkan sebuah populasi. Didalam populasi terdapat Individu yang disebut dengan chromosome, chromosome merupakan representasi dari solusi tersebut. chromosome tersebut berevolusi dalam proses Iterasi yang berkelanjutan, sehingga dihasilkan generasi. Setiap generasi, chromosome akan dievaluasi berdasarkan suatu fungsi evaluasi (Gen dan Cheng, 1997). Setelah dihasilkan beberapa generasi maka algoritma genetika akan konvergen pada chromosome terbaik yang merupakan solusi optimal (Goldberg, 1989). Sebelum algoritma ini diterapkan, harus mengetahui masalah apa yang harus dioptimalkan. Masalah tersebut harus dinyatakan dalam sebuah fungsi tujuan terlebih dahulu, yang disebut dengan fungsi fitness. Jika nilai yang didapatkan semakin besar, maka solusi yang dihasilkan semakin baik. Meskipun awalnya semua nilai fitness yang dihasilkan kemungkinan sangat kecil, hal ini bisa terjadi karena algoritma genetika menghasilkan nilai secara random, namun sebagian nilai fitness tersebut lebih tinggi dari nilai yang lain Adapun ciri-ciri bahwa suatu permasalah dapat diselesaikan dengan menggunakan algoritma genetika adalah (Basuki, 2003): - Memiliki fungsi tujuan optimasi non linear dengan banyak kendala yang juga dalam bentuk non linier. - Mempunyai kemungkinan solusi yang jumlahnya tak terhingga. - Membutuhkan solusi “real time” dalam arti solusi tersebut bisa didapatkan dengan cepat sehingga dapat diimplementasikan untuk permasalahan yang mempunyai perubahan yang cepat. - Mempunyai multi-objective dan multicriteria, sehinggga diperlukan solusi yang dapat diterima oleh semua pihak. Berikut ini merupakan siklus dari algoritma genetika : 1. [Mulai] Membangun opulasi awal secara random sebnayak n chromosome (sesuai dengan permasalahannya) 2. [Fitness] Evaluasi setiap fitness f(x) dari setiap chromosome x pada populasi


3. [Populasi baru] membuat populasi baru hingga didapatan populas baru yang lengkap dengan melakukan langkahlangkah berikut (Obitko, 1998): [Seleksi] Pilih dua chromosome induk dari populasi berdasarkan fitnessnya (semakin besar fitnessnya semakin besar kemungkinan untuk dipilih sebagai induk) [Crossover] Sesuai dengan besarnya kemungkinan crossover, induk yang dipilih disilangkan untuk membentuk anak. Jika tidak ada crossover, maka anak merupakan salinan dari induknya. [Mutasi] sesuai dengan besarnya kemungkinan mutasi, anak akan dimutasi pada setiap posisi pada chromosome [Penerimaan] Penempatan anak baru pada populasi baru. 4. [Ganti] Menggunakan populasi yang baru dibentuk untuk proses algoritma selanjutnya 5. [Tes] jika kondisi akhir terpenuhi, berhenti, dan hasilnya merupaka solusi terbaik dari populasi saat itu. 6. [Ulangi] kembali ke nomer 2 . 2.1. Evaluasi Evaluasi digunakan untuk menghitung nilai fitness pada setiap chromosome. Semakin besar nilai fitness tersebut maka semakin baik chromosome untuk dijadikan kandidat solusi (Mahmudy, 2015). Fitness adalah nilai yang menunjukkan tingkat kesesuaian individu terhadap kriteria yang ingin dicapai. Fitness merupakan fungsi yang dimiliki oleh masing-masing individu untuk menentukan tingkat kesesuaian individu tersebut dengan kriteria yang ingin dicapai (Karas dan Umit. 2011) Nilai fitness ini yang akan dijadikan acuan untuk mendapatkan nilai optimal dalam Algoritma Genetika (Basuki, 2003). Dalam Evolusi natural individu dengan nilai fitness tinggi akan bertahan hidup, sedangkan untuk individu yang mempunyai nilai fitness rendah akan mati.Persamaan yang digunakan untuk menghitung nilai fitness adalah sebagai berikut:

102

Dengan keterangan: adalah jarak tempuh dari titik i ke titik j. P merupakan Penalty apabila customer dilayani diluar jadwal 2.2. Operator Genetika Operator genetika digunakan untuk mengkombinasi (modifikasi) individu dalam aliran populasi untuk mencetak individu pada generasi berikutnya. 2.3. Crossover Crossover merupakan operator AG yang mengkombinasikan dua parent untuk menghasilkan chromosome keturunan . proses kombinasi ini disebut juga dengan proses persilangan. Proses Crossover dilakukan dengan menukarkan nilai gen dari dua parent secara acak. Peluang terjadinya proses crossover pada chromosome parent dalam proses crossover berdasarkan suatu probabilitas yang disebut dengan probabilitas crossover (Pc). Secara umum, mekanisme crossover adalah sebagai berikut: 1. Memilih dua buah Chromosome yang berperan sebagai induk 2. Memilih secara acak posisi dalam chromosome, biasa disebut dengan titik crossover, sehingga masing-masing chromosome induk terpecah menjadi dua segmen. 3. Melakukan pertukaran antar segmen chromosome induk untuk menghasilkan chromosome anak. Contoh proses crossover ditunjukkan pada gambar berikut: 4 3 5 2 6 1 Parent 1 Parent 2

2 1 3 5 4 6

Mapping

2 6 5 4

Protochild 4 3 5 5 4 1 2 1 3 2 6 6 Child 1

6 3 2 5 4 1

Child 2

5 1 3 2 6 4

Gambar 1. Proses Crossover PMX Dimana : ∑

+ ∑

(1)

Fakultas Ilmu Komputer, Universitas Brawijaya

Crossover yang digunakan untuk penelitian


ini yaitu Crossover Partial-Mapped (PMX), yang secara acak memilih satu titik potong dan menukarkan bagian kanan dari setiap induk untuk menghasilkan offspring (anak). 2.4. Mutasi Setelah mengalami proses crossover, pada offspring dapat dilakukan mutasi. Mutasi dilakukan dengan cara melakukan perubahan pada satu gen atau lebih dari individu. Namun tidak semua keturunan dari crossover mengalami mutasi. Banyaknya parent yang mengalam mutasi akan bergantung pada probabiitas mutasi ( ) yang ditentukan. Mutasi berfungsi untuk menggantikan gen yang hilang dari populasi selama seleksi serta menyediakan gen yang tidak ada dalam populasi awal. Sehingga mutasi akan meningkatkan variasi populasi Pada penelitian ini untuk proses mutasi menggunakan repicrocal exchange mutation dengan memilih dua posisi secara random, dengan memilih dua titik acak kemudian menukar nilai gen pada dua titik tersebut. Contoh Mutasi yang dilakukan pada tugas akhir ini dapat dilihat pada Gambar 2. Parent

4 3 5 2 6 1

Child

4 6 5 2 3 1

Gambar 3. Proses Exchange Mutasi

103

Seleksi Elitis Seleksi Elitis merupakan Seleksi yang dilakukan dengan mengambil nilai Fitness tertinggi suatu individu (Wati, 2011). Individu yang terpilih tersebut akan dijadikan kandidat sebagai individu-individu yang akan menjadi generasi selanjutnya. Proses Seleksi Elitis dilakukan secara acak sehingga tidak ada jaminan bahwa Suatu individu yang bernilai fitness tertinggi akan selalu terpilih Seleksi Roulette wheel Seleksi roullete wheel menirukan permainan roulette wheel (roda roullete wheel) dimana masing-masing chromosome menepati potongan lingkaran pada roda roulette wheel secara proposional secara proposional sesuai dengan nilai fitnessnya. Chromosome dengan nilai fitness tinggi akan menepati potongan lingkaran yang lebih besar dibandingkan dengan nilai fitness yang lebih kecil. Berikut adalah tahap-tahap seleksi roulette wheel: - Menghitung niai fitness untuk setiap chromosom - Menghitung total nilai fitness pada populasi - Menghitung nilai probabilitas seleksi pada setiap chromosome - Hitung probabilitas kumulatif untuk setiap chromosome Contoh Seleksi Roulette wheel dapat dilihat pada Gambar 3.

2.5. Seleksi Seleksi merupakan pemilihan Individu terbaik yang akan dijadikan parent untuk generasi selanjutnya (Kuswara, 2003). Tujuannya dilakukan proses seleksi untuk memperoleh solusi terbaik dalam memperoleh individu dengan sifat paling bagus, sehingga perlu dilakukan Seleksi populasi baru dan Reproduksi. Populasi baru tersebut merupakan kandidat solusi yang dipilih pada akhir setiap generasi, yang kemudian dijadikan sebagai populasi generasi berikutnya. Beberapa metode yang digunakan untuk memilih individu yang akan dijadikan parent pada proses seleksi adalah roulette wheel selection, binary tournament dan elitism. Pada tugas akhir ini metode seleksi yang digunakan adalah metode Elitism dan metode roullete wheel.

20%

40%

30%

10%

Gambar 3. Seleksi Roulette wheel 4. METODOLOGI DAN PERANCANGAN SISTEM Pada bab ini dibahas mengenai metode yang digunakan dalam pembuatan Sistem pencarian rute distribusi air minum kemasan dengan Algoritma genetika menggunakan VRPTW. 4.1. Tahap Pembuatan Sistem Tahap-tahap penelitian ini disajikan pada



Gambar 4 berikut:

5.1. Start

Study Literatur

104 Perbandingan Metode Seleksi Roulette wheel dan Metode Seleksi Elitis.

Uji coba pertama dilakukan pengujian metode seleksi elitis dan metode seleksi roulette wheel terhadap perubahan fitness.

Analisa Permasalahan

0.12 Analisa Kebutuhan Sistem

Perancangan Sistem Implementasi Algoritma Genetika

0.1 Nilai Fitness

Pengumpulan Data

0.08 0.06

Uji Coba Sistem

0.04 Evaluasi dan Analisa Hasil

Stop

Gambar 4 Tahap Pembuatan sistem

4.2. Data Penelitian Data yang digunakan untuk penelitian ini merupakan data yang diambil secara random untuk data jarak tempuh. Data mengenai pelanggan (jumlah permintahan dan waktu pelayanan) diambil dari beberapa sample toko yang ada dilapangan. Data yang diambil merupakan data sample toko untuk permintaan dalam satu hari. Data dan jumlah kapasitas angkut kendaraan yang dimiliki oleh distributor ditentukan sebelum melakukan penelitian. 5. PENGUJIAN DAN ANALISIS Untuk mengevaluasi program dilakukan beberapa uji coba antara lain: 1. Uji coba untuk menentukan perbandingan Metode seleksi Elitis dan Roulette wheel 2. Uji Coba untuk menentukan ukuran populasi yang optimal untuk proses algoritma genetika untuk optimasi distribusi air minum kemasan. 3. Uji coba untuk menentukan banyaknya generasi yang optimal untuk proses algoritma genetika optimasi distribusi air minum kemasan. 4. Uji coba untuk mencari kombinas probabilitas mutasi dan probabilitas crossover yang terbaik untuk menyelsaikan permasalahan optimasi distrbusi air minum kemasan. Fakultas Ilmu Komputer, Universitas Brawijaya

1

2

3

4

5

6

7

8

9 10

Gambar 5. Grafik Hasil Uji Coba perbandingan Metode Elitis dan Metode Roulette wheel Data yang digunakan dalam pengujian ini menggunakan 30 data pelanggan toko . Jumlah populasi yang digunakan sebanyak 30 Individu dan 1000 jumlah generasi yang diapakai. Uji coba dilakukan sebanyak 10 kali percobaan dari masing-masing metode seleksi dengan 40 populasi. Hasil percobaan yang telah dilakukan pada system untuk percobaan metode seleksi elitis dan roulette wheel untuk data 1 dapat dilihat pada Grafik pada Gambar 5. Grafik menunjukkan bahwa dengan dilakukan 10 kali percobaan nilai fitness yang dihasilkan dari metode seleksi Elitis cenderung menghasilkan nilai fitness yang lebih stabil dibandingkan dengan metode seleski roulette wheel. Rata-rata nilai fitness seleksi elitis yang diperoleh adalah 0.082945 jauh lebih besar dari pada seleksi menggunakan metode roulette wheel. Dibandingkan dengan hasil uji coba dengan metode seleksi roulette wheel nilai fitness yang dihasilkan sebesar 0,058533 berada dibawah dari percobaan dengan menggunakan metode seleksi Elitis. Dengan hasil percobaan dari metode seleksi akan diketahui metode seleksi mana yang lebih cocok diguankan untuk masalah VRPTW yaitu dengan menggunakan metode seleksi Elitis. 5.2. Hasil dan Analisa Uji Coba Generasi. Percobaan untuk banyaknya generasi dilakukan dengan pelanggan tetap sebanyak 30 dengan parameter yang sama dengan percobaan


seleksi. Banyaknya generasi yang digunakan adalah sebanyak kelipatan 500 mulai dari 500 generasi sampai 3500 generasi. Setiap generasi dilakukan 20 kali uji coba dengan populasi sebanyak 40 populasi, probabilitas crossover dan probabilitas mutasi sebesar 0,2

105 0.11

Nilai Fitness

0.105 0.1

0.095

0.092

0.09

0.09 Nilai Fitness

0.085

0.088

0.08

0.086

20 40 60 80 100120140160180200

0.084

Populasi

0.082 0.08

Gambar 7. Uji Coba Ukuran Populasi 500 1000 1500 2000 2500 3000 3500

generasi Gambar 6. Uji Coba Banyaknya Generasi

Dari Grafik Gambar 6 dapat diketahui bahwa jumlah generasi mempengaruhi hasil dari proses algoritma genetika. Nilai paling rendah diperoleh pada generasi 500 karena algoritma genetika belum melakukan proses genetika secara optimal. Akan tetapi pengujian dengan banyak generasi juga belum bisa dikatakan hasilnya akan menjadi optimal. Selain waktu proses yang lebih lama nilai fitness yang dihasilkan juga belum tentu lebih baik dari generasi yang lebih rendah. Dari percobaan dapat dilihat bahwa pada generasi 2500 hasil nilai fitness mengalami kenaikan yang optimal dengan nilai fitness 0.089443. Dan selanjutnya dari generasi 2500 sampai generasi 3500 tidak terjadi peningkatan ratarata nilai fitness yang signifikan. 5.3

Uji Coba Ukuran Populasi.

Percobaan selanjutnya adalah uji coba ukuran populasi dengan menggunakan 30 Pelanggan dan waktu ketersediaan, waktu kunjungan yang sama. Percobaan ini menggunakan 2000 generasi dan nilai Pc dan Pm adalah 0,2, percobaan dilakukan sebanyak 10 kali.

Hasil uji coba untuk ukuran populasi dapat dilihat pada Gambar 7. Grafik mengalami kenaikan yang signifikan untuk nilai rata-rata fitness dengan percobaan yang dilakukan 10 kali, kenaikan terjadi dimulai dari ukuran 20 Populasi hingga 100 Populasi, dengan nilai fitness 0,101342415, namun pada ukuran populasi 100 sampai dengan ukuran populasi 200 sudah tidak terjadi perubahan yang cukup signifikan dan grafik mulai membentuk garis lurus. Pada ukuran populasi 100 merupakan ukuran populasi yang paling optimal untuk permasalahan VRPTW. Semakin tinggi ukuran populasi dapat memengaruhi nilai fitness yang dihasilkan akan tetapi semakin banyak untuk ukuran populasi maka waktu yang dibutuhkan untuk proses algoritma genetika juga semakian besar. 5.4.

Uji Coba Kombinasi Probabilitas Crossover dan Probabilitas Mutasi.

Uji coba dilakukan terhadap pengaruh probabilitas crossover dan probabilitas mutasi terhadap perubahan nilai fitness yang terjadi. Menggunakan 30 data pelanggan dengan waktu ketersediaan yang sama. Pada data tersebut akan dilakukan pengujian probabilitas crossover dan probabilitas mutasi dengan nilai 0-1. Ukuran populasi yang digunakan sebanyak 40 populasi dengan generasi sebanyak 2000, metode seleksi yang digunakan adalah metode seleksi elitis. Uji coba dilakukan sebanyak 10 kali percobaan pada setiap kombinasi probabilitas crossover dan probabilitas mutase. Hasil uji coba kombinasi probabilitas crossover dan probabilitas mutasi dapat dilihat pada Gambar 8.


106

dihasilkan. Oleh karena itu dapat dikatakan bahwa nilai fitness yang dihasilkan akan lebih bervariasi, sehingga peluang untuk didapatkan individu dengan nilai fitness yang lebih besar juga akan semakin besar juga

0.1 0.098 0.096 0.094 0.092 0.09 0.088 0.086 0.084 0.082 0.08 0.1:0.9

0.2:0.7

0.3:0.7

0.4:0.6

0.5:0.5

0.6:0.4

0.7:0.3

0.8:0.2

6. KESIMPULAN

0.9:0.1

Nilai Fitness


Kombinasi PC : PM Gambar 8. Uji Coba Kombinasi PC:PM

Berdasarkan Gambar 8 rata-rata nilai fitness terbesar terdapat pada kombinasi probabilitas crossover dan probabilitas mutasi 0.3:0.7 dengan nilai rata-rata fitness adalah 0.092169208. Grafik menunjukkan rata-rata nilai fitness semakin ketengah menunjukkan bahwa garis yang terdapat pada grafik semakin memuncak dengan kombinasi probabilitas crossover 0.3 dan probabilitas mutasi 0.7 sebagai puncak tertingginya. Kombinasi probabilitas crossover dan probabilitas mutasi untuk menyelesaikan permasalahan vehicle routing problem with time window adalah 0.3:07. Hal ini sesuai dengan penelitian sebelumnya (Mahmudy, Marian, dan Luong, 2014) yang menyatakan bahwa tingkat crossover yang terlalu besar (dan mutasi kecil) akan menurunkan kemampuan GA untuk mengeksplorasi daerah pencarian. Pada kondisi sebaliknya (tingkat crossover kecil, mutasi besar) akan menurunkan kemampuan GA untuk belajar dari generasi sebelumnya dan tidak mampu untuk mengeksploitasi daerah optimum local. Perubahan nilai fitness yang terjadi berdasarkan kenaikan probabilitas crossover dan probabilitas mutasi terjadi karena semakin seringnya individu tersebut pengalami proses persilangan sehingga variasi individu baru yang dihasilkan semakin banyak. Apabila nilai probabilitas crossover dan mutase besar maka semakin besar pula peluang individu tersebut mengalami proses crossover dan mutasi akan lebih banyak sehingga akan semakin banyak dihasilkan individu-individu baru yang Fakultas Ilmu Komputer, Universitas Brawijaya

Kesimpulan yang dapat diambil dari penelitian ini adalah algoritma genetika dapat diterapkan pada pencarian rute optimal pada disitribusi air minum dengan kendala time window, dengan dilakukan pengujian terhadap hasil data yang telah didapat. Pengujian dilakukan dengan menggunakan operator genetika (PC/PM, jumlah generasi dan jumlah populasi) kemudian dilakukan seleksi sehingga didapatkan nilai fitness terbaik.Seleksi dilakukan dengan menggunakan dua metode yang mana dari salah satu seleksi tersebut dipilih Metode yang menghasilkan nilai fitness yang lebih baik.

Hasil pengujian terhadap sistem optimasi distribusi air mium menggunakan Algoritma Genetika didapatkan bahwa seleksi dengan metode Elitis menghasilkan nilai fitness 0.08294 jauh lebih baik daripada menggunakan seleksi Roulette wheel dengan rata-rata nilai fitness 0.0583. Untuk penggunaan parameter genetika kombinasi probabilitas crossover dan probabilitas mutasi hasil kombinasi terbaik dalam penelitian ini terjadi pada kombinasi probabilitas crossover 0,3 dan probabilitas mutasi 0,7 dengan rata-rata nilai fitness 0,092169208. Nilai suatu fitness dapat dipengaruhi oleh kenaikan probabilitas crossover dan probabilitas mutasi, karena seringanya individu mengalami proses persilangan sehingga terbentuklah individu yang lebih bervariasi dan nilai fitness yang didapatkan juga lebih bervariasi. Pengaruh parameter genetika untuk penggunaan ukuran generasi dan ukuran populasi dapat mempengaruhi hasil optimal pada penelitian ini. Ukuran populasi optimal adalah sebanyak 100 populasi dengan nilai fitness 0,10134215 pada percobaan mulai dari Ukuran populasi 20 sampai 100 ukuran populasi mengalamai perubahan nilai fitness yang cukup signifikan, namun pada ukuran populasi 120 sampai 200 ukuran populasi tidak mengalami kenaikan yang signifikan dan lebih


cenderung membentuk garis lurus. untuk pengaruh banyaknya generasi, semakin banyaknya generasi jelas sangat mempengaruhi hasil optimal yang diperoleh, dari hasil nilai fitnessnya dapat dilihat bahwa ukuran generasi sangat berpengaruh semakin besar generasinya maka semakin besar pula nilai fitness yang didapat, akan tetapi semakin besar banyaknya generasi juga belum tentu akan didapatkan hasil yang optimal. 7. DAFTAR PUSTAKA Basuki, Achmad 2003. Strategi Menggunakan Algoritma Genetika. Politeknik Elektronika Negeri Surabaya PENSITS. Diakses tanggal 25 Februari 2014 Gen, M. dan R. Cheng. 1997. Genetic Algorithm and Engineering Design. John Wile & Sons, Inc. Goldberg. D.E. 1989. Genetic Algorithm in Search, Optimiztion, and Machine Learning. Addison-Weasley Publishing Company, Inc. Mahmudy, W. F. 2014, Improved simulated annealing for optimization of vehicle routing problem with time windows (VRPTW). Kursor, vol. 7, no. 3, pp. 109-116. Mahmudy, W. F. 2015. Dasar-Dasar Algoritma Evolusi. Universitas Brawijaya. Malang. Mahmudy, W. F., Marian, R. M. & Luong, L. H. S. 2014. Hybrid genetic algorithms


107

for part type selection and machine loading problems with alternative production plans in flexible manufacturing system. ECTI Transactions on Computer and Information Technology (ECTI‐CIT). vol. 8, no. 1, pp. 80-93 Obitko, M. 1998. Genetic Algorithms. http://www.obitko.com/tutorials/genetic -algorithms/. Diakses tanggal 4 Maret 201. Karas, I. R. and Umit, A. 2011. A Genetic Algorithm Approach for Findng The Shortest Driving Time On Mobile Devices. Scientific Research and Essays, Vol 6(2), p. 394-405. Setiawan, K. 2003. Paradigma Sistem Cerdas. Banyumedia. Surabaya. Suprayogi, D. A. & Mahmudy, W. F. 2015. Penerapan algoritma genetika traveling salesman problem with time window: Studi kasus rute antar jemput laundry', Jurnal Buana Informatika, vol. 6, no. 2, pp. 121-130. Wati, A. W. 2011. Penerapan Algoritma Genetika Dalam Optimasi Model Dan Simulasi Dari Suatu Sistem. Jurnal Keilmuan Tehnik Industri, vol. 1, no. 4. Yeun, L. C., Ismail, R.W., Omar, K, dan Zirous, M. 2008. Vehicle Routing Problem : Model and solution. Journal of Quality Measurement and Analysis, vol. 4, no. 1, pp. 205-218.

Penerapan Algoritma Genetika untuk Optimasi Vehicle Routing Problem with Time Window (VRPTW) Studi Kasus Air Minum Kemasan

Recommend Documents