1
VARIANT ORDER CROSSOVER DAN MUTASI INVERTED DISPLACEMENT DALAM ALGORITMA GENETIKA PADA VEHICLE ROUTING PROBLEM WITH STOCHASTIC DEMANDS Rezha Kharisma Putri1, Sapti Wahyuningsih2, dan Trianingsih Eni Lestari3 Universitas Negeri Malang E-mail:
[email protected] Abstrak: Vehicle routing problem with stochastic demands adalah masalah pencarian rute kendaraan dengan permintaan dari pelanggan baru diketahui ketika kendaraan sampai di tempat pelanggan. Rute dapat diperoleh dengan menggunakan algoritma genetika. Dengan operator mutasi yang sama yaitu inverted displacement akan dibandingkan hasil algoritma genetika pada VRPSD dengan operator order crossover dan operator variant order crossover . Operator variant order crossover memberikan hasil yang lebih optimum dibandingkan dengan . Hal ini dikarenakan pada operator variant order crossover komposisi keturunan yang dihasilkan lebih bervariasi dan mengurangi kemungkinan keturunan identik dengan induknya. Operator mutasi inverted displacement dapat mengeksplor kromosom yang belum muncul dalam populasi. Akan tetapi waktu yang diperlukan pada proses evolusi algoritma genetika cukup lama pada saat evaluasi kromosom. Kata kunci: Vehicle Routing Problem With Stochastic Demands, Algoritma Genetika, Variant Order Crossover , Order Crossover , Mutasi Inverted Displacement Teori graph merupakan salah satu cabang ilmu matematika yang dapat digunakan untuk menyelesaikan permasalahan dalam kehidupan sehari-hari. Salah satu permasalahan yang seringkali diselesaikan melalui pendekatan dengan teori graph adalah masalah pencarian rute kendaraan untuk pendistribusian maupun pengambilan barang. Pencarian rute kendaraan dapat mengoptimalkan jalur-jalur pengiriman sehingga biaya pendistribusian berkurang. Salah satu terapan dari teori graph yang banyak digunakan untuk menyelesaikan permasalahan pencarian rute kendaraan adalah vehicle routing problem with stochastic demansd (vrpsd). VRPSD ini berkembang ketika suatu perusahaan seringkali menggunakan vehicle routing problem secara umum dan mengabaikan kenyataan di lapangan bahwa permintaan dari pelanggan adalah stokastik. Algoritma heuristik yang dapat digunakan untuk menyelesaikan VRPSD adalah algoritma genetika yang pernah ditulis oleh Ismail dan Irhamah (2008b) dalam jurnal Journal of Applied Sciences. Proses evolusi algoritma genetika dipengaruhi oleh operator yang digunakan yaitu operator seleksi, crossover, dan mutasi. Metode pada masingmasing operator telah dikembangkan seperti yang dituliskan oleh Deep dan Mebrahtu 2011b dalam jurnal International Journal of Combinatorial Optimization Problems and Informatics. Deep dan Mebrahtu menemukan tiga , , variasi dari operator order crossover yaitu variant order crossover 1. 2. 3.
Rezha Kharisma Putri adalah mahasiswa jurusan Matematika FMIPA Universitas Negeri Malang Sapti Wahyuningsih adalah dosen jurusan Matematika FMIPA Universitas Negeri Malang Trianingsih Eni Lestari adalah dosen jurusan Matematika FMIPA Universitas Negeri Malang
2
dan . Berdasarkan penelitian tersebut, variant order crossover memberikan hasil lebih optimum dibandingkan operator variant order crossover dan pada permasalahan travelling salesman problem. Selain mengembangkan operator crossover, Deep dan Mebrahtu 2011a juga mengembangkan operator mutasi dengan menggabungkan operator mutasi inversi, displacement, dan exchange. Berdasarkan penelitian tersebut, penggabungan operator mutasi inversi yang menginversi substring dalam kromosom dan displacement yang menyisipkan substring secara acak disebut inverted dispalcement memberikan hasil lebih optimum dibandingkan dengan operator mutasi inversi exchange. Berdasarkan uraian diatas akan dikaji penggunaan variant order crossover dan mutasi inverted displacement dalam algoritma genetika pada vehicle routing problem with stochastic demands. TUJUAN 1. Menganalisa perbandingan operator variant order crossover dengan order crossover dalam algoritma genetika yang digunakan untuk menyelesaikan VRPSD dengan operator mutasi inverted displacement. 2. Menganalisa kelebihan dan kekurangan algoritma genetika dengan operator variant order crossover dan mutasi inverted displacement untuk menyelesaikan VRPSD. HASIL DAN PEMBAHASAN Aldous dan Wilson (2000: 6) mengungkapkan gagasan tentang graph, yaitu diagram yang merepresentasikan titik yang disebut verteks sebagai objek dan garis yang disebut sisi merepresentasikan hubungan antar objek. Graph yang digunakan untuk masalah pencarian rute kendaraan adalah graph komplit yang telah diberi bobot yaitu bilangan yang berasosiasi pada setiap sisi. Graph komplit adalah graph yang setiap dua titik yang berbeda dihubungkan oleh satu sisi (Meng, 2007: 21). Graph komplit berbobot digunakan sebagai model dalam vehicle routing problem with stochastic demands. •
Vehicle Routing Problem with Stochastic Demands Vehicle routing problem with stochastic demands merupakan pengembangan dari model vehicle routing problem dengan penambahan kendala bahwa permintaan pelanggan bersifat stokastik yang nilai pastinya baru diketahui setelah kendaraan sampai di tempat pelanggan. Akan tetapi permintaan pelanggan diasumsikan mengikuti distribusi peluang tertentu berdasarkan perilaku permintaan pelanggan sebelumnya. Dalam artikel ini permintaan pelanggan dibatasi mengikuti distribusi seragam. Ismail dan Irhamah (2008a) menyebutkan ada dua pendekatan berbeda yang digunakan untuk menyelesaikan permasalahan pada VRPSD yaitu pendekatan priori yang merupakan pendekatan yang mengharuskan kendaraan melanjutkan pelayanan sesuai dengan rute yang direncanakan dan pendekatan reoptimazion yang merupakan pendekatan bahwa kendaraan mengunjungi pelanggan yang tersisa yang memungkinkan berbeda dengan rute yang telah ditentukan diawal.
3
Vehicle routing problem with stochastic demands oleh Ismail dan Irhamah (2008b) didefinisikan sebagai graph lengkap = , , . = {0,1,2, . . , !} adalah himpunan titik dengan titik 0 disebut sebagai depot dan titik 1,2, . . , ! sebagai pelanggan. A= { #, $ : #, $ ∈ , # ≠ $} adalah himpunan sisi yang menghubungkan titik. C= {()* : #, $ ∈ , # ≠ $} adalah matriks non-negativ yang berisikan bobot antara titik # dan $. Permintaan pelanggan adalah variabel acak +) , # = 1,2, . . , ! berdistribusi bebas dan diketahui. Permintaan sesungguhnya setiap pelanggan hanya diketahui ketika kendaraan tiba di tempat pelanggan. Asumsikan permintaan pelanggan +) tidak melebihi kapasitas kendaraan , dan mengikuti distribusi peluang diskret -). = /012 +) = 3 , 3 = 0,1,2, . . , 4 ≤ ,. Misalkan 6 = 0,1,2, . . , ! dengan priori tour 0 → 1 → 2. . → $ → $ + 1. . → ! → 0. Ongkos total yang diharapkan dari kendaraan melayani pelanggan ke−$ sampai pelanggan ke−! dan kembali ke depot adalah :* ; memenuhi ? :* ; = <#!#<=<>:* ; , :*@ ; A Dimana :*? ; = (*,*B + ∑.DE :*B ; − 3 -*B ,. + ∑.HEF2 + 2(*B ,G + :*B ; + , − 3 I-*B ,. @ :* ; = (*,J + (J,*B + ∑K .L :*B , − 3 -*B ,. dengan kondisi batas :M ; = (M,J , ; ∈ NM . Persamaan :*? ; adalah ongkos yang diharapkan untuk kondisi kendaraan melanjutkan rute ke titik selanjutnya secara langsung, sedangkan :*@ ; adalah ongkos yang diharapkan untuk kondisi kendaraan kembali ke depot untuk menyetok ulang. Terdapat ambang batas kapasitas ℎ* sedemikian sehingga jika kapasitas kendaraan setelah melayani pelanggan ke−$ melebihi nilai ambang batas ini maka keputusan terbaik adalah melanjutkan proses menuju pelanggan selanjutnya yang telah direncanakan. Tetapi jika tidak maka lebih baik kembali ke depot untuk menyetok ulang. Nilai ambang batas ℎ* adalah nilai terakhir ; sehingga ongkos :*@ . lebih minimum dari ongkos :*? ; . •
ALGORITMA GENETIKA PADA VEHICLE ROUTING PROBLEM WITH STOCHASTIC DEMAND Algoritma genetika adalah pencarian heuristik yang didasarkan atas mekanisme seleksi alam dan evolusi biologis untuk menentukan struktur individu dengan kualitas tinggi dalam populasi. Dengan demikian algoritma genetika merupakan teknik pencarian dan optimasi yang meniru proses evolusi dan perubahan genetika pada struktur kromosom makhluk hidup. Sivanandam (2008: 30) memberikan langkah-langkah dasar dalam proses algoritma genetika yaitu membentuk populasi awal acak yang terdiri dari ! kromosom. Kemudian mengevaluasi nilai fitness setiap kromosom dalam populasi. Membuat populasi baru dengan seleksi, crossover, mutasi, dan menempatkan keturunan baru dalam populasi baru. Mengulang proses pembentukan populasi baru sampai kondisi akhir terpenuhi. Michalewicz dalam Gen dan Cheng (1997: 1) meringkas bahwa algoritma genetika memiliki lima komponen dasar yaitu representasi genetika dari solusi suatu permasalahan, langkah untuk membentuk populasi awal solusi, mengevaluasi fungsi nilai solusi dalam bentuk nilai fitness, operator genetika yang
4
mengubah struktur genetika dari keturunan, dan nilai parameter dalam algoritma genetika. Langkah-langkah menyelesaikan vehicle routing problem with stochastic demands dengan menggunakan algoritma genetika adalah sebagai berikut: 1. Pengkodean Dalam vehicle routing problem with stochastic demands untuk merepresetasikan kromosom digunakan teknik pengkodean permutasi. Setiap kromosom adalah sejumlah bilangan integer yang merepresentasikan posisi dalam sebuah urutan. 2. Inisialisasi Tahap inisialisasi merupakan proses dalam menentukan parameter yang akan digunakan. Jumlah generasi merupakan banyaknya iterasi yang akan digunakan untuk memperoleh solusi. Parameter ini mempengaruhi kestabilan output dan lama iterasi. Ukuran populasi P adalah banyaknya kromosom yang akan digunakan untuk setiap iterasi. Parameter ini mempengaruhi kinerja dan efektivitas algoritma. Jika ukuran populasi terlalu kecil maka aloritma akan lebih cepat konvergen pada satu nilai (Michalewicz, 1996: 72). Probabilitas crossover -Q untuk menunjukkan seberapa sering gen tertentu dari kromosom yang telah terpilih akan melewati crossover. Semakin besar probabilitas crossover maka semakin cepat struktur baru terbentuk. Tetapi jika terlalu besar, fungsi objektivitas yang baik dapat dengan cepat keluar dari populasi. Sedangkan probabilitas crossover yang semakin kecil dapat menghalangi pencarian solusi optimal. De Jong, Grefenstette Schaffer dalam Michalewicz (2004: 293) mengungkapkan nilai probabilitas crossover yang baik berkisar antara 0,60 sampai 0,95. Probabilitas mutasi -R untuk menunjukkan seberapa sering gen tertentu dari kromosom yang telah diproses dengan crossover akan melewati mutasi. Parameter ini bertujuan untuk meningkatkan variasi kromosom dalam populasi. Semakin rendah probabilitas mutasi maka akan menghalangi gen yang berpotensi baik tidak dicoba. Sedangkan semakin tinggi probabilitas maka keturunan akan semakin mirip dengan induk. Schwefel, Wegener, dan Weinert (2003: 126) menuliskan bahwa probabilitas mutasi yang sering direkomendasikan adalah 1/!. Sedangkan Siarry dan Michalewicz (2008: 357) menuliskan probabilitas mutasi yang baik digunakan adalah berkisar antara 0,1% sampai 5%. 3. Membangkitkan Populasi Awal Proses pembentukan populasi awal untuk generasi pertama yang digunakan adalah dengan cara random generator. Langkah yang digunakan adalah membangkitkan bilangan acak sejumlah ukuran kromosom. Kemudian mengurutkan bilangan acak dari yang terkecil sampai yang terbesar. Urutan bilangan acak ini menunjukkan urutan gen dalam kromosom. 4. Evaluasi Pada vehicle routing problem with stochastic demands fungsi tujuannya adalah meminimumkan rute kendaraan. Kromosom terbaik adalah kromosom yang memiliki nilai fitness terkecil. Nilai fitness yang digunakan adalah nilai fungsi objektivitas vehicle routing problem with stochastic demands. Fungsi objektivitas suatu rute adalah :J ; yang diperoleh dari persamaan
5 ?
:* ; = <#!#<=<>:* ; , :*@ ; A Dimana :*? ; = (*,*B + ∑.DE :*B ; − 3 -*B ,. + ∑.HEF2 + 2(*B :*B ; + , − 3 I-*B ,. @ :* ; = (*,J + (J,*B + ∑K .L :*B , − 3 -*B ,. dengan 2 = 0 dan kondisi batas :M ; = (M,J , ; ∈ NM .
,G
+
5. Roulette Wheel Selection Agar hanya kromosom terbaik yang melanjutkan perannya dalam evolusi algoritma genetika maka tahap selanjutnya adalah proses seleksi. Operator seleksi yang digunakan adalah roulette wheel selection. Dalam artikel ini untuk menghitung probabilitas setiap kromosom diterapkan mekanisme penyesuaian normalisasi linear. Mekanisme penyesuaian ini dapat mempertinggi kemampuan kromosom terbaik untuk reproduksi disaat kromosom yang lemah justru mungkin untuk reproduksi turunannya. Parameter yang diperlukan dalam mekanisme penyesuaian normalisasi linear adalah nilai dasar, selang pengurangan, dan nilai minimum. Probabilitas kromosom dengan mekanisme penyesuaian normalisasi linear diperoleh dengan persamaan berikut VWX -. = Y, untuk setiap kromosom 3 = 1,2,3, . . , P Z
Dimana \]^. = 2V − _` ∗ 3 − 1 b dan jika\]^. < < , maka \]^. = <. Menghitung probabilitas kumulatif ;. masing-masing kromosom ;. = ∑.)L -) , untuk setiap kromosom 3 = 1,2,3, . . , P Menentukan individu yang terpilih dalam proses seleksi. Jika ;.d < 0 ≤ ;. maka kromosom ke−3 yang terpilih. 6. Order Crossover dan Variant Order Crossover Proses crossover terlebih dahulu membangkitkan bilangan acak antara 0 dan 1 sebanyak kromosom dalam populasi. Jika nilai bilangan acak kromosom lebih kecil atau sama dengan probabilitas crossover -Q , maka kromosom tersebut akan mengalami proses crossover. Selanjutnya kromosom terpilih akan mengalami proses crossover dengan langkah sebagai berikut. 1. Menentukan dua gen sebagai cut point. 2. Menyalin gen yang berada diantara cut point tersebut ke keturunan dengan posisi yang sama. 3. Mengurutkan gen yang berada pada induk kedua dengan urutan gen yang berada pada posisi setelah cut point kedua diikuti dengan gen yang berada pada posisi sebelum cut point pertama dan diakhiri dengan gen yang berada pada posisi diantara kedua cut point. 4. Kemudian gen yang telah diurutkan tersebut dibandingkan dengan keturunan pertama. Apabila gen tersebut ada pada keturunan pertama maka abaikan gen tersebut dari urutan itu. 5. Kemudian memasukkan urutan yang baru saja didapat pada keturunan dengan cara memasukkan urutan gen pada posisi setelah cut point kedua terlebih dahulu dan sisanya dimasukkan pada posisi sebelum cut point pertama. 6. Mengulangi langkah 3 sampai 5 untuk menghasilkan keturunan kedua.
6
Dalam artikel ini operator crossover yang digunakan adalah order crossover dan variant order crossover . Misalkan kromosom terpilih adalah 1 2 3 4 5 6 7 8 9 dan 4 5 2 1 8 7 6 9 3. Pada order crossover posisi cut point kedua induk adalah sama |4 Induk - = 1 2 3 5 6 7 | 8 9 -k = 4 5 2 |1 8 7 6 | 9 3 Keturunan 1 = 2 1 8 |4 5 6 7 | 9 3 1k = 3 4 5 |1 8 7 6 |9 2 Pada variant order crossover posisi cut point kedua induk berberda Induk - = 1 2 3 | 4 5 6 7 | 8 9 -k = 4 5 |2 1 8 7 | 6 9 3 Keturunan 1 = 2 1 8 | 4 5 6 7 | 9 3 1k = 5 6 |2 1 8 7 | 9 3 4 7. Mutasi Inverted Displacement Pemilihan kromosom yang akan mengalami mutasi dengan membangkitkan bilangan acak antara 0 dan 1 sebanyak kromosom dalam populasi. Jika nilai bilangan acak kromosom lebih kecil atau sama dengan probabilitas mutasi -R , maka kromosom tersebut akan mengalami proses mutasi. Operator mutasi yang digunakan adalah inverted displacement. Operator mutasi ini merupakan penggabungan dari operator mutasi inversi dan displacement. Langkah proses mutasi adalah sebagai berikut. 1. Memilih dua posisi dalam kromosom secara acak, misal diperoleh 4 dan 8. Maka substring pada posisi 4 sampai posisi 8 yaitu 1 4 3 7 8 diinversikan menjadi 8 7 3 4 1. \ l = 5 6 2 |8 7 3 4 1| 9 2. Memasukkan substring yang diperoleh pada langkah 1 ke dalam kromosom secara acak, misal diperoleh 2. Maka substring 8 7 3 4 1 berada pada posisi 2 3 4 5 6. \l = 5 8 7 3 4 1 6 2 9 8. Populasi Baru Pembentukan generasi baru yang digunakan adalah penggantian induk yang lemah. Pada artikel ini induk yang lemah adalah induk dengan nilai fitness terbesar dalam kromosom. 9. Kriteria Terminasi Kondisi algoritma genetika dihentikan dalam artikel ini adalah generasi maksimum. Algoritma genetika berhenti berevolusi jika telah melakukan evolusi sebanyak generasi yang telah ditentukan saat inisialisasi. •
Contoh Vehicle Routing Problem with Stochastic Demands dengan Algoritma Genetika Seorang penjual produk makanan ringan setiap 2 minggu harus mengirim produknya yang telah dipak dalam box kepada 5 pelanggan tetapnya yang berada dalam satu kota. Kendaraan yang digunakan penjual berjumlah 1 dengan kapasitas angkut 20 box. Setiap pelanggan tidak memesan permintaan sebelumnya sehingga penjual baru mengetahui permintaan pelanggan saat penjual sampai ditempat pelanggan tersebut. Akan tetapi penjual memiliki range permintaan pelanggan
7
berdasarkan pada catatan pembelian yang telah dilakukan pelanggan selama 3 bulan terakhir. Perkiraan pembelian pelanggan disajikan dalam Tabel 1 berikut. Tabel 1 Perkiraan Pembelian 5 Pelanggan Pelanggan Catatan pembelian (box) Range permintaan (box) 1 1,4,3,2,2,3 1,2,3,4 2 3,2,5,4,3,4 2,3,4,5 3 4,2,5,1,3,2 1,2,3,4,5 4 3,5,7,5,4,6 3,4,5,6,7 5 0,3,2,2,1,1 0,1,2,3
Jarak antar pelanggan dan pelanggan dengan depot disajikan dalam Tabel 2 berikut. Tabel 2 Jarak Antar 5 Pelanggan dan 5 Pelanggan dengan Depot Node 0 1 2 3 4 5 0 0 15 24 35 10 27 1 15 0 36 12 5 24 2 24 36 0 19 20 29 3 35 12 19 0 15 17 4 10 5 20 15 0 6 5 27 24 29 17 6 0
Langkah awal dalam menyelesaikan permasalah tersebut adalah menentukan distribusi permintaan setiap pelanggan. Dengan menggunakan alat bantu EasyFit diperoleh hasil uji distribusi permintaan kelima pelanggan sebagai berikut: (1) Permintaan pelanggan 1 berdistribusi seragam U 1,4 , peluang pelanggan 1 dikunjungi dengan range permintaan 3 = 1,2,3,4 adalah -. = ; (2) Permintaan pelanggan 2 berdistribusi seragam U 2,5 , peluang pelanggan 2 dikunjungi dengan range permintaan 3 = 2,3,4,5 adalah -. = ; (3) Permintaan pelanggan 3 berdistribusi seragam U 1,5 , peluang pelanggan 3 dikunjungi dengan range permintaan 3 = 1,2,3,4,5 adalah -. = ; (4) Permintaan pelanggan 4 berdistribusi seragam U 3,7 ; (5) peluang pelanggan 4 dikunjungi dengan range permintaan 3 = 3,4,5,6,7 adalah -. = ; (6) Permintaan pelanggan 5 berdistribusi seragam U 0,3 , peluang pelanggan 5 dikunjungi dengan range permintaan 3 = 0,1,2,3 adalah -. = . Setelah distribusi permintaan diketahui, maka permasalahan tersebut diselesaikan dengan algoritma genetika. a) Operator Order Crossover n Penyelesaian permasalahan diatas dengan operator order crossover dalam algoritma genetika menghasilkan fungsi objektivitas minimum 98,425 pada kromosom 4 1 3 5 2. Sehingga rute kendaraan yang minimum adalah 4 1 3 5 2 dengan ambang batas ℎ = 4, ℎ = 1, ℎk = 5, dan ℎ = 10. Dengan demikian rute berawal dari depot dan mengunjungi pelanggan 4. Jika kapasitas kendaraan setelah melayani pelanggan 4 kurang dari atau sama dengan 4 maka kendaraan disarankan kembali ke depot untuk menyetok ulang sebelum melanjutkan melayani pelanggan 2. Tetapi jika kapasitas kendaraan melebihi 4 maka kendaraan dapat langsung melanjutkan ke pelanggan 1. Kendaraan melanjutkan mengunjungi pelanggan sesuai dengan rute yang telah direncanakan beserta masing-masing ambang batas setelah melayani pelanggan. Sampai
8
kendaraan melayani pelanggan terakhir yaitu pelanggan 2. Setelah melayani pelanggan 2 maka kendaraan kembali ke depot. b) Operator Variant Order Crossover Sebagai perbandingan dalam pencarian rute kendaraan permasalahan diatas, dengan populasi awal dan parameter yang sama, akan digunakan operator variant order crossover pada proses evolusi algoritma genetika. Proses evolusi algoritma genetika berjalan sama seperti langkah diatas. Setelah mencapai 5 generasi diperoleh fungsi objektivitas minimum 97,700 pada kromosom 2 5 3 1 4 dengan ambang batas ℎ = 3, ℎ = 0, ℎk = 3, dan ℎ = 8. Selain contoh diatas, telah dikaji studi kasus 6 pelanggan dan 7 pelanggan. Solusi yang diperoleh dari masing-masing kasus disajikan dalam Tabel 3 berikut: Tabel 3 Tabel Ringkasan Solusi Tiga Contoh Kasus No. Kasus Order Crossover -Q 1 5 pelanggan 0,75 Rute yang diperoleh 4 1 3 5 2 dengan ongkos 98,425 2 6 pelanggan 0,70 Rute yang diperoleh 1 2 4 3 5 6 atau 1 2 5 3 4 6 dengan ongkos 38,049 3 7 pelanggan 0,65 Rute yang diperoleh 2 1 3 7 5 6 4 dengan ongkos 57,721
Vaiant Order Crossover Rute yang diperoleh 2 5 3 1 4 dengan ongkos 97,700 Rute yang diperoleh 2 1 4 3 5 dengan ongkos 36,049 Rute yang diperoleh 4 3 2 1 7 6 5 dengan ongkos 57,008
Hasil yang diperoleh dari ketiga permasalahan adalah rute yang merupakan urutan pelanggan yang akan dikunjungi. Ongkos yang dimiliki suatu rute adalah ongkos yang diharapkan dari kendaraan melanjutkan melayani pelanggan dan kendaraan kembali ke depot untuk menyetok ulang. Operator variant order crossover memberikan hasil yang lebih optimum dibandingkan dengan operator order crossover . Hal ini dikarenakan pada operator variant order crossover komposisi keturunan yang dihasilkan dari penyilangan dua induk lebih bervariasi Operator mutasi inverted displacement dapat mengeksplor kromosom sehingga menghasilkan kromosom yang lebih baik dari induknya. Kemampuan operator mutasi inverted displacement dalam mengeksplor kromosom dikarenakan proses mutasi yang dilakukan dengan menginversikan substring kemudian menyisipkannya secara acak. Proses inversi memungkinkan substring yang baik dipertahankan sedangkan proses menyisipkan memungkinkan mengeksplor kromosom yang belum muncul. Penggunaan mekanisme penyesuaian normalisasi linear mempengaruhi pencapaian solusi yang lebih optimum karena hanya kromosom dengan fungsi objektivitas minimum yang berperan dalam proses evolusi crossover dan mutasi. Selain itu, dengan digunakannya penggantian induk yang lemah pada saat pembentukan populasi baru setelah proses evolusi berperan dalam menyimpan kromosom yang baik agar tidak keluar dari populasi dan mengganti kromosom induk yang kurang baik dengan keturunan yang lebih baik. Disisi lain dengan digunakannya algoritma genetika untuk menyelesaikan vehicle routing problem with stochastic demands juga memiliki kekurangan. Kekurangan algoritma genetika ini adalah waktu yang diperlukan cukup kompleks
9
seperti yang dituliskan Shanmugam, Ganesan dan Vanathi (2011). Salah satu proses yang memerlukan waktu cukup kompleks adalah proses evaluasi. Setiap kromosom dalam populasi harus dievaluasi dengan fungsi objektivitas vehicle routing problem with stochastic demands. PENUTUP Kesimpulan Berdasarkan pembahasan dapat disimpulkan bahwa: 1. Berdasarkan kajian yang telah dilakukan, operator variant order crossover memberikan hasil yang lebih optimum dibandingkan dengan operator order crossover . Hal ini dikarenakan keturunan yang dihasilkan lebih bervariasi. 2. Dengan menggunakan algoritma genetika untuk menyelesaikan vehicle routing problem with stochastic demands solusi dapat diperoleh kapanpun dan tidak tunggal. Solusi yang dihasilkan adalah rute yang merupakan urutan pelanggan yang harus dikunjungi. Ongkos yang diharapkan dari rute yang diperoleh adalah ongkos minimum dari kendaraan kembali ke depot dan kendaraan melanjutkan melayani pelanggan. Dengan operator variant order crossover dapat mengurangi kemungkinan kromosom yang dihasilkan identik dengan induknya sedangkan dengan mutasi inverted displacement mengoptimalkan proses eksplorasi kromosom yang akan dihasilkan. Akan tetapi proses evolusi algoritma genetika membutuhkan waktu yang cukup lama. Salah satu proses yang membutuhkan waktu adalah pada saat proses evaluasi kromosom. Semakin banyak titik dan semakin banyak kromosom dalam populasi maka iterasi pada fungsi objektivitas semakin lama. Besarnya kapasitas kendaraan juga mempengaruhi lama iterasi fungsi objektivitas, karena disetiap iterasi kapasitas kendaraan dievaluasi dari kapasitas kendaraan maksimum sampai kapasitas kendaraan minimum atau 0. Saran Agar dapat disimpulkan secara umum variant order crossover lebih optimum dibandingkan order crossover dalam algoritma genetika pada vehicle routing problem with stochastic demands, diperlukan pengkajian lebih lanjut dengan penggunaan metode seleksi tournament, stochastic universal sampling, local selection, dan steady state selection. Selain pengkajian dengan metode seleksi, juga diperlukan pengkajian lebih lanjut dengan operator mutasi insertion, displacement, reciprocal exchange, dan inversi exchange. Untuk mempermudah dan mempercepat proses pencarian solusi disarankan realisasi dalam bentuk perangkat lunak. Sedangkan untuk vehicle routing problem with stochastic demands diperlukan pengkajian jika distribusi permintaan pelanggan heterogen dan selain distribusi seragam serta meningkatkan jumlah pelanggan dan kapasitas kendaraan. DAFTAR RUJUKAN Aldous, Joan & Wilson, Robin J. 2000. Graph and Application. Great Britain : Springer. Deep, Kusum & Mebrahtu, Hadush. 2011a. Combined Mutation Operators of Genetic Algorithm for the Travelling Salesman Problem. International
10
Journal of Combinatorial Optimization Problems and Informatics, (Online), 2 (3): 1-23, (http://ijcopi.org/ojs/index.php?journal=ijcopi&page=article&op=download &path%5B%5D=44&path%5B%5D=80), diakses 20 Januari 2013. Deep, Kusum & Mebrahtu, Hadush. 2011b. New Variants of Order Crossover for Travelling Salesman Problem. International Journal of Combinatorial Optimization Problems and Informatics, (Online), 2 (11): 2-13, (http://ijcopi.org/ojs/index.php?journal=ijcopi&page=article&op=download &path%5B%5D=44&path%5B%5D=80), diakses 20 Januari 2013. Gen, Mitsuo & Cheng, Runwei. 2000. Genetic Algorithms and Engineering Optimization. John Wiley & Sons, Inc. Ismail, Z. & Irhamah. 2008a. Adaptive Permutation-Based Genetic Algorithm for Solving Vehicle Routing Problem with stochastic Demands. Journal of Applied Sciences, (Online), 8 (18): 3228-3234, (http://www.its.ac.id/personal/files/pub/4191-irhamah-statistikapublished_jms243161-167.pdf), diakses tanggal 25 Januari 2012. Ismail, Z. & Irhamah. 2008b. Solving the Vehicle Routing Problem with stochastic Demands via Hybrid Genetic Algorithm-Tabu Search. Journal of Applied Sciences, (Online), 4(3): 161-167, (http://www.its.ac.id/personal/files/pub/4191-irhamah-statistikapublished_jms243161-167.pdf), diakses tanggal 25 Januari 2012. Meng, K.K. Fengming, D. & Guan, T.E. 2007. Introduction to Graph Theory. Singapura: World Scientific. Dari Google Book, (Online), (http://books.google.co.id/books?id=7_bQa4SJTQQC&hl=id), diakses tanggal 20 Januari 2013. Michalewicz, Zbigniew. 1996. Genetic Algorithms+Data Structures=Evolution Programs (3rd rev. & ext. ed). New York: Springer. Dari Google Book, (Online), (http://books.google.co.id/books?id=vlhLAobsK68C&lr=&hl=id), diakses 7 Maret 2013. Michalewicz, Zbigniew & Fogel, David B. 2004. How to Solve It: Modern Heuristic (2nd Ed). Jerman: Springer. Dari Google Book, (Online), (http://books.google.co.id/books?id=RJbV_-JlIUQC&hl=id), diakses 7 Maret 2013. Schwefel, Hans-Paul, Wegener, Ingo & Weinert, Klaus. 2003. Advances in Computational Intelligence: Theory and Practice. New York: Springer. Dari Google Book, (Online), (http://books.google.co.id/books?id=oG5T7Gu0AcC&hl=id), diakses tanggal 7 Maret 2013. Shanmugam, Geetha, Ganesan, Poonthalir & Dr. P.T. Vanathi. 2011. Meta Heuristic Algorithms for Vehicle Routing Problem with Stochastic Demands. Journal of Computer Science, (Online), 7 (4): 533-542, (http://thescipub.com/pdf/10.3844/jcssp.2011.533.542), diakses tanggal 3 April 2013. Siarry, Patrick & Michalewicz, Zbigniew (eds). 2008. Advances in Metaheuristics for Hard Optimization. New York: Springer. Dari Google Book, (Online), (http://books.google.co.id/books?id=TkMR1b-VCR4C&hl=id), diakses tanggal 7 Maret 2013. Sivanandam, S.N. & Deepa, S.N. 2008. Introduction to Genetic Algorithms. Berlin: Springer.
