Penerapan Algoritma Genetika Untuk Permasalahan Distribusi Rantai Pasok Dua Tingkat Yang Dipengaruhi Oleh Biaya Tetap Novita M Mayasari1, Mahendrawathi Er, S.T, M.Sc, Ph.D1, Rully Soelaiman, S.Kom, M.Kom2 1
Jurusan Sistem Informasi, Institut Teknologi Sepuluh Nopember, Surabaya, Indonesia Jurusan Teknik Informatika, Institut Teknologi Sepuluh Nopember, Surabaya, Indonesia
2
Abstrak Permasalahan distribusi merupakan hal penting yang harus dipertimbangkan oleh perusahaan-perusahaan dalam sebuah jaringan rantai pasok. Hal ini dikarenakan sekitar 30% biaya produk ditimbulkan oleh biaya distribusi.Selain itu biaya distribusi juga memiliki peran yang penting dalam menentukan harga. Banyak permasalahan transportasi dan distribusi dapat dimodelkan sebagai permasalahan transportasi dengan biaya tetap. Permasalahan transportasi dengan biaya tetap merupakan perluasan dari permasalahan transportasi klasik dimana biaya tetapnya terjadi untuk setiap pasokan yang digunakan sebagai solusi Pada tugas akhir ini diajukan penggunaan algoritma genetika untuk menyelesaikan permasalahan distribusi rantai pasok dua tingkat yang dipengaruhi oleh biaya tetap. Dua jenis biaya yang dipertimbangkan dalam permasalahan transportasi dengan biaya tetap adalah (i) variable cost yaitu biaya yang meningkat seiring dengan jumlah produk yang diantarkan dari sumber ke tujuan, (ii) fixed cost yaitu biaya yang timbul setiap terjadi proses transportasi untuk sejumlah barang dari sumber ke tujuan. Tujuan yang ingin dicapai adalah untuk meminimalkan total biaya distribusi. Hasil yang diharapkan dapat diperoleh dari tugas akhir ini adalah sebuah implementasi dari algoritma genetika untuk menyelesaikan permasalahan distribusi rantai pasok dua tingkat yang dipengaruhi oleh biaya tetap. Hasil dari algoritma genetika ini akan dibandingkan dengan solusi yang dihasilkan menggunakan software TORA sehingga dapat diketahui bahwa algoritma ini mampu menyelesaikan persoalan distribusi dengan baik. Hal ini untuk kedepannya diharapkan dapat menjadi masukan untuk manajemen rantai pasok perusahaan dalam menghadapi permasalahan distribusi dan transportasi.
Kata Kunci : Permasalahan distribusi,Rantai pasok,Algoritma genetika,Biaya tetap ransportasi
1. PENDAHULUAN anajemen rantai pasok telah menjadi konsep penting di dunia bisnis dewasa ini [4]. Inti utama dari manajemen rantai pasok adalah proses distribusi. Distribusi adalah proses untuk memindahkan dan menyimpan barang mulai dari tingkat pemasok sampai ke tingkat pelanggan dalam rantai pasok [9]. Distribusi yang optimal akan menjadi kunci dari keberhasilan perusahaan dalam menjalankan bisnis, karena secara langsung proses distribusi akan berdampak pada biaya rantai pasok Salah satu permasalahan distribusi adalah strategi keputusan dalam menentukan rute pengiriman dan pengalokasian banyaknya produk yang harus dipindahkan mulai dari tingkat produksi hingga ke tingkat pelanggan. Banyak permasalahan transportasi dan distribusi dapat dimodelkan sebagai permasalahan transportasi dengan biaya tetap. Pada persoalan distribusi ini terdapat dua macam macam biaya yang berpengaruh (i) variable cost yaitu biaya yang meningkat seiring dengan jumlah produk yang diantarkan dari sumber ke tujuan, (ii) fixed cost yaitu biaya yang timbul setiap terjadi proses transportasi untuk sejumlah barang dari sumber ke tujuan. .Permasalahan distribusi banyak tingkat merupakan permasalahan umum dalam konteks jaringan rantai pasok, sedangkan sebagian besar dari penelitian yang telah dilakukan sebelumnya diarahkan pada permasalahan distribusi satu tingkat . Dengan pertimbangan diatas, tugas akhir ini memusatkan pada permasalahan distribusi dari tiga elemen rantai pasok yang melibatkan distribusi dua tingkat dan biaya tetap, dengan tujuan meminimumkan biaya total distribusi. Oleh karena itu digunakan algoritma genetika untuk menentukan total biaya distribusi yang paling optimal. Algoritma genetika ini sangat tepat digunakan untuk penyelesaian masalah optimasi yang kompleks dan sukar diselesaikan dengan metode konvensional.
2. DASAR TEORI
M
2.1 Persoalan Distribusi Persoalan transportasi membahas masalah pendistribusian suatu komoditas atau produk dari sejumlah sumber (supply) kepada sejumlah tujuan (destination, demand) dengan tujuan meminimumkan ongkos pengangkutan. Ciri-ciri khusus persoalan transportasi [11] adalah : Terdapat sejumlah sumber dan sejumlah tujuan tertentu. Kuantitas komoditas atau produk yang didistribusikan dari setiap sumber dan yang diminta oleh setiap tujuan, besarnya tertentu. Komoditas yang dikirim atau yang diangkut dari suatu sumber ke suatu tujuan, besarnya sesuai dengan permintaan dan atau kapasitas sumber. Ongkos pengangkutan komoditas dari suatu sumber ke suatu tujuan, besarnya tertentu. 2.2 Algoritma Genetika GA sebagai salah satu cabang dari algoritma evolusi merupakan metode adaptive yang biasa digunakan untuk memecahkan suatu pencarian nilai dalam sebuah masalah optimasi [8]. Peletak prinsip dasar sekaligus pencipta GA adalah John Holland. Algoritma ini didasarkan pada proses genetik yang ada dalam makhluk hidup yaitu perkembangan generasi dalam sebuah populasi yang alami, secara lambat laun mengikuti prinsip seleksi alam atau “siapa yang kuat, dia yang bertahan (survive)”. Dengan meniru proses ini, GA dapat digunakan untuk mencari solusi permasalahan-permasalahan dalam dunia nyata.
1
Model Persoalan Distribusi Rantai Pasok Model permasalahan distribusi rantai pasok disini dinyatakan sebagai permasalahan distribusi dua tingkat yang dipengaruhi biaya tetap. Dengan permodelan demikian maka akan terdapat dua tingkatan distribusi dimana tingkatan pertama dimulai dari pabrik (pemasok) ke pusat distribusi dan yang kedua dari pusat distribusi ke pelanggan. Demikian pula untuk biaya yang diperhitungkan, juga terdapat dua jenis biaya, yaitu variabel cost, biaya yang berubah-ubah tergantung pada jumlah yang ditransportasikan, dan yang kedua adalah fixed cost yaitu biaya tetap yang tidak akan berubah meskipun jumlah yang ditransportasikan bertambah atau berkurang. Model distribusi rantai pasok ini dapat dilihat pada gambar 3.1.
Algoritma ini bekerja dengan sebuah populasi yang terdiri dari individu-individu, yang masing-masing individu merepresentasikan sebuah solusi yang mungkin bagi persoalan yang ada. Dalam kaitan ini, individu dilambangkan dengan sebuah nilai fitness yang akan digunakan untuk mencari solusi terbaik dari persoalan yang ada. Algoritma genetika banyak digunakan untuk memecahkan masalah yang rumit dimana fungsi objektifnya tidak memiliki sifat-sifat yang ramah seperti sifat tidak kontinyu, tidak dapat di differensialkan ataupun saat pengetahuan tentang daerah asal (domain) sangat jarang atau bahkan tidak ada sehingga menyulitkan baik desain maupun analisis, pada saat itulah algoritma genetika akan terlihat keunggulannya. Pada umumnya GA akan melalui suatu siklus yang terdiri dari 4 fase [10], di antaranya: 1. Membangun sebuah populasi yang terdiri dari kromosom kromosom. 2. Mengevaluasi masing-masing kromosom. 3. Proses seleksi agar didapat kromosom yang terbaik. Manipulasi genetik untuk menciptakan populasi baru dari kromosom-kromosom 2.3 Mekanisme Kerja Algoritma Genetika Mekanisme yang ada dalam GA sangat sederhana, yaitu hanya melibatkan penyalinan string dan pertukaran bagian string. Siklus perkembangbiakan GA diawali dengan pembuatan himpunan solusi secara random dinamakan populasi, dimana di dalamnya terdapat individu-individu yang dinamakan kromosom. Kromosom ini secara lambat laun mengalami iterasi pemilihan dalam sebuah generasi. Selama dalam sebuah generasi, kromosom-kromosom ini dievaluasi, dengan menggunakan rumus-rumus yang ada dalam fungsi fitness. Untuk menciptakan generasi berikutnya dengan kromosom yang baru (dinamakan keturunan/offspring) dapat dilakukan dengan menggabungkan dua kromosom yang telah didapat sebelumnya dengan menggunakan operator pindah silang (crossover) ataupun dengan memodifikasi sebuah kromosom dengan menggunakan operator mutasi. Sebuah generasi baru sebelum dievaluasi lagi, maka dia melalui proses seleksi berdasarkan fungsi fitness-nya. Dari seleksi ini, kromosom-kromosom yang paling bagus mempunyai kemungkinan besar untuk terseleksi. Setelah beberapa generasi, algoritma akan mengalami konvergen pada sejumlah kromosom terbaik, yang memiliki nilai optimum dari permasalahan yang diselesaikan.
Gambar 3.1 Model Distribusi Rantai Pasok Berdasarkan gambar 3.1 dapat dijelaskan bahwa terdapat sejumlah p pabrik (pemasok atau gudang), sejumlah q pusat distribusi (gudang atau ritel) dan sejumlah r pelanggan (ritel atau pengguna akhir). Setiap pabrik dapat mengirimkan ke pusat distribusi yang mana pun dengan sejumlah Cij biaya transportasi (untuk setiap unit yang dikirim) ditambah dengan F ij biaya tetap. Setiap pusat distribusi dapat mengirimkan ke pelanggan yang mana pun dengan sejumlah Cjk biaya transportasi (untuk setiap unit yang dikirimkan) dan ditambah dengan Fjk biaya tetap. Setiap pabrik i=1,2,...p memiliki batasan pasokan Si dan setiap pelanggan k=1,2,...r memiliki jumlah permintaan D k . Setiap pusat distribusi j memiliki kapasitas penyipanan SCj . Asumsi Asumsi-asumsi yang digunakan pada persoalan ini adalah sebagai berikut: - Jumlah kapasitas sumber ≥ dari jumlah permintaan.
3. METODOLOGI Pada Bagian metodologi ini dibahas mengenai perancangan dan pembuatan siatem perangkat lunak. Perancangan yang dilakukan meliputi dua bagian penting, yaitu perancangan persoalan distribusi dan perancangan algoritma genetika.
p
S
r i
i 1
3.1 Desain Persoalan Distribusi Pada bagian ini akan dijelaskan terlebih dahulu model persoalan distribusi rantai pasok, asumsi-asumsi yang digunakan dan model matematika pada persoalan distribusi rantai pasok.
-
D
k
(1)
k 1
Kapasitas stok pada distribution center ≥ jumlah permintaan. r
SC j
D j, j 1 to q k
k 1
2
(2)
Model Matematika Model matematika pada persoalan distribusi rantai pasok yang dipengaruhi oleh biaya tetap ini adalah : Minimum p
Z=
q
C
q
ij
mulai
p, q, r , jum.Generasi, C ij , C jk , Fij , F jk , S i , Dk
r
X ij Fij ij C jk X jk F jk jk (3)
i 1 j 1
j 1 k 1
menghitung nilai CF jk dan CFij
Dengan Batasan : q
X
ij
(i, i 1 sampai p)
(4)
Dk ( k , k 1 sampai r)
(5)
Si
Inisialisasi populasi : Generate kromosom X jk
j 1 q
X
jk
Evaluasi : mengkodeka
j 1
X ij 0 , dan integer
n X
ij
(6)
X jk 0 , dan integer
Sorting: MencariMinZ , HitungZ
(7)
ij 0 jika X ij 0 , generasi 1
= 1 jika X ij 0 ,
best _ fitness min Z
X jk 0 . output :
Dari persamaan 3 hingga 7 telah dijabarkan mengenai fungsi tujuan serta batasan yang menjadi model matematis dari persoalan distribusi rantai pasok yang dipengaruhi oleh biaya tetap. Dari model matematis yang telah dijabarkan tersebut, diperoleh model matematis yang dapat digunakan pada algoritma genetika untuk menyelesaikan permasalahan yang sama. Hal tersebut dilakukan dengan merubah persamaan 3 menjadi model transportasi linier dengan cara mengabaikan nilai variable biner ( ij ) dan ( jk ) (Palekar et al., 1990;King, 1975) sehingga model matematika yang dihasilkan menjadi : Minimum p
Z=
q
q
i 1 j 1
Generasi jum.Generasi
CF jk C jk F jk / Min A j , Dk
(10)
Gambar 3.2 Diagram Alir Algoritma Genetika
1. Modul Input Data input yang digunakan untuk penerapan algoritma genetika pada persoalan distribusi ini dapat dilihat pada Tabel 3.2. 2. Inisialisasi Kromosom Representasi kromosom merupakan salah satu bagian terpenting dalam proses GA yang memberikan dampak pada hasil akhir dari metode GA tersebut. Dengan kata lain apabila representasi kromosom tidak tepat, maka hasil akhir yang diperoleh bisa jadi tidak sesuai dengan apa yang diharapkan. Proses untuk merepresentasikan permasalahan ke dalam kromosom biasa disebut sebagai proses encoding. Dalam permasalahan optimasi biaya pada permasalahan distribusi rantai pasok dua tingkat kromosom direpresentasikan sebagai matrix perencanaan distribusi. Perencanaan distribusi yang mungkin adalah yang memenuhi kebutuhan pelanggan dari pusat distribusi . Jadi kromosom akan berupa matrik ukuran j*k, dimana setiap elemennya merupakan gen. Pada sebuah gen baris ke-j dan kolom ke-k dari kromosom mengindikasikan jumlah unit Xjk yang didistribusikan kepada pelanggan k melalui pusat distribusi j. Populasi awal biasanya dibangkitkan secara acak. Namun beberapa studi menunjukkan bahwa pembangkitan populasi awal yang menyertakan beberapa
r
A j Dk ( j , j 1 sampai q )
selesai
mutasi
j 1 k 1
(9)
X ij _ opt , X jk _ opt , Z opt
crossover
(8)
CFij C ij Fij / MinS i , A j
tidak
ya
Seleksi
r
CFij X ij CF jk X jk
Dimana
membandingkan min Z dengan min Z generasisebelumnya
ya
jk 0 jika X jk 0 , = 1 jika
tidak
(11)
k 1
Berdasarkan pada persamaan 8 ini persoalan distribusi dua tingkat dapat diubah menjadi suatu bentuk ekuivalent persoalan distribusi satu tingkat. Sehingga persoalan distribusi satu tingkat ini juga memiliki ekuivalent matriks biaya distribusi. Ekuivalent matriks biaya distribusi ini dapat dilihat pada Tabel 3.1. Persamaan 8 inilah yang akan digunakan sebagai fungsi tujuan pada implementasi penyelesaian persoalan distribusi rantai pasok dua tingkat dengan biaya tetap dengan menggunakan algoritma genetika. 3.2 Desain Algoritma Genetika Desain algoritma genetika dapat dijelaskan dengan diagram alir pada Gambar 3..2. Langkah-langkah pada diagram alir ini adalah sebagai berikut : 3
solusi yang bagus, dapat meningkatkan konvergensi dari GA. Untuk meningkatkan keanekaragaman dari kromosom awal yang dibangkitkan, maka tiga kromosom dibangun dengan menerapkan prosedur alokasi biaya terendah dengan menggunakan aturan dan data diawah ini: Kromosom 1, di-generate dengan mengaplikasikan aturan biaya terkecil pada CFjk Kromosom 2, di-generate dengan mengaplikasikan aturan biaya terkecil pada Cjk Kromosom 3, di-generate dengan mengaplikasikan aturan biaya terkecil pada Fjk Kromosom 4-10, digenerate secara random. Kesepuluh kromosom yang dibangun merupakan populasi awal. Pengalokasian selesai dilakukan apabila permintaan pelanggan Dk terpenuhi.
Langkah 1: Menemukan jumlah unit yang dikirimkan dari setiap pusat distribusi. r
A j X jk ( j , j 1 sampai q) k 1
Langkah 2: Menemukan empat kemungkinan perencanaan distribusi dari pabrik ke pusat distribusi yang memenuhi kebutuhan dari Aj dengan menerapkan metode alokasi biaya berikut ini: Biaya terkecil pada CFij Biaya terkecil pada Cij Biaya terkecil pada Fij dan Random. Langkah 3:Evaluasi semua empat rencana distribusi dengan TC1 dan rencana distribusi terbaik Xij. Langkah 4:Menyimpan Xij terbaik. Setelah Xij ditentukan, maka nilai TC1 dapat dihitung dengan mensustitusikan nilai Xij kedalam persamaan 8, maka nilai fitness atau nilai Z dari kromosom tersebut dapat ditemukan. 4. Sorting Pada tahap ini, nilai fitness yang telah didapatkan dari proses evaluasi dipilih yang paling minimum. Nilai Z yang minimum disebut dengan best_fitness. Best_fitness ini akan dibandingkan dengan best_fitness generasi berikutnya sehingga akan menghasilkan best_fitness yang paling optimal. 5. Seleksi Tujuan utama proses seleksi ini adalah mempertahankan kromosom yang memiliki nilai fitness terbaik dan mengeliminasi kromosom yang memiliki nilai fitness buruk. Langkah-langkah proses seleksi ini adalah: - Mengkonversi nilai fitness masing-masing kromosom. Fungsi konversi yang digunakan adalah :
Tabel 3.2 Data Input No 1. 2. 3. 4. 5.
Nama Data
Keterangan
p q r Si Dk
6.
Cij
7.
Fij
8.
Cjk
Jumlah pabrik Jumlah pusat distribusi Jumlah pelanggan kapasitas pabrik ke-i Permintaan dari pelanggan k Biaya satuan distribusi produk dari pabrik i ke pusat distribusi j Biaya tetap yang mempengaruhi dengan setiap pengiriman dari pabrik i ke pusat distribusi j. Biaya satuan distribusi produk dari pusat distribusi j ke pelanggan k Biaya tetap yang mempengaruhi dengan setiap pengiriman dari pusat distribusi j ke pelanggan k. Jumlah Generasi Ukuran Populasi Probabilitas crossover Probabilitas mutasi
9.
Fjk
10. 11. 12. 13.
JumlahGenerasi pop_size p_cross p_mut
new_fit(c) = e
v* fit ( c )
(12) Keterangan : : eksponensial e : nilai pembeda antara kromosom v terbaik dari yang buruk dalam persoalan minimasi. Dalam persoalan ini ditetapkan v = 0.00005 sebagai pembeda terbaik. - Menghitung probabilitas kromosom. Pada langkah ini, new_fit (c) yang dihasilkan digunakan untuk menemukan frekuensi yang diharapkan atau probabilitas seleksi p(c) tiap kromosom. Probabilitas seleksi pada tiap kromosom ini dapat dihitung dengan persamaan 13.
3. Evaluasi Kromosom Pada tahap evaluasi ini adalah menentukan nilai fitness masing-masing kromosom. Nilai fitness adalah total biaya distribusi (Z) dari pabrik ke pelanggan melalui pusat distribusi. Nilai Z diperoleh dengan menjumlahkan total biaya distribusi dari pabrik ke pusat distribusi (TC1) dan total biaya distribusi dari pusat distribusi ke pelanggan (TC2). Langkah pertama proses evaluasi ini adalah menghitung nilai TC2, yaitu dengan mensubstitusikan nilai Xjk pada masing-masing kromosom ke dalam persamaan 8. Langkah selanjutnya adalah menghitung nilai TC1,dalam rangka menemukan nilai TC1, perencanaan distribusi Xij dibutuhkan. Prosedur dibawah ini diambil untuk mendapatkan tabel Xij :
pop _ size
p c new _ fit c /
new _ fit c
(13)
c 1
-
Memilih kromosom baru Pada langkah ketiga ini bertujuan untuk memilih kromosom baru pada generasi berikutnya. Metode pemilihan yang digunakan adalah Roulette Wheel. Sehingga langkah selanjutnya adalah menghitung probabilitas kumulatif dengan persamaan 14 c
cp c pc c 1
4
(14)
Kemudian tentukan bilangan R secara acak untuk tiap kromosom. Selanjutnya kromosom yang terpilih adalah kromosom yang memiliki nilai R sesuai dengan bentuk persamaan 15. cp c 1 R cp(c) (15) Pada proses ini kromosom yang memiliki nilai fitness baik akan terpilih dan kromosom yang memiliki nilai fitness buruk akan ditolak.
operator crossover yang digunakan pada tugas akhir ini adalah operator PMX (partially mapped crossover) dengan dua titik potong. Dua titik potong ini ditentukan dengan men-generate secara random jumlah customer (k). sehingga gen yang berada pada dua titik potong tersebut dipindah silang sehingga menghasilkan kromosom anak. Proses operasi crossover dapat lebih jelas dilihat pada tabel 3.4. 7. Mutasi Tujuan dari mutasi adalah menjaga keanekaragaman dan menghindari terjadinya solusi lokal seperti mengenalkan gen baru atau menciptakan ulang dari gen yang bagus. Parameter utama yaitu probabilitas mutasi (p_mut). Untuk melakukan mutasi secara efektif, efek dari mutasi haruslah besar dengan begitu kemungkinan p_mut haruslah tinggi. Pada tugas akhir ini nilai p_mut diasumsikan 0.5. langkah-langkah melakukan proses mutasi adalah: Tentukan bilangan random R_mut untuk tiap gen. Bandingkan R_mut tiap gen dengan p_mut. Jika R_mut < p_mut maka lakukan proses mutasi pada gen yang terpilih. Operasi mutasi dapat lebih jelas dilihat di Tabel 3.3. 8. Output Pada tahapan output ini akan ditampilkan hasil implementasi algoritma genetika pada permasalahan distribusi rantai pasok yang dipengaruhi oleh biaya tetap. Hasilnya berupa nilai dari fitness teroptimal yang merupakan nilai Zopt atau nilai biaya distribusi total. Selain itu, akan ditampilkan juga kromosom yang menghasilkan fitness optimal yang menggambarkan perencanaan distribusi terbaik, berupa Xijopt dan Xjkopt .
6. Crossover Modul seleksi tidak dapat membuat solusi baru pada populasi tetapi hanya membuat banyak salinan dari solusi bagus dengan mengorbankan solusi yang tidak terlalu bagus. Untuk membuat solusi baru dilakukan modul crossover dan mutasi. Kemungkinan dari crossover (p_cross) merupakan parameter yang penting pada operasi crossover. Pada tugas akhir ini nilai dari p_cross diasumsikan 0.3, sehingga setidaknya 30% kromosom yang terpilih oleh modul seleksi akan menjalani crossover dan menghasilkan offspring. Operasi crossover akan menghasilkan anak baru dari orang tua. Gen baru untuk anak (offspring) memiliki karakteristik kombinasi dari ortu (parent). Modul crossover terdiri dari dua tahapan: Pemilihan kromosom yang akan di-crossover , dengan cara : 1. Tentukan angka secara acak R_cross untuk semua kromosom. 2. Bandingkan R_cross masing-masing kromosom dengan p_cross. Jika R_cross < p_cross maka kromosom tersebut terpilih untuk di-crossover. 3. Jika jumlah kromosom yang terpilih ganjil, ulangi langkah1 sampai jumlah kromosom genap. Operasi crossover Tabel 3.1 Ekuivalent Matriks Biaya Distribusi Distribution Centre Customer Slack Supply 1 2 j q 1 2 k r 1 CF11 CF12 CF1j CF1q M M M M 0 S1 2 CF CF CF CF M M M M 0 S2 21 22 2j 2q Plant i CFi1 CFi2 CFij CFiq M M M M 0 Si p CFp1 CFp2 CFpj CFpq M M M M 0 Sp 1 0 M M M CF11 CF12 CF1k CF1r 0 A1 2 M 0 M M CF21 CF22 CF2k CF2r 0 A2 DC j M M 0 M CFj1 CFj2 CFjk CFjr 0 Aj q M M M 0 CFq1 CFq2 CFqk CFqr 0 Aq Req A1 A2 Aj Aq D1 D2 D3 D4 S Keterangan : M = angka yang sangat besar CFij = ekuivalent matriks biaya dari Plant ke Distribution Center, nilai ini didapatkan berdasarkan persamaan 9 CFjk = ekuivalent matriks biaya dari Distribution Center ke Customer, nilai ini didapatkan berdasarkan persamaan 10 Aj = jumlah unit yang dikirimkan melalui Distribution Center j, nilai ini didapatkan berdasarkan persamaan 11 S = S i Dk Tabel 3.3 Operasi Mutasi C’’
X jk
1’
j 1 2 3
X jk sesudah
sebelum dimutasi 1 0 150 0
2 80 0 0
k 3 0 100 0
J 4 0 270 0
1 2 3
5
C’’
dimutasi k
1 0 150 0
2 0 80 0
1’’ 3 0 100 0
4 0 0 270
Tabel 3.4 Operasi Crossover C’
X jk
1’
j
k 1 0 150 0 k 1 0 0 150
1 2 3 j
2’
Cut point 2,3
sebelum crossover
1 2 3
2 0 80 0
3 100 0 0
4 0 270 0
2 80 0 0
3 0 100 0
4 0 0 270
1 2
400 25
900 5
200 35
1300 14
1 Fjk = 500 Cjk = 43
j 2 2250 20
400 60
150
1200 25
1500 5
1800 32
80
k 1 2
Si 3 1150 30
250 350 Dk
3
3
800 10
0 0
2300 50
100
4
2000 50
2000 30
1000 40
270
k 1 0 150 0 k 1 0 0 150
1’ 2 80 0 0
3 0 100 0
4 0 270 0
2 0 80 0
3 100 0 0
4 0 0 270
2’
Pada ujicoba parameter ini akan digunakan 3 data uji untuk mewakili permasalahan ukuran kecil, sedang, dan besar. Sedangkan untuk skenario ujicoba, terdapat 4 skenario yang akan menguji masing-masing parameter. Setiap uji coba pada tiap-tiap skenario akan dijalankan sebanyak 10 kali untuk setiap ujicoba . Hasil keluaran dari tiap uji coba akan dievaluasi dengan cara melihat grafik nilai minimum serta rata-rata nilai dari tiap uji coba, berikut empat skenario tersebut. 1. Ujicoba Ukuran Populasi. Uji coba dilakukan untuk melihat pengaruh ukuran populasi dalam membantu untuk mendapatkan solusi yang optimal. Nilai untuk ukuran populasi dibuat berbeda dimulai dari yang paling kecil, 10, hingga yang paling besar, 200. Dari uji coba ini dapat dianalisa bahwa pengaruh ukuran populasi pada semua jenis data terhadap nilai terbaik stabil dari ukuran populasi terkecil hingga terbesar. Sedangkan rata-rata nilai pada data besar akan cenderung lebih minimum seiring bertambahnya ukuran populasi. Waktu komputasi berbanding lurus dengan ukuran populasi. Langkah ujicoba skenario 1 beserta hasilnya dapat dilihat pada tabel 4.2, 4.3 dan 4.4.
Tabel 4.1 Data Uji Coba j 2
j
1 2 3
Tahap uji coba dilakukan pada prosesor Intel(R) Core(TM) Duo CPU T5450 @ 1.66 GHz, memory sebesar 1.00 GB dan perangkat lunak berupa Sistem Operasi Windows XP Professional dan Matlab 7.0.4. Uji coba dapat dilakukan pada data yang terdapat pada Tabel 4.I. Data uji coba ini adalah berupa tabel biaya distribusi dan biaya tetap dari plant ke customer melalui Distribution Center. Tujuan dari pelaksanaan ujicoba ini dimaksudkan untuk melihat tingkat keakurasian solusi yang dihasilkan oleh aplikasi . Sedangkan untuk mengetahui pengaruh parameter algoritma genetika terhadap solusi yang dihasilkan serta waktu komputasi yang dibutuhkan, akan dilakukan ujicoba parameter.
1 Fij = 1000 Cij = 10
C’’
setelah crossover
1 2 3 j
4. HASIL UJI COBA DAN EVALUASI
i
X jk
Tabel 4.2 Hasil Ujicoba Parameter Ukuran Populasi Permasalahan kecil Parameter Ukuran populasi Maksimal generasi Pc Pm
Keterangan : i = identifikasi dari plants/pabrik (i = 1 sampai p) j = identifikasi dari distribution center (j =1 sampai q) k = identifikasi dari customer (k = 1 sampai r) Si = persediaan pada plant i Dk = permintaan pada customer k
MinZ Waktu(s)
Uji1
Uji2
Uji3
Uji4
Uji5
10
50
100
150
200
250
250
250
250
250
0.5 0.5 112600 2.9973
0.5 0.5 112600 12.8422
0.5 0.5 112600 25.3251
0.5 0.5 112600 37.9734
0.5 0.5 112600 50.7807
Tabel 4.3 Hasil Ujicoba Parameter Ukuran Populasi Permasalahan sedang Parameter
4.1 Skenario Uji Coba Parameter Pada tahap ini akan dilakukan uji coba dan evaluasi terhadap aplikasi dengan tujuan untuk melihat pengaruh parameter-parameter algoritma genetika, yaitu ukuran populasi, maksimal generasi, probabilitas pindah silang (p_cross), dan probabilitas mutasi (p_mut) dalam membantu mendapatkan solusi yang optimal serta pengaruhnya terhadap waktu komputasi.
Ukuran populasi Maksimal generasi Pc Pm MinZ Waktu(s)
6
Uji1
Uji2
Uji3
Uji4
Uji5
10
50
100
150
200
250
250
250
250
250
0.5 0.5 64743
0.5 0.5 64743
0.5 0.5 64743
0.5 0.5 64743
0.5 0.5 64743
3.5688
15.8886
31.5596
47.8484
63.965
3. Tabel 4.4 Hasil Ujicoba Parameter Ukuran Populasi Permasalahan besar Parameter Ukuran populasi Maksimal generasi Pc Pm MinZ Waktu(s)
2.
Uji1
Uji2
Uji3
Uji4
Uji5
10
50
100
150
200
250
250
250
250
250
0.5 0.5 73195 5.0967
0.5 0.5 73195 23.5773
0.5 0.5 73195 46.5218
0.5 0.5 73195 70.7649
0.5 0.5 73195 91.9901
Ujicoba Maksimal Generasi Uji coba dilakukan untuk melihat pengaruh maksimal generasi dalam membantu untuk mendapatkan solusi yang optimal. Nilai untuk maksimal generasi dibuat berbeda dimulai dari yang paling kecil, 50, hingga yang paling besar, 500. Pada ujicoba skenario 2 dapat dianalisa pengaruh maksimal Generasi pada semua jenis data nilai terbaik stabil dari maksimal generasi terkecil hingga terbesar. Rata-rata nilai pada data besar akan cenderung lebih minimum seiring bertambahnya maksimal generasi. Waktu komputasi berbanding lurus dengan ukuran maksimal generasi. Langkah ujicoba skenario 2 beserta hasilnya dapat dilihat pada tabel 4.5, 4.6 dan 4.7.
Tabel 4.8 Hasil Ujicoba Parameter Probabilitas Pindah Silang Permasalahan kecil Parameter Ukuran populasi Maksimal generasi Pc Pm MinZ Waktu(s)
Uji1
Uji2
Uji3
Uji4
100
100
100
100
50
150
250
350
0.5 0.5 112600 5.3728
0.5 0.5 112600 15.3497
0.5 0.5 112600 25.3376
0.5 0.5 112600 35.2962
Parameter
Uji5 100
Ukuran populasi Maksimal generasi Pc Pm MinZ
500 0.5 0.5 112600 50.3103
Waktu(s)
Tabel 4.6 Hasil Ujicoba Parameter Maksimal Generasi Permasalahan sedang Parameter Ukuran populasi Maksimal generasi Pc Pm MinZ Waktu(s)
Uji1
Uji2
Uji3
Uji4
100
100
100
100
50
150
250
350
0.5 0.5 64743 6.5367
0.5 0.5 64743 18.6918
0.5 0.5 64743 30.8619
0.5 0.5 64743 43.1208
Uji1
Uji2
Uji3
Uji4
100
100
100
100
50
150
250
350
0.5 0.5 73195 9.7382
0.5 0.5 73195 27.8216
0.5 0.5 73195 45.3624
0.5 0.5 73195 63.4823
Uji2
Uji3
Uji4
Uji5
100
100
100
100
100
250
250
250
250
250
0.1 0.5 112600 25.1411
0.3 0.5 112600 25.129
0.5 0.5 112600 25.2814
0.7 0.5 112600 25.358
0.9 0.5 112600 25.4095
Uji5
Uji1
Uji2
Uji3
Uji4
100
100
100
100
100
250
250
250
250
250
0.1 0.5
0.3 0.5
0.5 0.5
0.7 0.5
0.9 0.5
64743
64
6474
64743
64743
30.7726
30.6419
30.8067
30.9988
31.2038
Tabel 4.10 Hasil Ujicoba Parameter Probabilitas Pindah Silang Permasalahan besar
Uji5 100
Parameter Ukuran populasi Maksimal generasi Pc Pm MinZ Waktu(s)
500 0.5 0.5 64743 61.2158
Tabel 4.7 Hasil Ujicoba Parameter Maksimal Generasi Permasalahan besar Parameter Ukuran populasi Maksimal generasi Pc Pm MinZ Waktu(s)
Uji1
Tabel 4.9 Hasil Ujicoba Parameter Probabilitas Pindah Silang Permasalahan sedang
Tabel 4.5 Hasil Ujicoba Parameter Maksimal Generasi Permasalahan kecil Parameter Ukuran populasi Maksimal generasi Pc Pm MinZ Waktu(s)
Ujicoba Probabilitas Pindah Silang. Uji coba dilakukan untuk melihat pengaruh probabilitas pindah silang dalam membantu untuk mendapatkan solusi yang optimal. Nilai untuk probabilitas pindah silang dibuat berbeda dimulai dari yang paling kecil, 0.1, hingga yang paling besar, 0.9. Pada ujicoba skenario 3 dapat dianalisa pengaruh probabilitas crossover yang semakin tinggi akan mempengaruhi besarnya ruang explorasi yang lebih luas karena kemungkinan kromosom yang terpilih lebih banyak. Nilai terbaik stabil dari Pc terkecil hingga terbesar, rata rata nilai cenderung turun seiring bertambahnya nilai Pc. Waktu komputasi cenderung naik dengan bertambahnya nialai Pc. Langkah ujicoba skenario 3 beserta hasilnya dapat dilihat pada tabel 4.8, 4.9 dan 4.10.
4.
Uji5 100 500 0.5 0.5 73195 90.4868
7
Uji1
Uji2
Uji3
Uji4
Uji5
100
100
100
100
100
250
250
250
250
250
0.1 0.5 73195 46.8601
0.3 0.5 73195 47.1583
0.5 0.5 73195 46.1526
0.7 0.5 73195 46.8344
0.9 0.5 73195 47.162
Ujicoba Probabilitas Mutasi. Uji coba dilakukan untuk melihat pengaruh probabilitas mutasi dalam membantu untuk mendapatkan solusi yang optimal. Nilai untuk probabilitas mutasi dibuat berbeda dimulai dari yang paling kecil, 0.1, hingga yang paling besar, 0.9. Pada ujicoba skenario 4 dapat dianalisa probabilitas mutasi yang semakin besar akan menyebabkan kemungkinan gen yang terpilih untuk dimutasi semakin banyak. Nilai terbaik stabil dari Pm terkecil
hingga terbesar, rata-rata nilai cenderung stabil hingga Pm 0.5, kemudia akan mengalami peningkatan. Waktu komputasi cenderung naik dengan bertambahnya nilai Pm. Langkah ujicoba skenario 3 beserta hasilnya dapat dilihat pada tabel 4.11, 4.12 dan 4.13 .
Solusi yang dihasilkan dihitung presentase selisih dari keduanya dengan menggunakan persamaan 5.1 .
% Deviation
Berdasarkan hasil uji coba yang telah dilakukan telah dibuktikan bahwa implementasi dari algoritma genetika mampu menghasilkan solusi yang optimal untuk menyelesaikan persoalan distribusi rantai pasok dua tingkat dengan biaya teteap. Hasil uji coba ini dibandingkan dengan solusi optimal yang telah dijalankan dengan TORA. Tabel 5.1 dan Gambar 5.1 akan menunjukkan perbandingan hasil solusi yang didapatkan dari algoritma genetika dan TORA. Berdasarkan pada Tabel 5.1 diatas dapat dilihat bahwa dari 21 data yang ada, 8 data hasil yang diperoleh GA lebih bagus dari TORA dengan presentase selisih 0.003%, dan 12 data tidak lebih baik dari TORA dengan presentase selisih 1.37%, serta satu data memberikan hasil yang sama antara TORA dengan GA. Hasil GA yang lebih minimum ini dimungkinkan terjadi dikarenakan implementasi pada TORA dan GA menggunakan fungsi tujuan yang berbeda. Pada Tora digunakan persamaan 3, sedangkan pada GA digunakan persamaan 8.
Tabel 4.11 Hasil Ujicoba Parameter Probabilitas Mutasi Permasalahan kecil Parameter Uji1 Uji2 Uji3 Uji4 Uji5 Ukuran 100 100 100 100 100 populasi Maksimal 250 250 250 250 250 generasi Pc 0.5 0.5 0.5 0.5 0.5 Pm 0.1 0.3 0.5 0.7 0.9 MinZ 112600 112600 112600 112600 112600 Waktu(s) 23.0966 25.0982 25.2811 25.2013 25.4193 Tabel 4.12 Hasil Ujicoba Parameter Probabilitas Mutasi Permasalahan sedang Parameter Uji5 Uji1 Uji2 Uji3 Uji4 Ukuran populasi Maksimal generasi Pc Pm MinZ Waktu(s)
100
100
100
100
100
250
250
250
250
250
0.5 0.1
0.5 0.3
0.5 0.5
0.5 0.7
0.5 0.9
64743
64743
64743
64743
64743
30.6387
30.6802
30.7785
31.0685
31.2798
(GA TORA) 100 TORA
Tabel 5.1 Perbandingan Hasil No
Uji Coba
Solusi
1
Data 1
TORA 31521.3
AG 31910
388.7
Persentase selisih (%) 1.233
2
Data 2
112603.3
112600
-3.25
-0.003
3 4
Data 3 Data 4
237763.5 173881
237750 173878.6
-13.5 -2.43
-0.006 -0.001
5 6 7
Data 5 Data 6 Data 7
157055 161711.4 56022.2
157050 161876.5 56020
-5 165.09 -2.2
-0.003 0.102 -0.004
8 9 10 11
Data 8 Data 9 Data 10 Data 11
31521.3 64741.85 253413 74652
31910 64743.04 254530 76212.5
388.7 1.19 1117 1560.5
1.233 0.002 0.441 2.090
12 13 14
Data 12 Data 13 Data 14
73199 45458.3 169825
73195 47140 169825
-4 1681.7 0
-0.005 3.699 0.000
15 16
Data 15 Data 16
52591.5 151394.6
53996.67 151394.3
1405.17 -0.31
2.672 0.000
17
Data 17
132893.6
132890
-3.6
-0.003
18 19
Data 18 Data 19
93105 279513.5
97707.12 279675.6
4602.12 162.08
4.943 0.058
20 21
Data 20 Data 21
71455.5 118443
71463.5 118450
8 7
0.011 0.006
Selisih
Tabel 4.13 Hasil Ujicoba Parameter Probabilitas Mutasi Permasalahan besar. Parameter Uji1 Uji2 Uji3 Uji4 Uji5 Ukuran 100 100 100 100 100 populasi Maksimal 250 250 250 250 250 generasi Pc 0.5 0.5 0.5 0.5 0.5 Pm 0.1 0.3 0.5 0.7 0.9 MinZ 73195 73195 73195 73195 73195 Waktu(s) 35.5287 43.9123 45.5875 45.9305 45.4832
4.2 Skenario Uji Coba Akurasi GA termasuk salah satu metode heuristik untuk menyelesaikan permasalahan optimasi. Hasil yang diperoleh melalui metode ini tidak selalu tepat sama dengan hasil dari metode konvensional. Namun bisa didapatkan hasil yang mendekati nilai optimal. Pada bagian ini akan dipaparkan mengenai ujicoba tingkat akurasi solusi yang dihasilkan oleh aplikasi dengan menggunakan metode genetic algoritma. Untuk mengetahui tingkat akurasi dari aplikasi yang dihasilkan dengan menggunakan GA, maka solusi-solusi yang diperoleh dari aplikasi dibandingkan dengan solusi yang dihasilkan menggunakan TORA. Oleh karena hal tersebut maka pada tahapan ini akan terdapat dua skenario ujicoba yang akan dilakukan : 1. Skenario uji coba menggunakan TORA. 2. Skenario uji coba menggunakan input parameter algoritma genetika, yaitu jumlah kromosom = 10, probabilitas crossover = 0.3, probabilitas mutasi = 0.5 dan maksimal generasi = pq+qr.
Dapat dilihat pada Tabel 5.1, pada beberapa data selisih antara GA dan TORA memiliki prosentase yang lebih besar dibandingkan lainnya, apabila ditinjau dengan data yang digunakan, selisih yang besar tersebut tidak dipengaruhi oleh ukuran persoalan maupun jumlah entitas pada setiap level. Hal ini dapat diartikan bahwa baik data 8
berukuran kecil, sedang maupun besar, memungkinkan hasil dengan selisih yang besar maupun kecil.
6. DAFTAR PUSTAKA
Gambar 5.1 Grafik Perbandingan Hasil TORA-GA Apabila dilihat secara keseluruhan, selisih antara GA dan TORA tidak terlampau jauh. Gambar 5.1 menunjukkan grafik perbandingan hasil memperlihatkan bahwa hasil perhitungan persoalan distribusi di TORA dan AG hampir sama. 5. KESIMPULAN Kesimpulan yang dapat diambil dari pengerjaan Tugas Akhir ini adalah: 1. Algoritma Genetika ini dapat menyelesaikan persoalan distribusi dengan menghasilkan solusi yang mendekati akurat jika dibandingkan TORA yang terlihat dari nilai rata-rata prosentase selisihnya sebesar 1.37% tidak lebih baik dari TORA 2. Performansi Algoritma Genetika dipengaruhi oleh beberapa parameter yaitu: Ukuran populasi : pada semua jenis data nilai terbaik stabil dari ukuran populasi terkecil hingga terbesar. Rata-rata nilai pada data besar akan cenderung lebih minimum seiring bertambahnya ukuran populasi. Waktu komputasi berbanding lurus dengan ukuran populasi. Maksimal Generasi : pada semua jenis data nilai terbaik stabil dari maksimal generasi terkecil hingga terbesar. Rata-rata nilai pada data besar akan cenderung lebih minimum seiring bertambahnya maksimal generasi. Waktu komputasi berbanding lurus dengan ukuran maksimal generasi. Probabilitas crossover : probabilitas crossover yang semakin tinggi akan mempengaruhi besarnya ruang explorasi yang lebih luas karena kemungkinan kromosom yang terpilih lebih banyak. Nilai terbaik stabil dari Pc terkecil hingga terbesar, rata rata nilai cenderung turun seiring bertambahnya nilai Pc. Waktu komputasi cenderung naik dengan bertambahnya nialai Pc. Probabilitas mutasi : probabilitas mutasi yang semakin besar akan menyebabkan kemungkinan gen yang terpilih untuk dimutasi semakin banyak. Nilai terbaik stabil dari Pm terkecil hingga terbesar, rata-rata nilai cenderung stabil hingga Pm 0.5, kemudia akan mengalami peningkatan. Waktu komputasi cenderung naik dengan bertambahnya nilai Pm.
9
[1]
Adlakha, V., dan Kowalski, K.,1999. “On The Fixed Charge Transportation Problem”. OMEGA 27, 381-388.
[2]
Arhami, Muhammad., dan Desiani, Anita.2005. Pemrograman MATLAB. Yogyakarta: ANDI.
[3]
Busetti,Franco. Italia
[4]
Chopra, Sunil, dan Meindl, Peter. 2001. Supply Chain Management: Strategy, Planning, and Operation. New Jersey: Prentice-Hall.
[5]
Gen, M. dan Cheng, R. 1997. Genetic Algorithm and Engineering Design. New York : John Wiley & Sons, Inc.
[6]
Jawahar, N., dan Balaji, A.N., 15 Desember 2007. “A genetic algorithm for two-stage supply chain distribution problem associated with a fixed charge ”. European journal of Operational Research 194, 496-537.
[7]
Markos, Sibel. 2008. Crossover Operators. URL:http://www.google.com
[8]
Melanie, Mitchell. 1999. An Introduction to Genetic Algorithms. Massachusetts: MIT Press.
[9]
Pujawan, I Nyoman. 2005. Supply Chain Management. Surabaya : ITS.
[10]
Suyanto. 2005. GA dalam Matlab. Yogyakarta: ANDI.
[11]
Taha, Hamdi A. 1982. Operation Research : An Introduction,edisi ke-3.Macmillan Publishing Co.Inc. .New York.
Genetic Algorithm Overview.
