Penerapan Algoritma Genetika untuk Optimasi Vehicle Routing Problem with Time Window (VRPTW) Studi Kasus Air Minum Kemasan Dita Sundarnigsih1, Wayan Firdaus Mahmudy, Sutrisno Teknik Informatika, Program Teknologi Informasi dan 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. ABSTRACK
One of the problems in the optimization is is determination 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 which 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 done 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 2500 probabilitasi crossover value of 0.3 and mutation probability 0.7. Keywords: Genetic Algorithm, Optimation route, distibution, VRPTW, time window. tempuh kendaraan. Kendala ini bisa dikatakan sebagai permasalahan Vehicle Routing Problem (VRP) [15]. Selain adanya kenadala waktu tempuh dan jarak terdapat I. PENDAHULUAN kendalalain yang bisa mempengaruhi optimas penentuan
1.1 Latar belakang
Air minum merupakan salah satu kebutuhan pokok bagi manusia, sehingga banyak permintaan dari pelanggan untuk pemasokan air minum kemasan. Adanya permintaaan yang cukup banyak dari pelanggan yang tersebar diberbagai titik mengakibatkan terjadi beberapa kendala dalam distribusi Air Minum Keamasan. Kendala distribusi yang dipengaruhi oleh beberapa factor yaitu jarak masing-masing pelanggan dan waktu
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) [15].
Original Article Sundarningsih, D, Mahmudy, WF & Sutrisno 2015, 'Penerapan algoritma genetika untuk optimasi vehicle routing problem with time window (VRPTW) : Studi kasus air minum kemasan ', DORO: Repository Jurnal Mahasiswa PTIIK Universitas Brawijaya, vol. 5, no. 9.
Dengan andanya beberapa kendala dalam distribusi sehingga untuk saat ini distribusi Air Minum Kemasan belum dilakukan secara maksimal. Oleh karena itu dibuatlah system untuk optimasi penentuan rute distribusi air minum kemasan. Penelitian VRP telah dilakukan sejak akhir tahun 50-an setelah Dantzig dan Ramser memberi penjelasan bahwa masalah tersebut merupakan generalisasi dari Traveling Salesman Problem (TSP) [15]. Pada penelitian Telah terdapat banyak penelitian mengenai pencarian rute transportasi optimal dengan kendala time window dengan menerapkan algoritma genetika. Salah satunya seperti Travelling Salesman Problem dengan kendala time window [12]. Algoritma Genetika karena Algoritma Genetika dapat diguankan untuk menyelesaikan masalah Optimasi yang kompleks untuk mencari rute paling optimum dengan memeperhatikan Jarak tempuh, kepadatan lalu lintas, arah dan lain-lain. Sehingga dengan menggunakan Algoritma Genetika diharapkan dapat meningkatan Pelayanan kepada Pelanggan.
1.2 Rumusan Masalah Berdasarkan latar belakang diatas, maka dapat dirumuskan masalah yang dijadikan objek penelitian untuk skripsi ini adalah sebagai berikut: 1. Bagaimana menerapkan algoritma genetika untuk pencarian rute optimal pada Distribusi Air Minum Dalam Kemasan dengan kendala time window? 2. Bagaimana hasil nilai fitness yang bisa dihasilkan dari Seleksi Elitis dan Roulette wheel? 3. Bagaimana pengaruh parameter genetika probabilitas crossover dan probabilitas mutasi terhadap hasil optimasi Distribusi Air Minum Kemasan? 4. Bagaimana pengaruh penerapan parameter genetika untuk jumlah populasi dan jumlah generasi terhadap hasil optimasi Distribusi Air Minum Kemasan?
1.3 Batasan Masalah Batas Masalah Penelitian ini adalah berikut: 1. Jumlah kendaraan yang digunakan telah ditentukan oleh pihak Distrubusi beserta kapasitas barang yang bisa ditampung oleh masing-masing kendaraan. 2. Kendaraan yang digunakan selalu tersedia dan dapat digunakan 3. Kendaraan berangkat setiap rentang satu jam setelah kendaraan pertama berangkat. 4. Pengantaran barang hanya dilakukan pada satu waktu, menggunakan one day service 5. Setiap pelanggan dikunjungi pada tiap time window masing-masing 6. Kedatangan sebelum time window dikenakan waktu tunggu 7. Kedatangan setelah time window dikenakan waktu penalty dan tidak dilayani
1.4 Tujuan Penelitian 1.
2.
3.
Membantu pihak disribusi Air Minum Kemasan dalam hal mengambil keputusan dan menentukan rute yang optimal untuk mengantarkan barang (Air Minum Kemasan) kepada setiap pelanggan Untuk menerapkan algoritma genetika dalam masalah rute optimal menggunakan Vehicle Routing Problem dengan kendala time window pada Distribusi Air Minum Kemasan. Mengetahui dan mengukur pengaruh operator genetika yang terdiri dari probabilitas crossover, probabilitas mutasi dan jumlah serta jumlah generasi terhadap hasil optimasi rute Distribusi Air Minum Kemasan.
2 TINJAUAN PUSTAKA 2.1 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 dan mudah.
2.2 Vehicle Routing Problem Vehicle Routing Problem (VRP) didefinisikan sebagai masalah untuk menentukan rute optimal kendaraan untuk pendistribusian barang atau jasa ke pelanggan dengan lokasi yang berbeda guna memenuhi permintaan yang telah diketahui, dari satu tempat distribusi atau lebih yang memenuhi beberapa kendala [14] . VRP memiliki tujuan meminimumkan biaya yang direpresentasikan oleh total jarak tenpuh kendaraan-kendaraan yang digunakan untuk melayanai semua pelanggan.
2.3 Vehicle Routing Problem With Time Window Pada penelitian sebelumnya,[6] membahas mengenai permasalahan VRP dengan time window pada masing-masing pelanggan merupakan masalah menentukan rute dalam kendaraan dengan bobot kapasitas kendaraan yang diangkut dari distribusi. VRPTW merupakan masalah penentuan penentuan rute kendaraan dengan biaya minimum untuk melayani seluruh pelanggan dan memenuhi kendala kapasitas kendaraan dengan time windows pada masing-masing pelanggan dan distribusi.
2.4 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 [4]. Setelah dihasilkan beberapa generasi maka algoritma genetika akan konvergen pada chromosome terbaik yang merupakan solusi optimal [5]. 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 [2]: • 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 multi-criteria, sehinggga diperlukan solusi yang dapat diterima oleh semua pihak. Berikut ini merupakan bentuk 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 langkah-langkah berikut [10]. 1. [Seleksi] Pilih dua chromosome induk dari populasi berdasarkan fitnessnya (semakin besar fitnessnya semakin besar kemungkinan untuk dipilih sebagai induk) 2. [Crossover] Sesuai dengan besarnya kemungkinan crossover, induk yang dipilih disilangkan untuk membentuk anak. Jika tidak ada crossover, maka anak merupakan salinan dari induknya. 3. [Mutasi] sesuai dengan besarnya kemungkinan mutasi, anak akan dimutasi pada setiap posisi pada chromosome
4.
4. 5.
6.
[Penerimaan] Penempatan anak baru pada populasi baru. [Ganti] Menggunakan populasi yang baru dibentuk untuk proses algoritma selanjutnya [Tes] jika kondisi akhir terpenuhi, berhenti, dan hasilnya merupaka solusi terbaik dari populasi saat itu. [Ulangi] kembali ke nomer 2 .
2.5 Nilai Fitness Fitness merupakan fungsi yang dimiliki oleh masingmasing individu untuk menentukan tingkat kesesuaian individu tersebut dengan kriteria yang ingin dicapai [7] Nilai fitness ini yang akan dijadikan acuan untuk mendapatkan nilai optimal dalam Algoritma Genetika [2]. 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: =
( )
Dimana : = ∑( ) + ∑() (2.2) Dengan keterangan: adalah jarak tempuh dari titik i ke titik j. P merupakan Penalty apabila customer dilayani diluar jadwal
-
2.6 Evaluasi Evaluasi digunakan untuk menghitung nilai fitness pada setiap chromosome. Semakin besar nilai fitness tersebut maka semakin baik chromosome untuk dijadikan kandidat solusi [8]. Fitness adalah nilai yang menunjukkan tingkat kesesuaian individu terhadap kriteria yang ingin dicapai. Untuk menghitung nilai fitness menggunakan persamaan 2.1 . untuk waktu tempuh dihitung berdasarkan persamaan 2.3. = Keterangan : 1. = jarak titik I ke titik j. 2. = %&'( ! " #$ )(
3.
= waktu tempuh dari titik I ke titik j
2.7 Operator Genetika Operator genetika digunakan untuk mengkombinasi (modifikasi) individu dalam aliran populasi untuk mencetak individu pada generasi berikutnya.
2.7.1 Crossover Crossover merupakan operator AG yang mengkombinasikan dua parent untuk menghasilkan chromosome keturunan . proses kombinasi ini disebut
Original Article Sundarningsih, D, Mahmudy, WF & Sutrisno 2015, 'Penerapan algoritma genetika untuk optimasi vehicle routing problem with time window (VRPTW) : Studi kasus air minum kemasan ', DORO: Repository Jurnal Mahasiswa PTIIK Universitas Brawijaya, vol. 5, no. 9.
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: Parent 1
4
3
5
2
6
1
Parent 2
2
1
3
5
4
6
Mapping
2
6
5
4
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
Protochild
Gambar 1. Proses Crossover PMX
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.7.2 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 2. Proses Exchange Mutasi
2.8 Seleksi Seleksi merupakan pemilihan Individu terbaik yang akan dijadikan parent untuk generasi selanjutnya [11]. 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. 2.8.1 Seleksi Elitis Seleksi Elitis merupakan Seleksi yang dilakukan dengan mengambil nilai Fitness tertinggi suatu Individu [14]. 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 2.8.2 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: o Menghitung niai fitness untuk setiap chromosom o Menghitung total nilai fitness pada populasi o Menghitung nilai probabilitas seleksi pada setiap chromosome o Hitung probabilitas kumulatif untuk setiap chromosome Contoh Seleksi Roulette wheel dapat dilihat pada gambar 3. 20%
40%
30%
10%
yaitu fungsi Representasi chromosome, crossover, mutasi, dan menghitung nilai fitness.Proses perancangannya ditunjukkan pada gambar 4. Gambar 3. Seleksi Roulette wheel
3. 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. Tahap-tahapnya adalah seperti pada Gambar 4 berikut:
Gambar 5 Proses Algoritma genetika
4. IMPLEMENTASI
Gambar 4 Tahap Pembuatan system
3.1 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.
Implementasi antar muka pada Optimasi penentuan rute Air Minum Kemasan Vehicle Routing Problem with Time Window (VRPTW) dengan algoritma genetika terdiri dari dua halaman utama yang terdiri dari halaman input dan hasil dari proses perhitungan algoritma genetika. Halaman pertama berfungsi untuk menjalankan proses Algoritma genetika dengan menginputkan beberapa parameter Algoritam genetika. Pada halaman utama ini juga telah ditunjukkan hasil dari proses algoritma genetika yaitu hasil seleksi generasi akhir, hasil Chromosome terbaik. Gambar 5 merupakan Implementasi antar muka
3.2 Perancangan Sistem Proses Optimasi Distribusi Air Minum Kemasan dengan menggunakan Algoritma genetika. Proses yang akan dibahas dalam algoritma genetika terdiri dari beberapa fungsi
Gambar 6. Tampilan Halaman Menu Utama
Original Article Sundarningsih, D, Mahmudy, WF & Sutrisno 2015, 'Penerapan algoritma genetika untuk optimasi vehicle routing problem with time window (VRPTW) : Studi kasus air minum kemasan ', DORO: Repository Jurnal Mahasiswa PTIIK Universitas Brawijaya, vol. 5, no. 9.
Pada halaman kedua menampilkan hasil perhitungan manual dari masing-masing chromosome, menampilkan detail waktu layanan, jarak tempuh dan penalty. Gambar 6 merupakan implementasi user interface hasil perhitungan manual algoritma genetika.
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 masingmasing 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 8. 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.
Gambar 7. Tampilan Halaman Perhitungan Manual
5. PENGUJIAN DAN ANALISA 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.
5.2 Hasil dan Analisa Uji Coba Generasi. Percobaan untuk Ukuran generasi dilakukan dengan pelanggan tetap sebanyak 30 dengan parameter yang sama dengan percobaan seleksi. Banyak 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
5.1 Hasil dan Analisa Uji Coba 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. 0.12
Nilai Fitness
0.1
0.08
0.06
0.04 1 Elitis
2
3
4
5
6
7
8
9
10
0.0794 0.0798 0.081 0.0803 0.0812 0.1015 0.0767 0.085 0.0825 0.082
Roullete wheel 0.052 0.0572 0.0479 0.0671 0.0628 0.0523 0.0603 0.0532 0.0694 0.0631
Gambar 8. Grafik Hasil Uji Coba perbandingan Metode Elitis dan Metode Roulette wheel
0.092 0.089443933
Nilai Fitness
0.09
0.089974441 0.090162952
0.088 0.086
0.084948938
0.084
0.085780397 0.085083155
0.083950048
0.082 0.08 500
1000
1500
2000
2500
3000
3500
Jumlah generasi Gambar 9. Grafik Hasil Uji Coba jumlah generasi
Dari Grafik Gambar 9 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 rata-rata nilai fitness yang signifikan.
5.3 Hasil dan Analisa Uji Coba Ukuran Populasi. Percobaan selanjutnya adalah uji coba banyaknya populasi dengan menggunakan 30 Pelanggan dan waktu ketersediaan, waktu kunjungan yang sama.
Untuk banyaknya generasi 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 10. 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.
0.11 0.105 Nilai Fitness
0.101342415
0.101725485 0.101779075 0.101351557 0.101657548 0.101854465
0.1
0.097205187 0.095 Fitness 0.09 0.086141461 0.086187116
0.085 0.085673811
Original Article 0.08 Sundarningsih, D, Mahmudy, WF algoritma 20& Sutrisno 40 2015, 60 'Penerapan 80 100 120 genetika 140 untuk 160 optimasi 180 vehicle 200 routing problem with Populasi time window (VRPTW) : Studi kasus air minum kemasan ', DORO: Repository Jurnal Mahasiswa PTIIK Universitas Brawijaya, vol. 5, no. 9. Gambar 10. Grafik Hasil Uji coba Ukuran Populasi
menyelesaikan permasalahan vehicle routing problem with time window adalah 0.3:07. Hal ini sesuai dengan penelitian sebelumnya [9] 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 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
5.4 Hasil dan Analisa 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. Jumlah populasi yang digunakan sebanyak 40 populasi dengan jumlah generasi sebanyak 2000 generasi, 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 grafik Gambar 11
.
0.1 0.098 0.096
Nilai Fitness
0.094
0.092169208
0.09186445
0.092 0.09
0.087889466
0.088 0.086
0.0887212
0.086213455 0.084951249 0.086413432
0.084 0.082
0.083973768 0.081706246
0.08 0.9:0.1 0.8:0.2 0.7:0.3 0.6:0.4 0.5:0.5 0.4:0.6 0.3:0.7 0.2:0.7 0.1:0.9 Kombinasi PC : PM Gambar 11. Grafik Hasil Uji Coba Kombinasi Probabilitas Crossover dan Probabilitas Mutasi
Berdasarkan grafik Gambar 11 rata-rata nilai fitness terbesar terdapat pada kombinasi probabilitas crossover dan probabilitas mutasi 0.3:0.7 dengan nilai ratarata fitness adalah 0.092169208. Grafik menunjukkan ratarata 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
6. PENUTUP 6.1 Kesimpulan Kesimpulan yang dapat diambil dari penelitian ini adalah: 1. 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
2.
3.
4.
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.
6.2 SARAN Aplikasi ini dapat dikembangkan dengan penambahan faktor yang mempengaruhi pelayanan dan waktu, jarak tempuh perjalanan pada pelanggan dan bisa dikembangkan dengan menggunakan metode dan parameter genetika yang lainnya serta menggunakan data yang dapat mempengaruhi kapasitas dan pelayanan kendaraan.
REFERESI [1] Amini, S., Javanshir, H., & Tavakkoli-Moghaddam, R. (2010). A Pso Approach for Solving VRPTW with Rela Case Study. IJRRAS. [2] Basuki, Achmad 2003. Strategi Menggunakan Algoritma Genetika. Politeknik Elektronika Negeri Surabaya PENS-ITS. Diakses tanggal 25 Februari 2014 [3] Ciptayani, PI, Mahmudy, WF & Widodo, AW 2009, 'Penerapan algoritma genetika untuk kompresi citra fraktal', Jurnal Ilmu Komputer, vol. 2, no. 1, April, pp. 1-9. [4] Gen, M. dan R. Cheng. 1997. Genetic Algorithm and Engineering Design. John Wile & Sons, Inc. [5] Goldberg. D.E. 1989. Genetic Algorithm in Search, Optimiztion, and MachineLearning. Addison-Weasley Publishing Company, Inc. [6] Harmerita.2007. Vehicle Routing Problem dengan Time Window pada Customer. [7] Karas, Ismail Rakip and Atila Umit. 2011. A Genetic Algorithm Approach For Findng The Shortest Driving Time On Mobile Devices. Scientific Research and Essays Vol 6(2), p. 394-405. [8] Mahmudy, Wayan Firdaus. 2013. Algoritma Evolusi. Universitas Brawijaya. Malang. [9] Mahmudy, WF, Marian, RM & Luong, LHS 2014. 'Hybrid genetic algorithms 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 [10] Obitko, Marek. 1998. Genetic Algorithms. http://www.obitko.com/tutorials/genetic-algorithms/. Diakses tanggal 4 Maret 2014. [11] Setiawan, Kuswara. 2003. Paradigma Sistem Cerdas.
Banyumedia. Surabaya. [12] Saputro, Rio. W.2009. Travelling Salesman Problem dengan Kendala Time Window pada Perusahaan Jasa Pengantar Barang Menggunakan Algoritma Genetika. [13] Solomon, M. M., Larsen, J., Kallehauge, B., & Madsen, O.B. (2005). Vehicle Routing Problem with Time Windows. Dalam G. Desaulniers, J. Desroisiers, & M.S.Marius, Column generation. Springer Science + Bussiness [14] Wati, Anastasia Widya. 2011. “Penerapan Algoritma Genetika Dalam Optimasi Model Dan Simulasi Dari Suatu Sistem.” Jurnal Keilmuan Tehnik Industri 1: 4. [15] Yeun, L.C., Ismail, R.W., Omar, K, & Zirous, M. (2008). Vehicle Routing Problem : Model and solution Journal of Quality Measurement and Analysis, 205218. [16] Yulius, Rina.2008. Seleksi Pada Algoritma Genetika.( http://yuriena.wordpress.com/2010/08/24/72/) .[27 November 2014]
Original Article Sundarningsih, D, Mahmudy, WF & Sutrisno 2015, 'Penerapan algoritma genetika untuk optimasi vehicle routing problem with time window (VRPTW) : Studi kasus air minum kemasan ', DORO: Repository Jurnal Mahasiswa PTIIK Universitas Brawijaya, vol. 5, no. 9.
Pernyataan Penulis Naskah ini dikirimkan untuk keperluan repository skripsi mahasiswa di Program Teknologi Informasi dan Ilmu Komputer, Universitas Brawijaya dan tidak melalui proses evaluasi oleh reviewer seperti layaknya naskah jurnal ilmiah.
