IMPLEMENTASI ALGORITMA GENETIKA (GA) PADA PERMASALAHAN VEHICLE ROUTING PROBLEM (VRP) DI PT FRISIAN FLAG INDONESIA (FFI) Ariyo Catur Wibowo, Anggara Hayun, J. Sudirwan Binus University, Jl. K.H. Syahdan,
[email protected]
ABSTRACT Transport is one of the important issues that are owned by the logistics department, so that transport costs should be as efficient as possible because it can contribute more in order to reduce the total cost and to improve the company’s competitive advantage. This research aims to generate a distribution service that has the shortest total mileage of limitations of the capacity of the vehicles, so that the distribution of the goods shall not exceed the limit of vehicles owned. Capacitated Vehicle Routing Problem (CVRP) is one of the problems with using a mathematical model based on considerations of distance and capacity of the vehicle in order to obtain the solution of this problem, use genetic algorithm (GA). GA chosen because it has the advantages of other methods, this genetic algorithm proposed has much quicker convergence speed, stronger overcoming getting into partial optimal ability. Therefore, it is more practical significance and value so as to reduce operating cost and improve economic benefit. As a support of basic goods distribution system, the system will be creating applications that integrate with the delivery process is used to determine which OOAD methods and system design requirements in accordance with company requirements. This system will be used as a tool to support the company's performance and speed up the process of making the distribution of goods. Keywords: VRP, Genetic Algorithm, Transportation, OOAD. ABSTRAK Transportasi merupakan salah satu permasalahan penting yang dihadapi oleh bagian logistik, dan biaya transportasi haruslah seefisien mungkin karena dapat memberikan kontribusi yang lebih sehingga dapat mengurangi total biayanya dan dapat meningkatkan keunggulan daya saing perusahaan. Penelitian ini bertujuan untuk menghasilkan suatu rute pendistribusian yang memiliki total jarak tempuh terpendek dengan memperhatikan batasan dari kapasitas kendaraan, sehingga pendistribusian barang tersebut tidak boleh melebihi dari batas kendaraan yang dimiliki. Capacitated Vehicle Routing Problem (CVRP) merupakan jenis permasalahan yang dihadapi dengan menggunakan model matematis berdasarkan pertimbangan jarak dan kapasitas kendaraan untuk dapat memperoleh solusi dari permasalahan ini maka digunakan algoritma genetika (GA). GA dipilih karena memiliki kelebihan dari metode yang lain, seperti GA menawarkan proses yang memiliki kecepatan yang lebih stabil seiring dengan berjalannya waktu dan kemampuan yang lebih kuat dalam menghadapi kemampuan yang optimal. GA secara praktikal digunakan untuk mengurangi biaya operasi dan memperbaiki nilai keuntungan. Sebagai penunjang dasar dari sistem pendistribusian barang, maka dibuatkan aplikasi sistem yang terintegrasi dengan proses pengiriman barang digunakan metode OOAD sehingga dapat ditentukan kebutuhan dan perancangan sistem yang sesuai dengan kebutuhan perusahaan. Sistem ini nantinya akan
digunakan sebagai tools untuk menunjang kinerja perusahaan dan mempercepat proses pembuatan rute distribusi barang. Kata kunci: VRP, Algoritma Genetika, Transportation, OOAD.
PENDAHULUAN Banyaknya persaingan serta kebutuhan pelanggan yang tinggi mendorong perusahaan untuk melakukan berbagai perbaikan dalam kegiatan distribusi dan transportasi. Permasalahan distribusi dan transportasi menjadi penting karena besarnya biaya yang harus dikeluarkan untuk aktivitas-aktivitas distribusi dalam manajemen logistik. Perusahaan menyadari bahwa masalah yang dapat menyebabkan kurang optimalnya transportasi ini disebabkan oleh jumlah permintaan yang berbeda-beda untuk tiap pelanggan, keterbatasan kendaraan, batas waktu pengiriman, lokasi pelanggan, permintaan yang berfluktuatif dan bagaimana membuat suatu rute dengan tujuan untuk meminimasi jumlah dari total jarak sehingga mengurangi biaya transportasi. Dengan mengetahui rute kendaraan dan jadwal pengiriman yang tepat, maka akan mengurangi permasalahan yang terdapat di bagian logistik. Permasalahan tersebut dapat dikatakan sebagai permasalahan Vehicle Routing Problem (VRP) dimana terjadi keterlambatan pengiriman yang dikarenakan kesalahan rute distribusi. Hal ini merupakan permasalahan Vehicle Routing Problem (VRP). VRP bertujuan untuk mencari rute yang paling optimal untuk pendistribusian barang dari satu depot ke pelanggan yang letaknya tersebar dan kembali lagi ke depot dengan harus memperhatikan batasan dari kapasitas yang dimiliki oleh kendaraan (Ong & Suprayogi, 2011, p. 1). Permasalahan VRP ini dapat diselesaikan dengan banyak metode, salah satunya dengan Algoritma Genetika (GA). GA merupakan suatu metode yang digunakan untuk memecahkan suatu pencarian nilai dalam permasalahan optimasi. Algoritma ini didasarkan pada proses genetik yang terdapat pada makhluk hidup dengan meniru teori evolusi biologi (Bräysy, 2001, p. 33). Metode GA dipilih karena memiliki kelebihan dari metode yang lain, seperti GA menawarkan proses yang memiliki kecepatan yang lebih stabil seiring dengan berjalannya waktu dan kemampuan yang lebih kuat dalam menghadapi kemampuan yang optimal. Maka GA lebih berharga dan praktikal secara signifikan untuk mengurangi biaya operasi dan memperbaiki nilai keuntungan (REN, 2012, p. 1). Salahnya memilih rute pendistribusian sehingga mengakibatkan keterlambatan pengiriman barang. Hal ini membuat perusahaan mengeluarkan biaya operasional yang lebih. Selain itu perusahaan sering mengalami permasalahan dalam hal kekurangan kendaraan, dikarenakan banyaknya permintaan pelanggan yang muncul setiap harinya. Apabila permasalahan ini tidak segera diselesaikan, cepat atau lambat perusahaan akan mengalami kerugian yang besar. FFI selama ini sudah menjalankan kegiatan bisnisnya dengan sistem yang telah terintegrasi dengan baik, sehingga memungkinkan FFI meminimalisir kesalahan yang terjadi. Namun dalam hal pendistribusian barang, penentuan rute dan penentuan jarak terpendek masih menggunakan cara yang manual. Dalam hal pencarian rute pendistribusian perusahaan selalu menggunakan cara memisahkan pesanan per wilayah seperti Jakarta Timur, Jakarta Selatan dan Bekasi. Setelah itu membagi kendaraan sesuai dengan wilayahnya dengan melihat jumlah pesanan dan kapasitas kendaraan. Penentuan rute distribusi ini dilakukan secara manual menghabiskan waktu yang cukup lama biasanya menghabiskan waktu kurang lebih 30 menit hingga satu jam. Oleh sebab itu, maka akan dirancang program aplikasi yang dapat melakukan pencarian rute distribusi yang lebih cepat, sehingga nantinya akan dapat menghemat waktu dan biaya serta meningkatkan pelayanan terhadap pelanggan. Pembuatan program dengan menggunakan metode GA, dengan memperhitungkan jarak dari depot ke pelanggan dan jarak antar pelanggan serta jumlah kendaraan yang digunakan dan kapasitas dari kendaraan tersebut. Pencarian rute terpendek tanpa sebuah program komputer hanyalah menjadi sebuah kotak yang tak berguna. Pemanfaatan teknologi informasi pada pencarian jalur terpendek menghasilkan suatu hasil yang akurat dan tepat. Sehingga dengan adanya program rute pendistribusian barang ini, diharapkan FFI akan
lebih berkembang lagi dan memberikan pelayanan yang lebih baik lagi bagi pelanggannya (Mutakhiroh, Saptono, & Wiryadinata, 2007, p. 33). Oleh karena itu, optimalisasi pemilihan rute dan jarak tempuh terpendek dalam melakukan pendistribusian pengiriman barang dan perancangan sistem informasi yang terorganisir harus dilakukan untuk mengoptimalkan pendistribusian pengiriman barang yang dilakukan oleh FFI.
METODE PENELITIAN Dalam melakukan penelitian ini dijelaskan mengenai proses dan urutan pengerjaannya. Berikut adalah proses pengerjaannya: 1. Penelitian Pendahuluan Penelitian pendahuluan yang dilakukan di PT. Frisian Flag Indonesia (FFI) adalah dengan melakukan observasi terhadap keseluruhan pabrik dan mempelajari gambaran pabrik secara umum. Melalui penelitian pendahuluan akan diketahui pula proses bisnis yang berjalan di FFI. Selain observasi langsung, dilakukan pula wawancara terhadap para karyawan FFI. Penelitian pendahuluan yang dilakukan bertujuan untuk memudahkan identifikasi masalah di tahap selanjutnya. 2. Perumusan Masalah Setelah melakukan observasi langsung dan wawancara, maka akan ditemukan beberapa masalah yang dihadapi oleh FFI. Permasalahan yang ditemukan akan diangkat menjadi suatu identifikasi permasalahan yang akan diselesaikan dalam penelitian ini. Dari permasalahan yang ditemukan, terdapat batasan masalah yang akan menjadi ruang lingkup dari penelitian. Dari perumusan masalah serta ruang lingkup yang dibuat, diharapkan tujuan dari penelitian ini dapat tercapai dan juga bermanfaat bagi peneliti, pembaca serta perusahaan itu sendiri. 3. Studi Pustaka Setelah itu peneliti akan mencari informasi serta teori-teori pendukung mengenai permasalahan studi kasus yang dilakukan. Studi pustaka yang dilakukan dengan menggunakan buku-buku sebagai literatur, jurnal-jurnal ilmiah ataupun informasi dari internet. Studi pustaka yang dilakukan diharapkan akan menjadi suatu landasan teori untuk menyelesaikan permasalahan yang ada di FFI. 4. Pengumpulan Data Pengumpulan data dapat diperoleh peneliti secara langsung dan tidak langsung. Data yang diperoleh secara langsung oleh peneliti dengan cara melakukan observasi dan survei ke perusahaan. Data yang diperoleh secara tidak langsung dapat berupa catatan laporan-laporan yang terdapat di dalam arsip. Adapun data-data yang diperlukan oleh peneliti adalah profil perusahaan, proses bisnis yang terdapat di dalam perusahaan, data konsumen, data permintaan, data kendaraan yang digunakan dan biaya operasional yang dikeluarkan oleh perusahaan. 5. Pengolahan Data Dari data yang telah terkumpul, tahap selanjutnya adalah melakukan pengolahan akan data-data tersebut. Pengolahan data dilakukan dengan menggunakan metode Genetika Algoritma (GA) yang terdiri dari 5 tahapan, yaitu: a. Populasi Awal Pada tahap ini adalah proses membangkitkan sejumlah individu secara acak atau melalui prosedur tertentu. Syarat-syarat yang harus dipenuhi untuk menunjukkan suatu solusi harus benar-benar diperhatikan dalam pembangkitan setiap individunya. b. Evaluasi Fitness Pertama-tama mencari nilai fitness yang akan dijadikan acuan dalam mencapai nilai optimal dalam algoritma genetika. Nilai fitness adalah nilai yang menyatakan baik tidaknya suatu solusi (individu). c. Seleksi Individu Seleksi dilakukan untuk mendapatkan calon induk yang baik, “induk yang baik akan menghasilkan keturunan yang baik”. Semakin tinggi nilai fitness suatu individu maka semakin besar kemungkinannya untuk terpilih. Seleksi dapat dilakukan dengan menggunakan random acak. d. Crossover dan Mutasi Setelah melakukan seleksi individu, maka tahap selanjutnya adalah melakukan crossover dan mutasi. Crossover merupakan proses mengkombinasikan dua individu untuk memperoleh individu-individu baru yang diharapkan mempunyai fitness lebih baik. Tidak semua pasangan
induk mengalami proses crossover, banyaknya pasangan induk yang mengalami crossover ditentukan dengan nilai probabilitas crossover. Mutasi gen adalah proses penggantian gen. Proses ini dilakukan secara acak pada posisi gen tertentu pada individu-individu yang terpilih untuk dimutasikan. Banyaknya individu yang mengalami mutasi ditentukan oleh besarnya probabilitas mutasi. e. Populasi Baru Setelah melakukan tahapan-tahapan tersebut maka akan didapatkan populasi baru. Dari populasi baru ini akan diulang kembali dari tahap 2 dan selanjutnya sampai menemukan hasil yang paling optimal. 6. Analisis dan Pembahasan Setelah melakukan pengolahan data selanjutnya peneliti melakukan analisis dari data yang telah di olah tersebut. Analisis dilakukan terhadap alternatif pemilihan rute pendistribusian barang dan pemilihan dari alternatif rute yang diberikan. Tujuan dari analisis ini adalah untuk memberikan suatu kesimpulan dari permasalah yang diangkat dan dapat memberikan saran yang berarti bagi perusahaan. 7. Perancangan Sistem Informasi Setelah melakukan analisis pengolahan data dan analisis, maka didapatkan struktur data yang nantinya dimasukkan ke dalam sistem yang akan dibuat. Sistem yang dirancang mengacu pada pengolahan data dan analisis kebutuhan user. Sistem dirancang berdasarkan proses bisnis, aktor yang terkait, event yang terjadi dan kegiatan-kegiatan yang dilakukan dalam sistem. 8. Pembuatan Sistem Informasi Tahap ini adalah melakukan pembuatan sistem informasi berupa aplikasi yang didasarkan pada perancangan sistem informasi sebelumnya, mulai dari problem domain analysis sampai dengan realisasi dari component design. Diharapkan dengan adanya pembuatan program ini, sistem distribusi pada perusahaan akan berjalan dengan lebih baik lagi. 9. Pengujian Sistem Informasi Pengujian sistem informasi ini dilakukan untuk melihat apakah masih terdapat banyak error atau bugs, apabila masih terdapat banyak error maka akan dikaji ulang sampai tidak ada lagi error atau bugs. Serta apakah program yang dibuat sudah sesuai dengan kebutuhan user. 10. Simpulan dan Saran Setelah melakukan tahapan ini semua, maka akan dapat ditarik suatu simpulan mengenai permasalahan yang ada. Simpulan yang dibuat ini diharapkan dapat memberikan jawaban dari tujuan penelitian ini, kemudian nantinya sebuah saran akan diberikan yang berguna dan bermanfaat bagi perusahaan untuk meningkatkan persaingan. Simpulan ini berisikan tentang hasil dari penelitian tersebut. Berdasarkan hasil penelitian maka akan didapatkan saran yang berguna bagi kemajuan perusahaan dan untuk meningkatkan kualitas pelayanannya. Berikut adalah gambar diagram alir penelitian:
Gambar 1. Diagram Alir Penelitian
LANGKAH-LANGKAH GA 1.
Populasi Awal Tahap ini bertujuan untuk membangkitkan sebuah populasi awal yang berisi sejumlah kromosom yang telah ditentukan banyaknya. Sebagai contoh banyaknya kromosom dalam populasi awal telah ditentukan sebanyak 30 kromosom, kromosom yang terbentuk terlihat seperti pada Tabel 1. Populasi awal ini dipilih secara random, berdasarkan nilai random yang muncul. Pada tahap populasi awal ini adalah seluruh individu dalam populasi sebelum iterasi dimulai. Tabel 1. Populasi Awal Kromosom 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
2.
4 11 1 8 17 13 15 12 4 4 4 14 19 6 7 7 8 10 2 20 15 6 8 15 20 17 6 15 18 4
8 4 16 15 9 17 20 1 19 2 8 8 14 4 8 4 3 14 12 19 10 13 9 8 16 9 20 11 11 7
12 18 10 6 15 5 2 15 8 17 1 16 6 19 19 2 4 5 9 18 2 18 3 7 7 7 13 1 17 9
13 19 18 9 19 6 11 10 13 15 11 6 13 17 11 13 10 20 14 4 20 4 6 5 4 10 4 13 5 18
20 17 19 3 14 1 9 17 14 6 2 2 8 7 5 10 13 15 5 7 7 5 4 19 15 16 5 19 7 10
1 15 4 14 1 12 13 13 3 5 3 15 20 14 2 6 14 6 1 2 8 20 14 4 3 11 12 20 14 15
10 8 8 5 20 14 7 8 9 11 17 12 4 12 3 12 12 4 20 13 13 12 12 3 1 20 3 16 6 1
3 13 6 17 10 16 19 20 5 14 13 3 10 15 20 15 18 13 3 12 5 17 13 1 9 1 16 4 13 20
Populasi Awal 2 5 11 17 9 10 12 20 2 6 3 12 15 20 13 2 1 20 7 18 2 3 13 11 8 3 11 7 2 19 8 12 10 1 14 14 18 9 16 5 2 17 12 6 18 12 16 7 9 8 16 20 7 15 10 5 19 18 9 1 16 17 1 12 11 8 13 18 3 5 1 4 17 15 18 11 16 9 5 17 5 9 19 6 17 1 9 18 16 12 6 16 10 18 11 6 9 8 17 5 16 3 12 17 1 7 1 16 19 10 1 17 5 18 19 9 13 18 2 16 12 5 2 18 19 12 14 13 3 2 15 11 9 14 19 18 5 7 3 9 8 3 1 2 12 14 5 8 11 12
19 14 7 13 19 9 16 4 7 10 6 10 5 10 9 3 7 7 15 3 11 11 20 10 10 8 8 2 9 6
6 3 11 10 4 18 5 3 10 1 12 20 18 9 10 8 2 3 13 1 14 9 2 20 17 19 2 10 10 2
18 16 14 16 6 10 3 7 20 18 14 4 9 2 13 14 1 19 7 10 19 2 16 12 11 18 1 14 15 3
14 5 5 4 12 20 6 11 11 20 19 7 15 20 12 19 16 17 17 11 18 15 7 14 6 15 10 8 20 19
16 7 2 12 7 4 18 19 16 13 5 11 2 11 16 20 15 8 19 14 4 8 11 17 8 6 17 17 19 13
15 1 17 19 5 8 4 2 1 19 18 17 3 16 6 18 20 11 8 15 6 14 15 6 14 5 18 6 4 16
7 9 9 11 16 15 17 6 15 3 9 13 7 1 14 1 11 2 4 16 9 3 10 11 13 4 7 12 16 17
Evaluasi Fungsi Fitness Fungsi fitness digunakan untuk menentukan seberapa baik individu yang dihasilkan oleh setiap kromosom. Total jarak adalah jumlah jarak antara satu rute dengan rute lainnya. Semakin tinggi nilai suatu fitness dari suatu kromosom, maka akan semakin baik nilai kromosom tersebut. Untuk mencari nilai fitness adalah sebagai berikut: Fungsi fitness =
= 0.00242
Maka akan diperoleh hasil nilai fitness dari setiap kromosom, sebagai berikut: Tabel 2. Nilai Fitness
Kromosom Total Jarak 1 412.6 2 331.9 3 392.1 4 428.3 5 422.4 6 394.5 7 341.7 8 450.3 9 365.2 10 325.2 11 385.7 12 418.9 13 416.6 14 404.8 15 512.0
3.
Kromosom Total Jarak 16 383.4 17 409.5 18 360.6 19 357.9 20 415.9 21 429.6 22 442.4 23 454.2 24 394.5 25 382.2 26 401.5 27 389.4 28 379.9 29 420.7 30 460.6 Total 12084.5
Fitness 0.00261 0.00244 0.00277 0.00279 0.00240 0.00233 0.00226 0.00220 0.00253 0.00262 0.00249 0.00257 0.00263 0.00238 0.00217 0.07519
Seleksi Tahap selanjutnya adalah menyeleksi hasil populasi tersebut. Sebelum melakukan seleksi ini, pertama-tama adalah mencari probabilitas fitness tiap rute dan mencari probabilitas kumulatif tiap rute. Probabilitas fitness didapatkan dengan cara pertama-tama menjumlahkan seluruh nilai fitness yang ada setelah itu nilai fitness setiap individu di bagi dengan jumlah total nilai fitness. Hasil probabilitas fitness (pk) yang ada dapat dilihat pada tabel di bawah ini. Kemudian mencari probabilitas kumulatif (qk) tiap rute. Berikut adalah contoh perhitungan untuk mendapatkan pk dan qk. Tabel 3. Hasil Seleksi dari Masing-masing Kromosom 6 6 8 15 4 18 7 8 4 17 11 2 14 10 8 7 4 4 11 8 11 7 4 14 1 20 8 17 6 15
4.
Fitness 0.00242 0.00301 0.00255 0.00233 0.00237 0.00253 0.00293 0.00222 0.00274 0.00308 0.00259 0.00239 0.00240 0.00247 0.00195
13 4 15 20 8 11 8 9 8 9 4 12 8 14 15 4 8 7 4 9 4 4 8 8 16 19 3 9 4 10
18 19 6 2 1 17 19 3 12 15 18 9 16 5 6 2 1 9 18 3 18 2 1 16 10 18 4 7 19 2
4 17 9 11 11 5 11 6 13 19 19 14 6 20 9 13 11 18 19 6 19 13 11 6 18 4 10 10 17 20
5 7 3 9 2 7 5 4 20 14 17 5 2 15 3 10 2 10 17 4 17 10 2 2 19 7 13 16 7 7
20 14 14 13 3 14 2 14 1 1 15 1 15 6 14 6 3 15 15 14 15 6 3 15 4 2 14 11 14 8
12 12 5 7 17 6 3 12 10 20 8 20 12 4 5 12 17 1 8 12 8 12 17 12 8 13 12 20 12 13
Kromosom 17 7 15 8 17 2 19 8 13 16 13 8 20 1 13 1 3 2 10 2 13 10 3 6 3 5 13 1 17 2 15 11 13 16 20 14 13 10 13 1 13 10 15 11 13 16 3 5 6 3 12 6 18 5 1 12 15 8 5 16
1 13 1 12 20 3 4 17 5 3 12 16 19 9 1 16 20 5 12 17 12 16 20 19 12 9 9 14 13 3
16 18 20 10 7 1 17 5 11 13 20 10 18 18 20 9 7 8 20 5 20 9 7 18 15 8 19 13 18 12
19 3 7 1 15 2 15 18 17 11 2 18 9 16 7 5 15 11 2 18 2 5 15 9 20 17 6 3 3 17
10 5 18 14 10 12 18 19 9 8 6 11 1 12 18 17 10 12 6 19 6 17 10 1 13 5 17 2 5 1
11 10 13 16 6 9 9 20 19 19 14 15 10 7 13 3 6 6 14 20 14 3 6 10 7 3 7 8 10 11
9 9 10 5 12 10 10 2 6 4 3 13 20 3 10 8 12 2 3 2 3 8 12 20 11 1 2 19 9 14
2 2 16 3 14 15 13 16 18 6 16 7 4 19 16 14 14 3 16 16 16 14 14 4 14 10 1 18 2 19
15 20 4 6 19 20 12 7 14 12 5 17 7 17 4 19 19 19 5 7 5 19 19 7 5 11 16 15 20 18
8 11 12 18 5 19 16 11 16 7 7 19 11 8 12 20 5 13 7 11 7 20 5 11 2 14 15 6 11 4
14 16 19 4 18 4 6 15 15 5 1 8 17 11 19 18 18 16 1 15 1 18 18 17 17 15 20 5 16 6
3 1 11 17 9 16 14 10 7 16 9 4 13 2 11 1 9 17 9 10 9 1 9 13 9 16 11 4 1 9
Fitness 0.00226 0.00247 0.00233 0.00293 0.00259 0.00238 0.00195 0.00220 0.00242 0.00237 0.00301 0.00279 0.00239 0.00277 0.00233 0.00261 0.00259 0.00217 0.00301 0.00220 0.00301 0.00261 0.00259 0.00239 0.00255 0.00240 0.00244 0.00249 0.00247 0.00233
Ke22 14 4 7 11 29 15 23 1 5 2 19 12 18 4 16 11 30 2 23 2 16 11 12 3 20 17 26 14 21
Crossover Crossover merupakan suatu proses persilangan sepasang kromosom parents untuk menghasilkan offspring atau keturunan yang menjadi generasi berikutnya. Offspring yang dihasilkan dari proses crossover ini diharapkan memiliki sifat-sifat yang unggul yang dimiliki oleh parents mereka. Penentuan crossover dilakukan dengan cara membandingkan nilai probabilitas crossover (pc) tersebut dengan bilangan yang dibangkitkan secara random. Metode yang digunakan untuk melakukan crossover adalah dengan metode penyilangan banyak titik (multi-point crossover), yaitu panjang kromosom diseleksi secara random dan tidak diperbolehkan
ada posisi yang sama, variabel-variabel ditukar antar kromosom pada titik tersebut untuk menghasilkan keturunan/ anak yang lebih baik dari orang tuanya (parent). Tabel 4. Hasil dari Crossover
5.
6.
Anak 1 Anak 2
4 17
8 9
12 15
19 13
14 20
1 1
20 10
10 3
2 2
Anak 3 Anak 4
4 14
2 8
17 16
15 6
6 2
14 5
12 11
3 15
5 12
Anak 5 Anak 6
2 20
12 19
18 9
4 14
7 5
20 1
13 2
19 3
6 6
Anak 7 Anak 8
15 6
10 13
2 18
4 20
5 7
20 8
12 15
17 5
7 16
Anak 9 Anak 10
8 20
9 16
3 7
6 4
15 8
20 14
1 12
16 13
12 1
Anak 11 Anak 12
17 6
9 20
7 13
10 4
5 16
12 11
3 17
16 1
15 12
Anak 13 Anak 14
15 18
11 11
17 1
5 13
7 19
14 20
6 16
13 4
8 15
Kromosom 3 13 5 11 Kromosom 19 18 17 7 Kromosom 9 8 16 10 Kromosom 1 16 3 12 Kromosom 5 2 17 5 Kromosom 11 6 14 9 Kromosom 3 1 5 7
11 12
9 8
17 19
15 6
6 18
18 14
7 16
5 4
16 7
9 9
1 4
10 10
20 1
8 18
7 20
11 13
16 19
13 3
17 18
5 11
3 15
1 13
10 7
11 17
14 12
15 8
16 4
19 17
6 1
11 11
9 14
13 19
18 10
8 4
14 2
3 9
18 18
19 19
10 9
17 2
11 3
7 6
4 11
14 15
13 10
14 3
19 2
8 8
2 19
1 18
20 15
13 7
18 5
4 10
` 3
12 9
9 2
10 10
18 14
20 8
19 17
4 6
16 12
Fitness 0.00236 0.00207 Fitness 0.00239 0.00249 Fitness 0.00221 0.00312 Fitness 0.00262 0.00225 Fitness 0.00231 0.00235 Fitness 0.00289 0.00238 Fitness 0.00231 0.00238
Mutasi Proses mutasi merupakan proses untuk menggantikan gen-gen yang hilang dari populasi dalam proses seleksi, selain itu untuk menghasilkan gen-gen yang tidak terdapat pada populasi awal. Proses mutasi ini dilakukan berdasarkan bilangan random yang dihasilkan, apabila nilai bilangan random lebih besar dari probabilitas mutasi maka individu tersebut tidak akan dimutasi, namun apabila nilai bilangan random tersebut lebih kecil dari peluang mutasi maka individu tersebut akan di mutasi. Proses mutasi dilakukan dengan mengubah satu atau beberapa gen dalam kromosom. Metode yang digunakan pada proses mutasi ini adalah metode mutasi biner. Tabel 5. Kromosom Kena Mutasi Kromosom Kena Mutasi 10 4 2 17 11 4 8 1 12 14 8 16
15 11 6
6 2 2
5 3 15
11 17 12
14 13 3
12 16 5
16 20 19
7 7 18
9 15 9
8 10 1
10 6 10
1 12 20
18 14 4
20 19 7
13 5 11
19 18 17
3 9 13
Kromosom Hasil Mutasi 10 4 2 17 11 4 17 1 12 14 8 16
12 11 6
6 2 2
5 3 15
11 8 12
14 13 3
15 16 5
16 20 19
7 7 18
9 15 20
8 10 1
10 6 10
1 12 9
18 14 4
20 19 7
13 5 11
19 18 17
3 9 13
Pelestarian Individu Terbaik Setelah melakukan tahapan itu semua, maka akan didapatkan hasil yang optimal, walaupun belum tentu menghasilkan yang paling optimal. Untuk mendapatkan hasil yang optimal harus dibuat sampai dengan generasi ke-100. Hasil dari populasi akhir generasi ke-1 ini, nantinya akan dijadikan sebagai populasi awal untuk dilakukan proses di generasi ke-2, mulai dari tahap seleksi, crossover, mutasi hingga pelestarian individu terbaik lagi. Proses ini akan selalu berulang sampai maksimum generasi ke-100. Kemudian didapatkan populasi akhir pada generasi ke-100 dan nantinya akan dipilih berdasarkan nilai fitness yang terbesar untuk dijadikan sebagai rute yang optimal. Hasil dari Generasi ke-1 dapat dilihat pada Tabel 6.
Tabel 6. Hasil Generasi Ke-1 Kromosom 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
4 11 1 8 17 13 15 12 4 4 4 14 19 6 7 7 8 10 2 20 15 6 8 15 20 17 6 15 18 4
8 4 16 15 9 17 20 1 19 2 17 8 14 4 8 4 3 14 12 19 10 13 9 8 16 9 20 11 11 7
12 18 10 6 15 5 2 15 8 17 1 16 6 19 19 2 4 5 18 9 2 18 3 7 7 7 13 17 1 9
19 19 18 9 13 6 11 10 13 15 11 6 13 17 11 13 10 20 4 14 4 20 6 5 4 10 4 5 13 18
14 17 19 3 20 1 9 17 14 6 2 2 8 7 5 10 13 15 7 5 5 7 15 19 8 5 16 7 19 10
1 15 4 14 1 12 13 13 3 14 3 5 20 14 2 6 14 6 20 1 20 8 20 4 14 12 11 14 20 15
20 8 8 5 10 14 7 8 9 12 8 11 4 12 3 12 12 4 13 2 12 15 1 3 12 3 17 6 16 1
10 13 6 17 3 16 19 20 5 3 13 15 10 15 20 15 18 13 19 3 17 5 16 1 13 16 1 13 4 20
Populasi Awal 2 3 13 11 10 12 20 2 3 12 15 20 2 1 20 7 2 5 11 12 3 11 7 2 8 12 10 1 14 18 9 16 2 17 12 6 5 19 18 9 16 20 7 15 12 17 7 9 16 17 1 12 8 13 18 3 1 4 17 15 11 16 9 5 5 9 19 6 1 9 18 16 6 9 8 17 6 16 10 18 7 1 16 19 16 3 12 17 12 5 2 18 9 13 18 2 1 17 5 18 15 11 6 14 12 14 9 3 8 3 1 2 15 5 7 3 14 5 8 11
9 6 13 18 8 19 14 5 18 1 10 4 11 5 18 17 17 12 5 11 6 1 19 16 19 19 2 12 9 12
17 14 7 13 19 9 16 4 7 10 6 10 5 10 9 3 7 7 3 15 11 11 10 10 9 8 8 9 2 6
15 3 11 10 6 18 5 3 10 20 12 1 18 9 10 8 2 3 1 13 9 14 17 20 2 2 19 10 10 2
6 16 14 16 18 10 3 7 20 8 14 18 9 2 13 14 1 19 10 7 13 19 11 12 3 1 18 18 14 3
18 5 5 4 14 20 6 11 11 7 19 20 15 20 12 19 16 17 11 17 18 10 7 14 6 20 15 20 8 19
7 7 2 12 16 4 18 19 16 11 5 13 2 11 16 20 15 8 14 12 8 4 4 17 11 13 7 19 17 13
5 1 17 19 4 8 4 2 1 16 18 19 3 16 6 18 20 11 15 8 14 2 14 6 15 18 5 4 6 16
16 9 9 11 7 15 17 6 15 13 9 3 7 1 14 1 11 2 16 4 3 9 13 11 10 4 10 16 12 17
Fitness 0.00236 0.00301 0.00255 0.00233 0.00207 0.00253 0.00293 0.00222 0.00274 0.00239 0.00259 0.00249 0.00240 0.00247 0.00195 0.00261 0.00244 0.00277 0.00221 0.00312 0.00262 0.00225 0.00231 0.00253 0.00235 0.00289 0.00238 0.00231 0.00238 0.00217
HASIL DAN PEMBAHASAN Untuk memudahkan pencarian rute yang cepat, dibuatkan program aplikasi dengan menggunakan metode GA. Pengujian aplikasi dilakukan sebanyak 10 kali percobaan dan dengan iterasi masing-masing percobaan 100 iterasi. Parameter yang digunakan dalam aplikasi ini adalah probabilitas crossover 0.5 dan probabilitas mutasi 0.1, dengan jumlah populasi sebanyak 30 populasi serta jumlah pelanggan sebanyak 20. Tabel 7. Perbandingan Percobaan Sebanyak 1000 Iterasi Percobaan Iterasi 1 2 3 4 5 6 7 8 9 10
100 200 300 400 500 600 700 800 900 1000
Kendaraan 1
Total Jarak (km)
Kendaraan 2
Total Jarak (km)
Kendaraan 3
Total Jarak (km)
Kendaraan 4
Total Jarak (km)
Kendaraan 5
0-17-7-12-14-0 0-11-17-7-6-0 0-12-17-7-6-0 0-16-6-8-0 0-16-5-1-17-6-18-0 0-10-6-19-5-1-3-0 0-13-8-14-18-0 0-13-1-9-3-7-18-0 0-3-9-10-6-19-0 0-12-17-7-5-16-0
391.4 92 92 80.2 107 95.4 69.8 100.8 103.1 100.9
0-4-15-0 0-8-5-9-16-0 0-20-4-11-13-0 0-14-5-12-9-17-18-0 0-8-7-12-0 0-11-17-7-9-16-0 0-15-2-0 0-15-2-0 0-8-1-5-16-0 0-13-8-6-0
51.6 101.5 64.9 106.9 89.2 114.8 55.7 55.7 83.8 68.8
0-16-6-8-0 0-8-5-9-16-0 0-19-3-9-1-10-18-0 0-20-7-3-11-0 0-20-13-11-2-0 0-20-4-12-0 0-16-5-12-6-10-0 0-20-4-12-0 0-20-4-11-13-0 0-15-2-18-0
80.2 93.1 95 116.7 66.1 84.9 85.3 84.9 64.9 59.2
0-20-13-11-2-18-0 0-15-4-0 0-15-2-0 0-4-13-10-1-19-0 0-15-4-0 0-15-2-0 0-19-3-9-1-11-4-0 0-11-8-14-19-0 0-15-2-18-0 0-4-10-9-1-19-0
69.6 53.1 55.7 87.6 53.1 55.7 96.1 91.4 59.2 99.6
0-10-19-1-5-9-3-0 0-20-13-11-2-18-0 0-8-14-5-16-0 0-15-2-0 0-3-9-14-10-19-0 0-13-8-14-18-0 0-20-17-7-0 0-16-10-6-5-17-0 0-12-17-7-14-0 0-20-11-14-3-0
Total Jarak Sub Total (km) Jarak (km) 103.9 69.6 80.2 55.7 102.7 69.8 101.9 119.4 88.3 116.6
Untuk memudahkan penghitungan dan kalkulasi, dilakukan konversi nama pelanggan dengan bentuk angka. Setiap kendaraan tidak boleh melebihi dari batas kapasitas kendaraan, yaitu seberat 2 ton sehingga setiap permintaan yang akan dikirim tidak boleh lebih dari 2 ton. Pada Tabel 7 telah dilakukan pengujian aplikasi sesuai dengan permasalahan rute dan permasalahan kapasitas kendaraan. Pengujian aplikasi dilakukan sebanyak 1000 kali iterasi. Sebanyak 1000 iterasi, didapatkan sub total jarak yang paling kecil terletak pada iterasi yang dilakukan sebanyak 300 kali iterasi, dengan total jarak tempuh sebesar 387.8 km.
696.7 409.3 387.8 447.1 418.1 420.6 408.8 452.2 399.3 445.1
Tabel 9. Rute Pendistribusian dengan 300 Iterasi Kendaraan 1 Depot - Carrefour Alfa Pasar Minggu Carrefour Alfa Pasar Minggu - Giant SPM Lebak Bulus Giant SPM Lebak Bulus - Carrefour Lebak Bulus Carrefour Lebak Bulus - Carrefour Kramat Jati Carrefour Kramat Jati - Depot
Kendaraan 3 Kendaraan 5 Depot - Hero Gatot Subroto Depot - Carrefour MT Haryono Hero Gatot Subroto - Carrefour Blok M Square Carrefour MT Haryono - Giant Kalibata Carrefour Blok M Square - Carrefour Permata Hijau Giant Kalibata - Carrefour Kota Kasablanka Carrefour Permata Hijau - Carrefour Ambassador Carrefour Kota Kasablanka - Giant Plaza Semanggi Carrefour Ambassador - Carrefour Taman Mini Giant Plaza Semanggi - Depot Carrefour Taman Mini - Giant SPM Pekayon Giant SPM Pekayon - Depot Total Jarak: 92 Km Total Jarak: 95 Km Total Jarak: 80.2 Km Kendaraan 2 Kendaraan 4 Depot - Indomaret DC Jababeka Depot - Giant Metland Transyogi Indomaret DC Jababeka - Carrefour Blue Mall Bekasi Giant Metland Transyogi - Carrefour Bekasi Square Carrefour Blue Mall Bekasi - Carrefour Alfa Bekasi Harapan Carrefour Bekasi Square - Depot Carrefour Alfa Bekasi Harapan - Giant Hypermarket Bekasi Giant Hypermarket Bekasi - Depot
Total Jarak: 64.9 Km
Total Jarak: 55.7 Km
SIMPULAN DAN SARAN Simpulan yang dapat diambil adalah sebagai berikut: 1. Algoritma Genetika dapat digunakan untuk menyelesaikan permasalahan Vehicle Routing Probel (VRP). 2. Hasil pencarian rute alternatif bervariasi, hal ini disebabkan oleh beberapa faktor diantaranya jumlah iterasi yang dilakukan serta bilangan random yang muncul, mengakibatkan pencarian rute tidak dapat mendapatkan hasil yang sama setiap melakukan pencarian. Beberapa saran yang dapat dijadikan pertimbangan untuk perusahaan sebagai berikut: 1. Perusahaan disarankan menggunakan aplikasi ini untuk menentukan rute distribusi sehingga biaya distribusi dapat di mininimalisir dan dapat diperkirakan. 2. Penelitian selanjutnya diharapkan untuk mempertimbangkan kemacetan, sebagai dasar perhitungan jarak tempuh antar pelanggn dan depot. 3. Peneltian selanjutnya disarankan mengembangkan metode Hybrid Algoritma Genetika sehingga dapat memberikan hasil yang lebih optimal.
REFERENSI Arief, N. W. (2011, April 15). Aspek Teknologi Informasi dalam Lingkungan Bisnis. Retrieved from Amikom: http://research.amikom.ac.id/index.php/KIM/article/view/4373/2707 Bräysy, O. (2001). Genetic Algorithm for the Vehicle Routing Problem with Time WIndows. Transportaion Science, 33-38. Gaol, D. C. (2008). Sistem Informasi Manajemen: Pemahaman dan Aplikasi. Jakarta: PT Grasindo. Gaspersz, V. (2009). Production Planning and Inventory Control Berdasarkan Pendekatan Sistem Terintegrasi MRP II dan JIT Menuju Manufakturing 21. Jakarta: Gramedia Pustaka Utama. Kusumadewi, S., & Purnomo, H. (2010). Penyelesaian Masalah Optimasi dengan Teknik-teknik Heuristik. Man, K. F., Tang, K. S., & Kwong, S. (1996). Genetic Algorithms: Concepts and Applications. IEEE Transactions on Industrial Electronics(Vol. 43), 519-534. Mutakhiroh, I., Saptono, F., & Wiryadinata, R. (2007). Pemanfaatan Metode Heuristik Dalam Pencarian Jalur Terpendek Dengan Algoritma Semut dan ALgoritma Genetika. Seminar Nsional Aplikasi Teknologi Informasi, 33-39. O'Brien, J. A. (2005). Pengantar Sistem Informasi Perspektif Bisnis dan Manajerial. Jakarta: Penerbit Salemba Empat. Ong, J. O., & Suprayogi. (2011). Vehicle Routing Probelm With Backhaul Multiple Trips and Time Window. Jurnal Teknik Industri(Vol. 13), 1-10. Satzinger, J. W., Jackson, R. B., & Burd, S. D. (2004). Systems Analysis and Design in Changing World, Third Edition. United States of America: Thomson Learning, Inc.
Sutapa, I. N., & Widyadana, I. G. (2003). Studi Tentang Travelling Salesman Dan Vehicle Routing Problem Dengan Time Windows. Jurnal Teknik Industri Vol. 5, No. 2, 81-89. Tanujaya, W., Dewi, D. R., & Endah, D. (2011). Penerapan Algoritma Genetik Untuk Penyelesaian Masalah Vehicle Routing Di PT. MIF. Widya Teknik(Vol. 10), 92-102. Wijaya, S. F., & Alianto, H. (2012). Esensi dan Penerapan ERP dalam Bisnis. Yogyakarta: Graha Ilmu. Yakub. (2012). Pengantar Sistem Informasi Edisi Pertama. Yogyakarta: Graha Ilmu.
