IMPLEMENTASI ALGORITMA GENETIKA HYBRID (BEST IMPROVEMENT SEARCH) PADA VEHICLE ROUTING PROBLEM WITH TIME WINDOW
Fitria Dwi Rosi, Purwanto, dan Mohammad Yasin Universitas Negeri Malang ABSTRAK: Vehicle Routing Problem With Time Window (VRPTW) pengembangan dari Vehicle Routing Problem (VRP) mencari rute dan jumlah kendaraan dengan kendala kapasitas dan waktu pelayanan. Algoritma genetika hybrid merupakan gabungan dari algoritma genetika dan local search (best improvement search). Dari uji coba yang dilakukan solusi yang dihasilkan algoritma genetika hybrid sama atau lebih baik daripada algoritma genetika dan metode-metode heuristicseperti nearest insertion heuristic. Hal ini dipengaruhi oleh adanya local search. Solusi dari local search akan lebih baik jika pada langkah awal telah ditemukan nilai fitness yang lebih baik dari sebelumnya. Dalam skripsi ini dapat dilihat bahwa algoritma genetika hybrid dapat digunakan untuk menyelesaikan masalah VRPTW, dimana solusi yang diberikan tidak tunggal dengan jarak tempuh yang sama. Selanjutnya, agar lebih mudah dalam menyelesaikan permasalahanVRPTW, algoritma genetika hybrid (best improvement search) direpresentasikan dalam program komputer menggunakan Borland Delphi 7. Akan tetapi, terdapat kelemahan program yaitu beberapa parameter yang harus diperhatikan, diantaranya banyaknya populasi yang digunakan dan generasi yang mempengaruhi lamanya iterasi Kata kunci : Graph, Vehicle Routing Problem (VRP), Vehicle Routing Problem With Time Window (VRPTW), Algoritma Genetika Hybrid, Best Improvement Search Permasalahan pengangkutan dan pengiriman barang dapat dimodelkan dalam suatu graph. Sisi pada graph merepresentasikan jalur antar konsumen dan titik-titik dalam graph sebagai produsen dan konsumen. Istilah produsen dalam graph dikenal dengan depot. Sedangkan istilah konsumen dalam graph dikenal dengan customer. Secara lebih khusus permasalahan pengangkutan dan pengiriman barang dapat dikelompokkan sebagai permasalahan Vehicle Routing Problem (VRP). MasalahVRP merupakan permasalahan untuk mencari sejumlah rute minimum dimana setiap customer dilayani tepat satu kali yang berawal dan berakhir di depot. Jumlah kendaraan dalam permasalahan ini diasumsikan selalu tersedia sejumlah rute yang terbentuk. Salah satu pengembangan Vehicle RoutingProblem ini adalah dengan menambahkan batasan waktu dan kapasitas angkutan dalam pendistribusian barang. Pengembangan VRP ini biasanya dikenal dengan nama Vehicle Routing ProblemWith Time Window(VRPTW). Model jaringan Vehicle Routing Problem With Time Window ini dapat digunakan untuk mencari jalur terpendek pendistribusian barang dengan batasan waktu pengiriman serta kapasitas angkutan.
Algoritma genetika hybrid merupakan kombinasi metode-metode heuristik lain ke dalam algoritma genetikadengan harapan mampu meningkatkan kinerja algoritma genetika (Syarif, Wamiliana & Junaidi. 2007). Pada prinsipnya hibridisasi ini diharapkan mampu memberikan solusi lain yang lebih baik disekitar lokal optimum yang diberikan oleh algoritma genetika atau dikenal dengan istilah (local search). Algoritma genetika hybrid menggunakan fungsi random sehingga menyebabkan algoritma genetika hybrid menjadi suatu algoritma berbasis komputer.Best Improvement Local Search adalah memperhatikan semua solusi tepat diantara semua lingkungan solusi. Dan mengambil solusi yang paling baik diantara semua rute. Untuk mempermudah penyelesaian VRPTW dengan Algoritma Genetika Hybrid digunakan alat bantu program yaitu Borland Delphi 7. PembahasanAlgoritma Genetika Hybrid untuk Vehicle Routing ProblemWith Time Window(VRPTW) Algoritma genetika hybrid merupakan gabungan dari algoritma genetika dengan pencarian lokal (local search) yaitu best improvement search untuk menghasilkan solusi yang lebih optimal. Penyelesaian permasalahan VRPTW dengan menggunakan Algoritma genetika hybrid melalui beberapa langkah. Berikut langkah-langkah algoritma genetika hybrid yang dapat menyelesaikan permasalahan VRPTW. 1. Penginisialisasian populasi dengan merepresentasikan tiap store atau kota dalam titik. Salah satu cara dalam menghasilkan populasi awal acak adalah dengan menggunakan permutasi josephus. Misalkan ada 7 kota, permutasi dapat dilakukan dengan menentukan titik awal dan selang. Misalkan titik awal adalah 3 dan selang adalah 2. Maka lintasan berangkat dari kota 3 selang 2 dari kota 3 adalah kota 5 ( dengan asumsi bahwa kota 1 sampai kota 7 membentuk sirkularlist ). Kota 5 dihapus dari daftar , selang 2 dari kota 5 adalah kota 7. Proses ini diulang hingga terdapat satu lintasan dalam daftar yang memuat semua titik. Hasil dari permutasi ini adalah 3 5 7 2 4 6 1. 2. Validasi order tiap rute untuk memperoleh banyaknya kendaraan yang digunakan dalam tiap rute. 3. Mengevaluasi fungsi fitness dari tiap populasi. Untuk mengevaluasi kromosom-kromosom digunakan fungsi fitness yang merupakan fungsi obyektif dari jumlah jarak terpendek dari jumlah yang ada R
(Fv). Fvi =
∑f
x
, dimana R adalah jumlah rute yang terbentuk
x =1
4.
n −1 f x = ∑ jarak ( c a − c a + 1 ) + jarak ( c n − c 1 ) a =1 Pilih sesuai dengan n individu terbaik dan masing-masing rute (individu) akan dilocal search (Best Improvement Local Search) dan pada akhir proses akan dibentuk sekumpulan rute (populasi) baru. Best Improvement Local Search adalah memperhatikan semua solusi tepat diantara semua lingkungan solusi. Dan mengambil solusi yang paling baik diantara semua rute.
5. 6.
7.
8. 9.
Validasi kendala waktu untuk memperoleh waktu yang dibutuhkan tiap rute per kendaraannya. Menyeleksi dengan seleksi roullete wheel. Seleksi yang digunakan untuk memilih individu-individu mana saja yang akan dipilih untuk proses kawin silang dan mutasi. Seleksi digunakan untuk mendapatkan calon induk yang baik. “induk yang baik menghasilkan keturunan yang baik”. Semakin tinggi nilai fitness suatu individu semakin besar kemungkinannya untuk terpilih. Lakukan crossover dan mutasi pada individu-individu tersebut sehingga diperoleh rute baru serta validasi rute baru tersebut, dan dilakukan local search, serta hitung nilai fitness-nya. Crossover bekerja pada pasangan solusi dan penyusunan ulang (recombines) yang menghasilkan satu kromosom. Fungsi crossover bergantung pada data yang disajikan. Pada dasarnya crossover bekerja dengan menukar sebagian gen pada kromosom satu ke kromosom yang lain yang menghasilkan kromosom yang berbeda. Berikut adalah beberapa operator crossover untuk representasi permutasi adalah metode simple random crossover, pindah silang satu titik, unifom crossover, order crossover.Adapun mengenai probabilitas crossover yang baik, dari hasil penelitian yang dilakukan oleh Zbiniew Michalewics (1996) menyatakan bahwa probabilitas crossover yang baik berada dalam range 0.65 sampai dengan 1. Operator ini digunakan untuk memodifikasi suatu kromosom agar menghasilkan perubahan kromosom yang random. Cara sederhana dalam melakukan mutasi ini adalah dengan mengubah satu atau lebih gen dalam kromosom. Fungsi mutasi adalah mengganti gen yang hilang pada proses seleksi dan menyediakan gen yang tidak terdapat pada populasi awal. Tingkat mutasi awal Pm didefinisikan sebagai prosentase dari jumlah gen dalam populasi. Tingkat mutasi mengontrol tingkat-tingkat gen yang dimodifikasi. Jika tingkat mutasi rendah, banyak gen yang tidak dicoba. Berikut adalah beberapa operator mutasi untuk representasi permutasi adalah metode inversion mutation, insertion mutation, Displacement Mutation dan rechiprocal exchange mutation. Adapun mengenai probabilitas mutasi yang baik, dari hasil penelitian yang dilakukan oleh Zbiniew Michalewics (1996) menyatakan bahwa probabilitas mutasi yang baik adalah yang berada pada range 0.01 sampai dengan 0.3. Keturunan-keturunan yang berupa rute-rute baru dan rute lama tersebut diurutkan berdasarkan fungsi fitness-nya. Kemudian rute-rute dengan fungsi fitness terbaik tersebut dievaluasi jaraknya. Jika sudah memenuhi semua kendala dalam VRPTW dipilih n rute terbaik.
Adapaun langkah-langkah algoritma genetika hybrid, bisa dilihat dari flowchart/diagram alir dari algoritma genetika hybrid. Start
• • • • • •
Mengurutkan Calon individu baru dari yang terkecil sampai terbesar baru
Kecepatan rata-rata Kapasitas kendaraan Waktu pelayanan Batasan waktu Jumlah permintaan dan jarak antar customer Parameter genetik (populasi, generasi, probabilitas pindah silang, probabilitas mutasi)
Solusi generasi ke-i = calon individu baru dengan jarak minimum
Mengurutkan Calon individu baru dari yang terkecil sampai terbesar baru
Pilih n individu baru
Populasi awal generasi ke i+1 = sejumlah n individu baru
Calon individu baru = populasi awal + individu baru Populasi awal Membuang individu yang tidak memenuhi kendala
Populasi Generasi ke-1 = populasi awal
Tampilkan solusi tiap generasi
For i : = 1 to generasi Evaluasi Fungsi Fitnes
Validasi Kapasitas
Pilih individu dengan jarak minimum dari solusi tiap generasi
Validasi Order Evaluasi Fungsi Fitnes Individu Baru
Tampilkan solusi terbaik
Local Search
Mutasi
Validasi Waktu
End
Seleksi
Crossover Flowchart Algoritma GenetikHybrid
Uji Coba Program Sebuah perusahaan A akan melakukan pengiriman barang kepada customernya yang tersebar di berbagai daerah. Pelayanan dimulai pukul 07.00 sampai dengan pukul 16.00 dengan kapasitas tiap kendaraan sebesar 75 kardus, kecepatan rata-rata kendaraan adalah 60 km/jam dan waktu untuk melayani persatu permintaan adalah sebesar 1 menit. Daftar permintaan tiap customer diberikan pada tabel berikut. Customer
1
2
3
4
5
6
7
8
Demand
20
25
15
30
20
15
30
25
Tabel Jarak 0
1
2
3
4
5
6
7
8
0
0
55
75
115
170
148
145
159
98
1
55
0
43
115
165
155
170
198
142
2
75
43
0
80
125
120
145
181
135
3
115
115
80
0
56
41
72
124
102
4
170
165
125
56
0
41
85
145
145
5
148
155
120
41
41
0
45
105
105
6
145
170
145
72
85
45
0
60
75
7
159
198
181
124
145
105
60
0
63
8
98
142
135
102
145
105
75
63
0
Perbandingan hasil uji coba Pm Jarak Minimum Jumlah Titik Populasi Generasi Pc 8 8 2 0.8 0.03 1081 8 10 2 0.8 0.03 1024 8 5 10 0.8 0.03 1090 8 10 10 0.8 0.03 899 20 5 10 0.8 0.03 118 50 10 2 0.8 0.03 116 100 10 2 0.8 0.03 120 Dari hasil uji coba diatas dapat dilihat bahwa jumlah populasi dan jumlah generasi maksimum mempengaruhi dalam pencapaian nilai optimum. Untuk jumlah kota dan populasi yang kecil tidak terlalu mempengaruhi ruang bagi algoritma genetika, namun jika jumlah kota besar dan populasi yang kecil maka tidak dapat memberikan ruang bagi algoritma genetika untuk memperbaiki keturunan. Untuk populasi yang besar kemungkinan untuk dapat memperbaiki tingkat populasi lebih besar. Sedangkan untuk jumlah generasi, apabila maksimum generasi terlalu besar (untuk data dengan ukuran kota yang relatif kecil kurang dari 10) akan menjadi tidak berguna karena populasi sudah mencapai kondisi optimum. Apabila generasi terlalu kecil (untuk ukuran data yang relatif besar lebih dari 10) algortima tidak akan bekerja dengan maksimal karena ketika belum mencapai optimum, proses algoritma sudah berhenti. Namun, untuk mendapatkan hasil yang benarbenar optimal, perlu dilakukan lebih dari satu kali uji coba dengan inputan yang sama.
Kesimpulan dan Saran Kesimpulan 1. Algoritma genetika hybrid dapat menyelesaikan permasalahan vehicle routing problem with time windows (VRPTW) sehingga dapat menentukan banyak kendaaran yang dibutuhkan dengan total waktu tempuh dan total jarak tempuh minimum. 2. Hasil yang diperoleh dengan menggunakan alat bantu program sama dengan manual. Meski demikian, tidak menutup kemungkinan hasil yang diperoleh berbeda., dikarenakan algoritma genetika hybrid berdasarkan pada pembangkitan secara random. Maka kadang tidak ditemukan hasil yang sama dengan manualnya. selain itu, Waktu yang diperlukan dalam menyelesaikan permasalahan dengan menggunakan alat bantu program lebih singkat bila dibandingkan dengan perhitungan secara manual. Saran 1. Sebaiknya dalam pengiterasian untuk mencari solusi digunakan alat bantu sehingga tidak membutuhkan waktu yang relatif lama. 2. Sebisa mungkin memberikan parameter genetik yang tidak terlalu besar akan tetapi menghasilkan solusi yang optimum, agar tidak membutuhkan waktu running yang lama. Pemberian parameter genetik yang terlampau besar hanyalah akan membuang-buang waktu saja, karena solusi yang diperoleh juga akan valid ketika diberikan parameter genetik yang tidak terlampau besar. 3. Perlu adanya pengembangan lebih lanjut dari penerapan algoritma genetika hybrid, sehingga tidak hanya pada permasalahan vehicle routing problem with time windows (VRPTW), namun dapat juga diterapkan pada permasalahan lain seperti permasalahan penjadwalan, shortest path. Daftar Pustaka Cheng, Lin. 2005. A Genetic Algorithm For The Vehicle Routing Problem With Time Windows, (online) (http://libres.uncg.edu/ir/uncw/f/chengl20051.pdf, diakses 3 oktober 2012). G.Vivo-Truyols,dkk. A Hybrid Genetic Algorithm with Local Search. (Online).(http://www.ual.es/GruposInv/anaconta/2001/A%20hybrid%20ge netic.pdf, diakses 3 oktober 2012). Loren’z, Pamelia. 2010. Implementasi Algoritma Genetika pada Vehicle Routing Problem with Time Windows. Skripsi tidak diterbitkan. Malang: Fakultas Matematika dan Ilmu Pengetahuan Alam Universitas Negeri Malang. Martínez, Carlos García- and Lozano2, Manuel. Local Search Based on Genetic Algorithms (Online). (http://sci2s.ugr.es/publications/ficheros/garciaSpringerBook08.pdf, diakses tanggal 3 oktober 2012) Michalewics, Zbiniew. 1996. Genetic Algorithms + Data Structures = Evolution Programs (online).
(http://www.stat.berkeley.edu/~aldous/Misc/michal.pdf, diakses tanggal 27 desember 2012) Ochoa, Gabriela, Sebastien and Marco. First-Improvement Vs. Best-Improvement Local Optima Networks Of NK Landscapes (Online), (http://www.cs.stir.ac.uk/~goc/papers/PPSN10FirstImprLON.pdf, diakses 3 oktober 2012). Syarif, Admi, Wamiliana & Junaidi, Akmal. 2007. Hybrid Genetic Algorithm dengan Fuzzy Logic Controller: Sebuah Pendekatan Baru Penyelesaian Traveling Salesman Problem (TSP). (Online). (http://digilib.unila.ac.id/ files/disk1/24/laptunilapp-gdl-res-2008-engadmisya-1178-2007_lp_-1.pdf, diakses 10 Maret 2012). Wilson, R. J and Watkins, J.J. 1990. Graph An Introductory Approach a First Course in Discrete Mathematics. Canada: John Willy and Sons, Inc. Yuliagandi, Devi. 2010. Implementasi Algoritma Genetika Hybrid (First Improvement Search) Pada Travelling Salesman Problem. Skripsi tidak diterbitkan. Malang: Fakultas Matematika dan Ilmu Pengetahuan Alam Universitas Negeri Malang. Yeun, Choong Liong and Zirour, Mourad. 2008. Vehicle Routing Problem : Models and Solution, (Online), (http://www.ukm.my/ppsmfst/jqma/Vol4_Is1/abstract/JQMA-4-1-19abstractrefs.pdf, diakses 5 Maret 2012) ________. Tanpa Tahun. 2. Tinjauan Pustaka. (Online), (http://jiunkpe/S1/ tmi/2006 /jiunkpe-ns-S1-2006-25402131/3424-flowshop-chapter2.pdf, diakses tanggal 3 oktober 2012)
