Jurnal Teknologi Informasi, Volume 6 Nomor 1, April 2010, ISSN 1414-9999 OPTIMASI PENJALURAN SALESMAN DENGAN METODE RODA ROULETTE, ORDER CROSSOVER, DAN SWAP MUTATION Djarot Nugroho, Yohan Wismantoro, Heribertus Himawan Pascasarjana Teknik Informatika Universitas Dian Nuswantoro
ABSTRACT SME on retail trading, especially consumer goods, have been give contribution onregional development and become a necessary bussiness. the characteristics of this bussiness are the trading have slow cycle and low margin but have very fastchange of price, it causes suplay problem is become very important. So, itbecomes very important to make any research about suplay technics to make moreoptimal. This research study about salesman tranportation technics to solvesequations with genetic algorithm.The route formulas which become cost study is time, where in equation solving have to fullfil some constrains where all customers must be visited and thecommodity carried not more than vehicle capasity. In this equation solving, thesalesmans will be got some illustrations for fullfil their duty to delivercommodities with minimal cost. This model is combined in information system as a decision support system by thesalesman, and then the simulations will be more realible. In this research alsostudy impact result by the system change after using Artificial Intelegent (AI) inthe company, so that the company can be made a decision to use the system ornot. Keywords: Artificial Intelegent, Genetic Algorithm, TSP, Consumer Good, Retail 1. LATAR BELAKANG Untuk kota Semarang terjadi peningkatan 8,5% pada bulan September 2009 dari bulan sebelumnya dan peningkatan 40,3% terhadap index tahunan pada bulan yang sama, dapat dilihat pada tabel . Hal ini menunjukan peningkatan yang signifikan yang menunjukan bisnis di bidang retail ini sangat menarik di Semarang. Dalam rangka untuk meningkatkan akurasi, maka dapat dibuat penelitian berdasarkan metode klasifikasi lengkap pelanggan untuk masalah umum yang dihadapi, kemudian menggabungkan dengan fungsi sistem informasi geografis kemudian skema tersebut dapat dibuat sebuah visualisasi. Model stokhastik pada masalah penjaluran kendaraan untuk meminimalisasi permintaan yang dijumpai dengan teknik pemrograman berdasarkan peluang, dimana dapat digunakan untuk penjaluran suplai untuk respon darurat dengan skala yang besar. Penambahan kompleksitas dalam metode ini mempertemukan panjang rute dari depot dengan jendela waktu dan biaya untuk menunggu, misalnya terjadi waktu tunggu atau kemacetan. Dalam uji komputasi yang dilakukan oleh Clara Novoa dkk (2006), dengan model Vehicle Routing Problem with Stochastic Demands(VRPSD). menunjukan kemampuan 5% dibandingkan dengan cara lama sebagai hasil dari beberapa konsumen yang tidak puas tiap rute yang diselesaikan dengan pelayanan tersebut. Daniela Favaretto dkk (2006), juga telah melakukan suatu percobaan yang menunjukan efisiensi penjaluran berdasarkan waktu (Vehicle Routing Problem with Time Windows/VRPTW). Dalam percobaan tersebut mereka mencoba salesman dengan 64 konsumen, hasilnya terdapat penambahan sekitar 3 konsumen dapat terlayani. 2. RUMUSAN MASALAH Berdasarkan latar belakang di atas, rumusan masalah yang akan diangkat adalah kurang optimalnya cost penjaluran salesman dalam hal penjaluran berdasarkan waktu, permintaan konsumen, dan penghindaran pengiriman kepada konsumen yang sama untuk menghindari persaingan antar salesman. 3. TUJUAN a. Mengoptimalkan kinerja salesman berdasarkan biaya waktu dan permintaan barang.
homepage: http://pps.dinus.ac.id email redaksi:
[email protected]
73
Jurnal Teknologi Informasi, Volume 6 Nomor 1, April 2010, ISSN 1414-9999 b. Mengetahui dampak dari model optimalisasi penjaluran berdasarkan permintaan dan waktu terhadap keterlaksanaan tugas pengiriman barang dan peningkatan jumlah permintaan. 4. MANFAAT 4.1. Bagi Salesman a. Membantu salesman memilih jalur yang paling optimal berdasarkan permintaan dan waktu yang ditempuh sehingga akan lebih banyak konsumen yang terlayani. b. Membantu salesman untuk memenuhi target penjualan dengan waktu yang relatif . c. Membantu para salesman dalam menganalisa pasar dan memutuskan jumlah barang yang akan dibawa untuk dijual. 4.2. Bagi Perusahaan a. Membantu meningkatkan efisiensi dari perusahaan sehingga laba perusahaan meningkat. b. Membantu perusahaan dalam memanajemen para salesmannya. 4.3. Bagi Akademik a. Menambah pengetahuan penjualan dalam bisnis penjualan consumer goods. b. Menambah pengetahuan dalam model penjaluran para salesman dalam bisnis consumer goods. 5. LANDASAN TEORI 5.1. Data Mining Data mining adalah proses pencarian data yang memiliki arti korelasi, pola dan trend dengan penyaringan melalui sejumlah data pada repositori, menggunakan teknologi seperti teknik statistik dan matematik pengetahuan Pola evaluasi Datamining Data relevant Seleksi dan transformasi Data warehouse
Data cleaning
Integrasi database Kumpulan database
Gambar 1. Data mining 5.2. Algoritma Genetik prosedur GA mulai t = 0; inisialisasi(P(t)); evaluasi(P(t)); perulangan (bukan kondisi akhir) mulai t = t + 1; Qs(t) = seleksi(P(t-1)); Qr(t) = rekombinasi(Qs(t)); P(t) = mutasi(Qr(t)); evaluasi(P(t)); selesai; selesai;
Gambar 2. Algoritma Genetik Umum
74
homepage: http://pps.dinus.ac.id email redaksi:
[email protected]
Jurnal Teknologi Informasi, Volume 6 Nomor 1, April 2010, ISSN 1414-9999 5.3.1. Inisialisasi Populasi awal dari solusi kandidat yang dihasilkan secara random, sesuai dengan fungsi-fungsi tujuan dan kendala yang sesuai dengan masalah yang ada. 5.3.2. Evaluasi Salah satu populasi diinisialisasi atau populasi offspring dibuat. Tahap ini berfungi untuk memperoleh fungsi fitness pada masing - masing fitness. Fungsi fitness ini diperoleh dari fungsi tujuan sesuai dengan masalah yang ada. Model yang digunakan adalah sebagai berikut: Fungsi tujuan: Fitness Min.
m
n
∑∑ c .x i =1 j =1
m
s.k.
ij
ij
∑x
ij
= 1 ; i = 1,2,3,...m
∑x
ij
= 1 ; j = 1,2,3,...m
∑q
j
i =1 m i =1 m
j =1
xij ≤ Q;
j = 1,2,..., m
Keterangan: cij = biaya yang dibutuhkan dari titik i ke titik j xij = jumlah kunjungan ke suatu titik bernilai 1 jika dikunjungi dan bernilai 0 jika tidak dikunjungi q = kebutuhan pada konsumen tujuan j Q =Total kapasitas kendaraan salesman 5.3.3. Seleksi Pemikiran utama dari seleksi adalah untuk mendapatkan solusi terbaik sampai terjelek. Pada penelitian ini metode yang digunakan adalah roda roulette. Seleksi ini bertujuan untuk memberikan kesempatan reproduksi lebih besar bagi anggota populasi yang memiliki fitness tinggi. Adapun algoritma seleksi roda roulette: a. Hitung total Fitness (F): Total Fitness=∑Fk; k=1,2,...,ukuranpopulasi b. Hitung Fitness Relatif tiap individu: pk=Fk/Total fitness c. Hitung Fitness komulatif • q1=p1 • qk=qk-1+pk; k=2,3,...,ukuran populasi d. Pilih induk yang akan menjadi kandidat untuk di rekombinasi/crossover dengan cara: • Bangkitkan bilangan random r. • Jika qk< r dan qk+1>r, maka pilih kromosom ke k+1 sebagai kandidat induk. 5.3.4. Rekombinasi/Crossover Crossover merupakan penyilangan induk yang dilakukan untuk membentuk keturunan yang baru. Crossover dilakukan antar dua individu. Metode yang dipilih dalam penelitian ini adalah order crossover. Penjelasan metode ini dapat dilihat sebagaimana gambar berikut. titik 1
Orang tua 1 Orang tua 2 Anak 1 Anak 2
titik 2
2 1 3 4 5 6 5 4 6 3 2 1 5 6 3 4 2 1 1 5 6 3 2 4 Gambar 3. Proses Crossover Menggunakan Metode Order Crossover
homepage: http://pps.dinus.ac.id email redaksi:
[email protected]
75
Jurnal Teknologi Informasi, Volume 6 Nomor 1, April 2010, ISSN 1414-9999
Dalam contoh di atas misalkan terpilih dua orang tua, dari hasil random [0,jumlahkons] terpilih dua titik untuk memisahkan rantai DNA pada suatu individu. kemudian proses bilangan random[0,1] untuk menentukan titik mana yang akan dipindah silangkan. maka hasilnya dapat dilihat pada gambar di atas. 5.3.5. Mutasi Model mutasi yang dilakukan adalah menggunakan swap mutation, dengan diberikan batasan dengan tipe individu yang sama. Misalkan terjadi konsumen 5 dan konsumen 3 mempunyai pesanan yang sama maka dapat dipertukarkan. 5 6 3 4 2 1 Kromosom awal Kromosom mutasi 3 6 5 4 2 1 Gambar 4. Proses Swap Mutation 6. KERANGKA PEMIKIRAN
Penelitian Awal: Data UKM, Salesman, posisi konsumen, gudang, waktu tempuh, kapasitas
Data Warehouse
Pemilihan data Analisa pasar
Data posisi, waktu, kapasitas max dll
komoditas
Metode penjaluran berdasarkan permintaan barang dan jendela waktu
Algoritma Genetik
Simulasi penjaluran Analisa Dampak
kesimpul Gambar 5. Kerangka pikiran
76
homepage: http://pps.dinus.ac.id email redaksi:
[email protected]
Jurnal Teknologi Informasi, Volume 6 Nomor 1, April 2010, ISSN 1414-9999 7. METODE PENELITIAN
Gambar 6. Algoritma Genetik pada Penelitian
homepage: http://pps.dinus.ac.id email redaksi:
[email protected]
77
Jurnal Teknologi Informasi, Volume 6 Nomor 1, April 2010, ISSN 1414-9999 8. HASIL DAN PEMBAHASAN Dari simulasi yang ada diperoleh jalur untuk masing – masing salesman adalah sebagai berikut. Tabel 1. Jalur Salesman 1 No. Jalur Salesman 1 1. 0=>39=>36=>35=>33=>34=>49=>48=>47 2. 0=>37=>40=>38 Total waktu Jalur Salesman 1= 93 menit
Total Barang Bawaan (pak) 190 pak 80 pak
No. Jalur Salesman 2 1. 0=>8=>10=>11=>12=>5=>4=>1 2. 0=>3=>9 Total waktu Jalur Salesman = 118 menit No. Jalur Salesman 3 1. 0=>17=>6=>2=>14=>13=>7=>15 2. 0=>18=>16 Total waktu Jalur Salesman 3= 119 menit
Total Barang Bawaan (pak) 180 pak 50 pak
No. Jalur Salesman 4 1. 0=>25=>23=>24=>19=>20=>21=>22 2. 0=>29=>27=>26=>28 Total waktu Jalur Salesman 4= 171 menit
Total Barang Bawaan (pak) 175 pak 115 pak
No. Jalur Salesman 5 1. 0=>30=>43=>50=>42=>41=>46=>45 2. 0=>44=>31=>32 Total waktu Jalur Salesman 5=152 menit
Total Barang Bawaan (pak) 175 70
Total Barang Bawaan (pak) 185 pak 50 pak
Untuk mengetahui dampak model terhadap perusahaan maka dibuat hipotesa sebagai berikut: H0 = Penerapan AI pada sistem penjaluran tidak memberikan dampak terhadap optimalisasi penjaluran. H1 = Penerapan AI pada sistem penjaluran memberikan dampak terhadap optimalisasi penjaluran. Dari analisa statistik di atas diperoleh hasil bahwa dengan menerapkan AI ke dalam sistem perusahaan dapat merubah pola kerja perusahaan menjadi lebih baik. Hal ini terlihat dari beberapa konsumen yang hanya kadang – kadang saja dikunjungi menjadi pasti terkunjungi sesuai data pada kuestioner dan simulasi. Dari data tersebut terdapat 4 konsumen saja yang kadang – kadang terkunjungi menjadi pasti terkunjungi. Efek lain dapat dilihat dari perubahan terpenuhinya kebutuhan konsumen oleh salesman. Dengan terpenuhinya kebutuhan konsumen maka diharapkan konsumen akan lebih puas, kemudian dengan puasnya konsumen maka akan terjadi peningkatan permintaan oleh konsumen. 9. KESIMPULAN DAN SARAN 9.1. Kesimpulan Dalam hal keterlaksanaan tugas, dengan jumlah sampel tersebut, penerapan AI mempunyai dampak sedikit signifikan dimana dari 4 konsumen yang kadang-kadang dikunjungi menjadi pasti terkunjungi oleh salesman. Dalam hal permintaan konsumen, terjadi peningkatan yang signifikan setelah penerapan AI terhadap metode penjaluran. Peningkatan permintaan ini dikarenakan semua konsumen terpenuhi jumlah permintaannya. 9.2.1.
Saran
9.2.1.1. Untuk Perusahaan Perusahaan sebaiknya menggunakan model penjaluran salesman yang terorganisir yang teroptimalisasi. Model penjaluran tersebut sebaiknya diintegrasikan dengan sistem informasi yang
78
homepage: http://pps.dinus.ac.id email redaksi:
[email protected]
Jurnal Teknologi Informasi, Volume 6 Nomor 1, April 2010, ISSN 1414-9999 digunakan oleh perusahaan. Jika ada waktu tersisa salesman sebaiknya mencari konsumen baru, sehingga dengan meningkatnya jumlah konsumen maka semakin banyak pendapatan perusahaan semakin meningkat. 9.2.1.2. Untuk Penelitian Selanjutnya Dalam pengembangan selanjutnya, berdasarkan kendala – kendala yang muncul di lapangan, diharapkan untuk merumuskan model optimasi diperhatikan faktor-faktor Waktu tunggu, kemungkinan gagal, waktu tunda, waktu maksimum, jenis barang dengan dengan volume dan beban berbeda, pengaruh jumlah pesanan yang dapat berubah setiap saat. DAFTAR PUSTAKA
[1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16]
http://www.bi.go.id Hu, Xiangpei dkk, (2006). ”An Intelligent Solution Form a Vehicle Routing Problem in Urban Distribution”. ICIC International Shen, Zhihong (2005).”The Minimum Unmet Demand Stochastic Vehicle Routing Problem”. USA:University of Southern California Bräysy, Olli, (2001).”Genetic Algorithm for the Vehicle Routing Problem with Time Windows”. Finland: University of Vaasa Oracle White Paper, (2005). ”Oracle Trade Management – Solution for the Consumer Goods Industry”. Oracle Novoa, Clara dkk, (2006).”A Set-Partitioning-Based Model for the Stochastic Vehicle Routing Problem”. USA: Texas State University Favaretto, Daniela dkk, (2006).” an Ant Colony System Approach for Variants of The Traveling Salesman Problem with Time Windows”. Venesia: Universit`a Ca’ Foscari di Venezia Pressman, Roger S., Ph.D., “Software Engineering: A Practitioner’s Approach -5th ed”, Boston: McGraw-Hill Budiyono, (2000). “Statistika Dasar Untuk Penelitian”, Surakarta: UNS Press Teguh Wahyono, (2008). ”Belajar Sendiri SPSS 16”, Jakarta: Elex Media Komputindo Suyanto, (2005). “Algoritma Genetik dalam MATLAB”. Yogyakarta: Penerbit ANDI Muhammad Muslich, (2009). “Metode Pengambilan Keputusan Kuantitatif”, Jakarta: Bumi Aksara Mak, K.L dkk (2004). ”a Genetic Algorithm for Vehicle Routing Problems With Stochastic Demand and Soft Time Windows”. Hongkong: University of Hong Kong Thangiah, S. R, (1998). “Vehicle Routing with Time Windows using Genetic Algorithms”, U.S.A: Slippery Rock University Zaïane, Osmar R. (1999). “Introduction to Data Mining”, Canada: University of Alberta Sri Kusumandari, Hari Purnomo, (2005). “Penyelesaian Masalah Optimasi dengan TeknikTeknik Heuristik”. Yogyakarta: Graha Ilmu
homepage: http://pps.dinus.ac.id email redaksi:
[email protected]
79