PENGEMBANGAN ALGORITMA BEE SWARM OPTIMIZATION UNTUK PENYELESAIAN CONTAINER STOWAGE PROBLEM Fiqihesa Putamawa dan Budi Santosa Jurusan Teknik Industri Institut Teknologi Sepuluh Nopember (ITS) Surabaya Kampus ITS Sukolilo Surabaya 60111 Email:
[email protected] ;
[email protected]
Abstrak (11 pt, bold) Container Stowage Problem (CSP) merupakan permasalahan penataan container ke dalam kapal dengan memperhatikan aturan penataan container dalam kapal. Aturan penataan tersebut, misalnya letak container harus sesuai dengan tipe dan ukuran container, container yang lebih berat diletakkan di bawah container yang lebih ringan, serta dalam proses penataan harus memperhatikan keseimbangan kapal. Tujuan permasalahan ini adalah meminimasi jumlah shifting sehingga diperoleh waktu unloading yang minimum. Dalam penelitian ini, diusulkan algoritma Bee Swarm Optimization (BSO) untuk menyelesaikan permasalahan tersebut. Algoritma yang diusulkan telah diaplikasikan untuk 5 macam kasus mulai 100 container (138 TEU) hingga 140 container (185 TEU). Hasil algoritma ini cukup kompetitif untuk kasus kecil dan sedang, sehingga algoritma ini dapat diaplikasikan untuk menyelesaikan permasalahan Container Stowage Problem. Kata kunci : container stowage problem, bee swarm optimization ABSTRACT Container Stowage Problem (CSP) is a problem how to arrange the containers into the vessel which regard the container ship stowage rules. The container ship stowage rules are : container’s location must conform with its type and size, the heavier container must be placed under the lighter container, and we must regard the vessel’s equilibrium when we arrange the containers. The purpose of this problem is minimizing the shifting so that obtained the minimum unloading time. This research propose Bee Swarm Algorithm for Container Stowage Problem. That algorithm has applied for 5 cases with 100 container (138 TEU) until 140 container (185 TEU). The solution result of proposed algorithm is competitive for small case and medium case. So, Bee Swarm Optimization can be applied for Container Stowage Problem. Keywords: container stowage problem, bee swarm optimization
1. Pendahuluan Pengiriman barang menggunakan container melalui jalur laut masih menjadi prioritas utama. Terutama untuk pengiriman barang dalam jumlah besar dan jarak jauh karena tidak ada pilihan lain yang lebih aman. Tidak adanya pilihan lain dalam pengiriman menyebabkan permintaan pengiriman container melalui jalur laut sangat tinggi. Sebuah kapal pengangkut container dapat mengangkut lebih dari 5000 container dan mengunjungi 10-25 pelabuhan (Dubrovsky et al, 2002). Menata 5000 container yang memiliki 10-25 tujuan bukan permasalahan yang mudah diselesaikan karena container dengan tujuan awal seharusnya diletakkan di atas
container dengan tujuan akhir sehingga dapat meminimalisasi jumlah shifting. Container Stowage Problems (CSP) merupakan permasalahan penataan container ke dalam kapal dengan memperhatikan aturan penataan container dalam kapal. Aturan penataan tersebut, misalnya letak container harus sesuai dengan tipe dan ukuran container, container lebih berat diletakkan di bawah container yang lebih ringan, serta dalam proses penataan harus memperhatikan keseimbangan kapal. Penataan ribuan container yang memiliki puluhan tujuan dengan memperhatikan ukuran, tipe, berat dan keseimbangan kapal, akan memunculkan banyak kemungkinan yang susah
diselesaikan secara eksak (combinatorial problems). Dari sekian banyak kombinasi, ada kombinasi yang tidak mungkin bisa dilakukan sehingga ketika kombinasi itu dijalankan harus dilakukan re-unloading agar sebanyak mungkin container bisa masuk ke dalam kapal. Maka dari itu, dilakukan pendekatan heuristik untuk penataan container sehingga jumlah reunloading atau shifting menjadi minimal. Menggunakan pendekatan heuristik karena problem penataan container ini termasuk NPHard Problem sehingga penyelesaian terbaik dengan metode heuristik (Avriel, 2000). Untuk kasus CSP, telah banyak dilakukan penelitian sebelumnya dengan bermacam-macam metode, antara lain Genetic Algorithm (Dubrovsky et al, 2002; Imai et al, 2002; Martins et al, 2009), Linear Programming (Ambrosino et al, 2004; Li et al, 2008), dan Ant Colony Optimization (Ambrosino et al, 2010). Akan tetapi, dari penelitian-penelitian yang telah dilakukan, masih sedikit yang menggunakan pendekatan metaheuristik. Oleh karena itu, masih terbuka peluang untuk melakukan penelitian mengenai CSP dengan metode metaheuristik. Metode metaheuristik juga baik digunakan untuk menyelesaikan CSP yang termasuk NP-Hard Problem dan Combinatorial Problem sehingga peneliti menggunakan metode metaheuristik. Metode metaheuristik yang digunakan adalah Artificial Bee Colony Algorithm (ABC) atau juga disebut Bee Swarm Optimization (BSO). Dipilih algoritma tersebut karena BSO memberikan hasil yang bagus dengan pembangkitan solusi baru dari elite bee dan dari area di sekitarnya. Algoritma ini selalu memperhatikan area di sekitar elite bee sehingga kecil kemungkinan terjebak pada local optimal. Genetic Algorithm yang sebelumnya digunakan memiliki kekurangan pada proses pencarian solusi optimal, yaitu konvergensi lambat dan ada kemungkinan solusi terbaik terbuang. Penyebabnya adalah proses pembaharuan sampel yang dilakukan dengan mutasi dan crossover berdasarkan bilangan random dapat memunculkan solusi baru yang jauh dari solusi awal dan solusi terbaik saat itu mungkin tergantikan oleh solusi lain yang belum tentu lebih baik. Sedangkan Ant Colony Optimization yang telah diterapkan membutuhkan waktu lama untuk pembangkitan
sampel karena sampel dibangkitkan per bagian sehingga membutuhkan proses pembangkitan yang berulang-ulang. Selain itu, algoritma BSO belum pernah diterapkan pada penelitian mengenai Container Stowage Problem. 2. Peraturan Penataan Container Container Stowage Problem berawal dari munculnya proses containerization. Containerization adalah pengangkutan menggunakan kapal berdasarkan sistem intermoda transportasi kargo dengan standar ISO (Ramadhani, 2008). Sebelum adanya sistem tersebut, kargo dikirim dalam ukuran yang bervariasi sesuai dengan ukuran barang yang dikirim sehingga susah ditata, banyak area yang kosong, rawan rusak dan hilang. Karena ada permasalahan tersebut, kemudian muncul sistem intermoda, yaitu sistem standarisasi ukuran kargo atau container sehingga container yang sama bisa dikirim ke tempat tujuan menggunakan alat transportasi yang berbeda dengan minimum gangguan dan lebih efisien. Dengan adanya sistem intermoda, maka penataan container menjadi lebih mudah dan cepat. Tapi karena jumlah container yang diangkut terus meningkat, maka semakin banyak alternatif yang muncul sehingga kemudian muncul Container Stowage Problem yang merupakan Combinatorial Problem dan NP-Hard Problem. Selain itu, penataan container ke dalam kapal harus mengikuti aturan yang ada, sebagai berikut : • Ukuran Container Terdapat 5 macam ukuran panjang container, yaitu 20 feet (6.1 m), 40 feet (12.2 m), 45 feet (13.7 m), 48 feet (14.6 m), dan 53 feet (16.2 m) dengan ukuran lebar yang sama, yaitu 8 feet. Namun, container yang sering digunakan pada transportasi laut adalah container dengan panjang 20 feet dan 40 feet. Container 20 feet biasanya disebut dengan satu TEU (Twenty-foot Equivalent Units) dan container 40 feet disebut dengan dua TEU atau satu FEU (Forty-foot Equivalent Unit). Pada proses stowage, kedua container tersebut dipisahkan karena diletakkan pada tempat yang berbeda. Masing-masing ukuran container memiliki tempat sendiri di kapal. Meskipun FEU memiliki ukuran dua kali TEU, FEU tidak bisa diletakkan pada dua lokasi TEU dan sebaliknya,
2
satu lokasi FEU tidak bisa ditempati dua buah TEU. Hal tersebut dilakukan untuk mempermudah jika terjadi shifting. • Tipe Container Selain dibedakan berdasarkan ukuran, container juga dibedakan berdasarkan tipenya. Macam-macam tipe container adalah sebagai berikut : o General/ Dry container adalah container biasa seperti pada umumnya. o Refrigerator container adalah container yang dilengkapi dengan sistem pendingin. o Hazardous container adalah container yang digunakan untuk memuat barang yang mudah meledak atau berbahaya. o Tank container adalah container berbentuk tangki yang digunakan untuk memuat barang cair. Dalam proses stowage, container tersebut dipisah karena memiliki tempat khusus, kecuali general/dry container. Refrigerator container memerlukan sumber listrik untuk menyalakan sistem pendingin sehingga harus diletakkan di area yang memiliki sumber listrik. Hazardous container harus dipisahkan dari container lain karena rawan meledak dan radiasi. Tank container yang berbentuk tangki harus diletakkan paling atas karena di atasnya tidak boleh ditumpuk container. • Berat Container Container memang memiliki ukuran yang sama, tapi memuat barang yang berbeda-beda sehingga berat masing-masing container berbeda. Secara umum, berat container dikelompokkan menjadi tiga jenis, yaitu ringan (5-15 ton), medium (15-25 ton), dan berat (lebih dari 25 ton). Dalam proses stowage, berat container sangat diperhatikan karena berpengaruh pada keseimbangan tumpukan container. Untuk menjaga keseimbangan tumpukan container maka container yang lebih berat diletakkan di bawah. Meskipun container berbentuk rectangular dan terbuat dari besi, masih ada kemungkinan container itu akan rusak jika beban di atasnya lebih berat. • Tujuan Container Kapal pengangkut container tidak hanya berlayar ke satu tujuan port saja, tapi lebih dari satu tujuan (multi tujuan) sehingga container yang diangkut memiliki bermacam-macam
tujuan. Setelah mencapai tujuan, container akan di-unstowage sedangkan container yang lain tetap berada di kapal. Tapi, ketika container yang akan di-unstowage terhalang container lain yang seharusnya tetap di kapal, maka perlu dilakukan shifting (pemidahan sementara). Untuk mengurangi jumlah shifting, dalam proses stowage diusahakan agar container dengan tujuan terdekat terletak paling atas dan tujuan terjauh terletak paling bawah (Ambrosino et al, 2004). • Keseimbangan Kapal Satu faktor yang penting lagi adalah keseimbangan kapal. Dalam proses stowage harus memperhatikan keseimbangan kapal. Ada tiga macam keseimbangan yang harus diperhatikan, yaitu : o Cross equilibrium, yaitu keseimbangan antara bagian kanan dan kiri kapal. Selisih berat bagian kanan dan bagian kiri tidak boleh melebihi batas toleransi yang telah ditentukan. o Horizontal equilibrium, yaitu keseimbangan antara bagian depan dan belakang. Selisih berat bagian depan dan bagian belakang juga tidak boleh melebihi batas toleransi yang telah ditentukan. Vertical equilibrium, yaitu keseimbangan antara bagian atas (upper deck) dengan bagian bawah (lower deck). Untuk kapal yang memiliki upper deck dan lower deck, maka berat pada bagian upper deck harus lebih ringan atau sama dengan berat pada bagian lower deck. • Penamaaan lokasi Setiap lokasi container pada kapal memiliki nama atau keterangan masing-masing berdasarkan posisi bay, row, dan tier. Penamaan bay dihitung dari bagian depan kapal ke bagian belakang kapal. Sedangkan penamaan row dihitung dari bagian tengah kapal ke bagian luar kapal jika kapal dilihat dari atas. Untuk penamaan tier dihitung dari bagian bawah ke bagian atas jika kapal dilihat dari samping. Contoh penamaan bay, row, dan tier dapat dilihat pada Gambar 2.1. berikut ini :
3
∑x
i +1 jkc
+ ∑ xijkc ≤ 1 ∀i ∈ E , j , k
(8)
∑x
i −1 jkc
+ ∑ xijkc ≤ 1 ∀i ∈ E , j , k
(9)
c∈T
c∈T
i +1 jk +1c
+ ∑ xijkc ≤ 1 ∀i ∈ E , j, k = 1,..., k − 1 (10)
∑x
i −1 jk +1c
+ ∑ xijkc ≤ 1 ∀i ∈ E , j, k = 1,..., k − 1 (11)
c∈T
Pada Gambar 2.5 dapat dilihat masingmasing nama untuk setiap lokasi berdasarkan nomor bay, row, dan tier. Ketika container 20’ yang diletakkan, maka bay diberi nomor ganjil dan disebut bay ganjil. Tapi, ketika container 40’ yang diletakkan, maka dua bay ganjil diberi nomor genap sehingga menjadi bay genap. Sedangkan untuk row dan tier diberi nomor sesuai dengan yang tertera. 3.
Model Matematis Container Stowage Problem Container Stowage Problem telah dilakukan penelitian dengan bermacam-macam metode dan beberapa model. Satu diantara model tersebut yang memperhatikan kelima faktor dalam proses stowage (ukuran, tipe, berat, dan tujuan container, serta keseimbangan kapal) adalah model yang dibangun oleh Daniela Ambrosino, Anna Sciomachen, dan Elena Tanfani (2004). Model dasar yang disusun adalah sebagai berikut ini : Min L =
∑∑ t l
∑∑ x l
lc
lc
xlc
(1)
c
=m
(2) (3)
c∈F
∑ ∑w x
ijkc
≤ MT
∀i, j
(12)
∑ ∑w x
ijkc
≤ MF
∀i, j
(13)
k
k
c
c∈T
c
c∈F
∑ (w x
− we xijk +1e ) ≥ 0 ∀i, j, k = 1,..., k − 1 (14)
∑ (d x
− d e xijk +1e ) ≥ 0 ∀i, j, k = 1,..., k − 1 (15)
c ,e∈C: wc ≠ we
c ,e∈C: dc ≠de
c ijkc
c ijkc
− Q2 ≤ − Q1 ≤
∑ ∑w x
−
∑ ∑w x
−
i∈A, j , k c
i , j∈L , k c
c ijkc
c ijkc
∑ ∑w x
≤ Q2 (16)
∑ ∑w x
≤ Q1 (17)
i∈P , j , k c
i , j∈R , k c
xlc ∈ {0,1} ∀l , c
c ijkc
c ijkc
(18)
Fungsi tujuan dari model matematis ini meminimalkan total waktu unloading (L), dengan variabel keputusannya adalah :
xlc : variabel untuk container ke-c di lokasi l, sama dengan 1 jika container ke-c berada di lokasi l dan sama dengan 0 jika tidak. x lc = x ijkc Untuk keterangan variabel lain yang digunakan dalam model matematis tersebut adalah sebagai berikut :
∑x
(4)
L
: lokasi penempatan ke – 1, ...., n yang ditunjukkan dengan i = bay, j = row, dan k = tier (l = 1,2,…,n)
c
: container ke – 1,...,m
t lc
: waktu yang diperlukan untuk unloading container ke-c di lokasi l
m
: jumlah semua container
l
lc
≤ 1 ∀l
c
∑∑ w x c
lc
≤Q
(5)
c
∑ xijkc = 0 ∀i ∈ E, j, k
(6)
∑x
(7)
c∈T
c∈F
c∈F
c
∑ xlc ≤ 1 ∀c
l
c∈F
∑x c∈T
Gambar 2.1. Penamaan bay, row, dan tier pada kapal
c∈F
ijkc
= 0 ∀i ∈ O, j , k
wc : berat container ke-c Q
: total kapasitas
Q 1 : toleransi keseimbangan anterior-posterior
4
Q 2 : toleransi keseimbangan left-right E
: bay genap
O
: bay ganjil
T
: container dengan ukuran 20 feet
F
: container dengan ukuran 40 feet
MT : batas berat satu tingkat container 20 feet MF : batas berat satu tingkat container 40 feet k
: tier kapal
dc
: tujuan dari container
Untuk keterangan tiap persamaan pada model matematis adalah sebagai berikut . Persamaan (1) merupakan fungsi tujuan, yaitu meminimasi total waktu unloading. Persamaan (2) adalah total lokasi l yang ditempati container harus sama dengan jumlah container. Persamaan (3) adalah satu container hanya ditempatkan pada satu lokasi. Persamaan (4) adalah satu lokasi hanya bisa ditempati satu container. Persamaan (5) adalah total berat container yang diangkut tidak boleh melebihi kapasitas kapal (Q). Persamaan (6) adalah container 20 feet (T) tidak akan ditempatkan pada bay genap (E). Persamaan (7) adalah Container 40 feet (F) tidak akan ditempatkan pada bay ganjil (O). Persamaan (8) dan (9) adalah container 20 feet dan container 40 feet tidak bisa diletakkan bersamaan pada bay ganjil dan bay genap yang berurutan. Persamaan (10) dan (11) adalah container 20 feet tidak bisa diletakkan di atas container 40 feet. Persamaan (12) adalah total berat tumpukan container 20 feet pada satu tier tidak boleh melebihi batas MT. Persamaan (13) adalah total berat tumpukan container 40 feet pada satu tier tidak boleh melebihi batas MF. Persamaan (14) adalah container yang lebih berat tidak bisa diletakkan di atas container yang lebih ringan. Persamaan (15) container dengan tujuan awal diletakkan di atas container dengan tujuan akhir. Persamaan (16) adalah selisih total berat container pada bagian anterior dengan bagian posterior tidak boleh melebihi toleransi Q 2 . Persamaan (17) adalah selisih total berat container pada sisi left dengan sisi right tidak boleh melebihi toleransi Q 1 . Persamaan (18) adalah variabel keputusan merupakan bilangan biner (0,1).
4. Pengembangan Algoritma Pengembangan algoritma dilakukan untuk menyesuaikan algoritma yang dipakai dengan permasalahan. Dari algoritma tersebut kemudian dibangun model pada software yang digunakan. Pengembangan algoritma Bee Swarm Optimization untuk penyelesaian permasalahan Container Stowage Problem adalah sebagai berikut : 1. Pengumpulan data Mengumpulkan data ukuran, berat, dan tujuan container, waktu unloading, dan jumlah bay, row, dan tier. 2. Penentuan parameter Menentukan nilai dari tiap parameter pengujian, yaitu : N
: jumlah sampel pada tiap iterasi
alpha : persentase experienced foragers beta
: persentase onlooker
cont20 : matriks berat dan tujuan container 20 feet cont40 : matriks berat dan tujuan container 40 feet time
: matriks waktu unloading
bay
: jumlah bay
3. Penentuan jumlah lokasi Menentukan jumlah lokasi untuk masingmasing container 20’ dan 40’. Jumlah total lokasi container 20’ dan 40’ harus sama dengan total jumlah lokasi dalam kapal, dimulai dari satu sampai jumlah lokasi yang telah ditentukan. 4. Pembangkitan N urutan random Membangkitkan urutan random untuk masing-masing container 20’ dan 40’. Urutan yang dibangkitkan sesuai dengan jumlah lokasi yang telah ditentukan dan sebanyak jumlah sampel N. 5. Penyesuaian urutan dengan jumlah container Penyesuaian dilakukan pada masing-masing urutan container 20’ maupun 40’. Penyesuaian dilakukan karena jumlah lokasi lebih banyak dari jumlah container. Nomor pada urutan yang tidak ada dalam daftar nomor container (nomor yang lebih dari jumlah container) diubah menjadi 0 dan dianggap pada lokasi tersebut tidak ada container yang diletakkan.
5
6. Pengubahan urutan menjadi posisi tumpukan Pada masing-masing urutan container 20’ dan 40’ kemudian diubah dalam bentuk tumpukan dengan tinggi sesuai jumlah tier. Satu tumpukan tidak boleh terdiri dari dua ukuran container. Satu tumpukan hanya berisi satu ukuran container,yaitu container 20’ saja atau 40’ saja sesuai dengan persamaan (10) dan (11). Langkah ini bertujuan untuk memastikan bahwa satu tumpukan hanya berisi satu jenis ukuran. 7. Penggabungan sampel container 20’ dan 40’ Kemudian tumpukan container 20’ dan 40’ dimasukkan ke dalam matriks dengan ukuran sesuai dengan jumlah bay, row, dan tier. Setelah diperoleh sampel yang utuh, kemudian dibuat dua buah matriks lagi dengan ukuran yang sama namun berisi berat (matriks berat) dan tujuan (matriks tujuan) sesuai dengan container yang ada pada sampel. 8. Pengecekan sampel terhadap konstrain berat container Sampel yang telah diperoleh disesuaikan dengan konstrain berat container, yaitu persamaan (14). Ketika susunan pada sampel tidak sesuai dengan konstrain (container lebih berat berada di atas container lebih ringan), maka akan diberikan penalti sebesar 1000000 untuk setiap pelanggaran konstrain yang terjadi. 9. Pengecekan sampel terhadap konstrain tujuan container Sampel yang telah diperoleh disesuaikan dengan konstrain tujuan container, yaitu persamaan (15). Ketika susunan pada sampel tidak sesuai dengan konstrain (container tujuan awal berada di bawah container tujuan akhir), maka akan diberikan penalti sebesar 1 untuk setiap pelanggaran konstrain yang terjadi. 10. Pengecekan sampel terhadap konstrain keseimbangan kapal Sampel yang telah diperoleh disesuaikan dengan konstrain keseimbangan kapal, yaitu keseimbangan anterior-posterior pada persamaan (16) dan keseimbangan left-right pada persamaan (17). Ketika susunan pada sampel tidak sesuai dengan konstrain (selisih berat pada anterior-posterior atau left-right melebihi toleransi), maka akan diberikan
penalti sebesar 1000 untuk setiap ton kelebihan yang terjadi. 11. Perhitungan total waktu unloading Waktu unloading memiliki nilai yang berbeda berdasarkan matriks time yang telah dimasukkan. Jika ada container yang diletakkan pada suatu lokasi maka besar waktu unloading sesuai dengan lokasinya. Jika tidak ada, maka waktu unloading sama dengan 0. Keseluruhan waktu unloading container dijumlahkan dan diperoleh total waktu unloading, sesuai persamaan (1). 12. Perhitungan nilai fitness Menghitung nilai fitness masing-masing sampel dengan menjumlahkan nilai penalti dan waktu unloading. 13. Pengurutan sampel berdasarkan nilai fitness Sampel diurutkan berdasarkan nilai total fitness dari yang terbaik (paling kecil) ke terburuk (paling besar). 14. Pengalokasian tiap sampel berdasarkan urutan nilai fitness Mengalokasikan tiap sampel ke dalam tiga kawanan yaitu : experienced forager, onlooker, atau scout berdasarkan urutan nilai fitness dan proporsi tiap kawanan yang telah ditentukan sebelumnya. Kelompok terbaik pertama adalah experienced forager sebanyak alpha*N, kelompok terbaik kedua adalah onlooker sebanyak beta*N, dan kelompok terakhir adalah scout. 15.a. Update posisi pada tiap experienced forager 1) Update posisi terbaik dari posisi sebelum Jika posisi pada iterasi sebelumnya lebih baik maka posisi yang digunakan adalah posisi pada iterasi sebelumnya. Jika posisi sekarang lebih baik, maka posisi terbaik sama dengan posisi sekarang. 2) Pemilihan elite bee Memilih elite bee berdasarkan fitness terbaik pada experienced forager. 3) Update posisi Memperbaharui posisi berdasarkan posisi terbaik dan elite bee.
6
15.b. Update posisi pada tiap onlooker 1) Pemilihan elite bee untuk tiap onlooker Memilih elite bee dari kelompok experienced forager dengan roulette wheel. 2) Update posisi Memperbaharui posisi berdasarkan elite bee yang telah dipilih sebelumnya. 15.c. Update posisi pada tiap scout 1) Perhitungan parameter pergeseran random Menghitung besarnya radius pergeseran random (tao) yaitu sebesar selisih bilangan random terbesar dan terkecil pada posisi tersebut. 2) Update posisi Memperbaharui posisi secara random dalam radius tao dengan pusat posisi awal. 16. Kriteria pemberhentian (stopping criteria) ditentukan untuk memutuskan apakah iterasi perlu dilanjutkan atau sudah cukup. Jika sudah cukup (kriteria pemberhentian tercapai) maka iterasi dihentikan dan muncul solusi terbaik. Jika kriteria pemberhentian belum tercapai, maka kembali ke langkah nomor 5. Kriteria pemberhentian yang digunakan ada dua macam, yaitu : • Untuk iterasi pertama sampai iterasi ke100, kriteria pemberhentiannya adalah nilai standar deviasi dari posisi terbaik telah kurang dari 1. • Untuk iterasi selanjutnya, criteria pemberhentiannya adalah nilai standar deviasi dari posisi terbaik telah kurang dari 1 atau nilai elite bee tidak berubah selama 100 iterasi. 5. Contoh Numerik Kasus yang digunakan adalah kasus yang sangat sederhana, yaitu penataan container pada lokasi yang berukuran 4 bay, 2 row, dan 1 tier, dengan data sebagai berikut : Tabel 5.1. Contoh kasus sangat sederhana ukuran Nomor berat Tujuan 20' 40'
1
10
1
2
15
2
1
25
1
Tabel 5.2. Waktu unloading row1 row2 tier1
120
126
Kasus tersebut akan diselesaikan dengan algoritma Bee Swarm Optimization yang telah dikembangkan dan akan dibandingkan dengan teknik enumerasi. Jika hasilnya sama dengan teknik enumerasi, maka algoritma telah valid karena teknik enumerasi pasti menghasilkan solusi optimal. 5.1 Enumerasi Enumerasi dilakukan dengan mencari semua kombinasi yang mungkin menjadi solusi. Untuk contoh kasus yang telah disebutkan sebelumnya terdapat 120 kemungkinan solusi. Setelah dilakukan perhitungan untuk semua kemungkinan tersebut, diperoleh hasil terbaik sebagai berikut : Total fitness = 366 Penalti = 0 Waktu unloading = 366 Terdapat 21 solusi terbaik, satu diantaranya adalah : row1 bay1 bay2 bay3
row2
1 1
2
bay4 container 20' container 40' Gambar 5.1. Contoh solusi terbaik (dilihat dari atas)
5.2 Algoritma Bee Swarm Optimization Contoh kasus yang telah disebutkan juga diselesaikan dengan algoritma Bee Swarm Optimization, langkah penyelesaiannya adalah sebagai berikut : Langkah 1. Inisialisasi Pada langkah pertama ini dilakukan penentuan parameter dan pemasukan data, seperti berikut : N = 10 alpha = 0.2 beta = 0.3 cont20 = [1 10 1 ; 2 15 2]
7
cont40 = [1 25 1] time = [120 126] bay = 4 Langkah 2. Pembangkitan N urutan random - Pembangkitan nilai random sebanyak N x jumlah lokasi, kemudian diurutkan sehingga diperoleh urutan seperti berikut : Tabel 5.3. Urutan sampel hasil pembangkitan Sampel
container 20'
container 40'
1
3
1
4
2
1
2
2
1
2
3
4
2
1
3
4
1
3
2
2
1
4
1
4
2
3
2
1
5
2
4
3
1
1
2
6
1
4
2
3
2
1
7
4
2
1
3
1
2
8
1
4
3
2
2
1
9
4
3
2
1
2
1
10
2
3
1
4
1
2
Tabel 5.4. Contoh posisi sampel hasil penyesuaian (dilihat dari atas) Sampel 6 7 8 9 10
Posisi
2
2
1
1
1 1
1
2
1
2
1
fitness = waktu unloading + 60*penalti
(19)
Langkah 4. Pengurutan nilai fitness Mengurutkan nilai fitness yang telah dihitung sehingga diperoleh urutan sampel seperti berikut ini : Tabel 5.5. Hasil pengurutan total fitness sampel fitness
- Penyesuaian urutan dengan lokasi penataan dan jumlah container sehingga diperoleh sampel seperti berikut :
1
1 ketika ada container tujuan awal berada di bawah container tujuan akhir. - Perhitungan waktu unloading sesuai dengan matriks time. - Menghitung total fitness dengan persamaan :
2 1 1
container 20' container 40'
Langkah 3. Perhitungan nilai fitness - Perhitungan nilai penalti dari tiap posisi, nilai penalti berbeda-beda sesuai dengan konstrain yang dilanggar. Penalti 1000000 ketika ada container berat berada di atas container ringan. Penalti 1000 ketika keseimbangan kapal melebihi batas yang ditentukan. Penalti
6
366
7
366
2
372
9
372
5
750366
8
750372
1
900360
10
900360
4
900378
3
1950372
Langkah 5. Pengalokasian tiap sampel Membagi sampel ke dalam tiga kelompok, yaitu : - Experienced forager sebanyak alpha*N pertama, yaitu (0,2)*10 = 2 sampel. Dua sampel terbaik masuk ke experienced forager, yaitu sampel nomor 6 dan 7. - Onlooker sebanyak beta*N berikutnya, yaitu (0,3)*10 = 3 sampel. Tiga sampel berikutnya masuk ke onlooker, yaitu sampel nomor 2,9, dan 5. - Scout sebanyak sisa dari dua kelompok sebelumnya. Lima sampel terakhir masuk ke scout, yaitu sampel nomor 8,1,10,4 dan 3. Langkah 6. Update posisi pada tiap experienced forager Memilih elite bee dari kelompok experienced forager, yaitu sampel nomor 6 (fitness terbaik). Kemudian melakukan update posisi untuk tiap experienced forager sesuai persamaan : posisinew = posisiold + r b *(posisi terbaik (20) posisiold ) + r e *(elite - posisiold )
8
Langkah 7. Update posisi pada tiap onlooker Memilih elite bee dari kelompok experienced forager dengan roulette wheel untuk tiap onlooker. Kemudian melakukan update posisi untuk tiap onlooker sesuai persamaan : posisinew = posisiold + r e *(elite - posisiold )
(21)
Langkah 8. Update posisi pada tiap scout Menghitung nilai tao (parameter pergeseran random) dengan persamaan : tao = | randommax - randommin |
(21)
Kemudian melakukan update posisi untuk tiap scout sesuai persamaan : (22) posisinew = posisiold + r w*(tao, posisiold ) Langkah 9. Ulangi langkah 3 sampai langkah 8 hingga kriteria pemberhentian terpenuhi. Jika standar deviasi posisi terbaik kurang dari 0.1, maka iterasi berhenti dan diperoleh hasil terbaik, yaitu : nilai penalti = 0 waktu unloading = 366 total fitness terbaik = 366 solusi akhir pada MATLAB
tier 1 row 1
row 2
Gambar 5.3. Output solusi terbaik untuk bay 1
Pada gambar 5.3 dapat dilihat ada tulisan xopt (: , : , 1), angka 1 menunjukkan nomor bay, sedangkan nomor row sesuai dengan urutan kolom pada matriks xopt (: , : , 1) (dari kiri ke kanan) dan nomor tier sesuai dengan urutan baris pada matriks xopt (: , : , 1) (dari bawah ke atas). Cara membaca posisi untuk bay 2,3, dan 4 sama seperti pada bay 1. Angka di dalam matriks menunjukkan nomor container yang diletakkan pada lokasi tersebut. Jika di posisi yang sama pada bay yang berurutan memiliki nomor yang sama, maka pada lokasi tersebut ditempati container 40’. Jika angka di dalam matriks bernilai 0, maka tidak ada container yang diletakkan pada posisi tersebut. Dari output solusi terbaik kemudian diubah menjadi seperti berikut agar mudah dibaca : row1 bay1
1
bay2
2
bay3 bay4
row2
1
container 20' container 40' Gambar 5.6. Solusi terbaik (dilihat dari atas)
Gambar 5.2. Output solusi terbaik pada MATLAB
Solusi terbaik yang diperoleh dari MATLAB seperti pada Gambar 5.2. Pada kasus tersebut terdapat 4 bay, 2 row, dan 1 tier. Cara mengetahui posisi container dari solusi terbaik seperti pada contoh berikut untuk bay 1 :
Gambar 5.6 menunjukkan posisi tiap container ketika dilihat atas. Karena hanya ada satu tier, maka semua container (2 buah container 20 feet dan 1 buah container 40 feet) terlihat ketika dilihat dari atas. 6. Eksperimen dan Analisis 6.1 Deskripsi Data Uji Data yang digunakan berdasarkan kriteria yang ada di dalam jurnal Ambrosino et al (2004) yang berjudul “Stowing a containership : the master bay plan problem”. Kriteria dari data tersebut adalah sebagai berikut :
9
• Kasus 3
Tabel 6.1. Tabel kriteria data untuk tiap kasus ukuran
berat (ton)
tujuan
total container
20
40
light
medium
heavy
d1
d2
d3
1
100
62
38
45
30
25
47
53
0
2
120
75
45
50
44
26
55
65
0
3
130
90
40
56
46
28
55
75
0
kasus
BSO
BSO modifikasi
rata-rata
18528
18504
terbaik
18492
18456
8
140
95
45
60
50
30
65
75
9
140
95
45
60
50
30
50
40
Dari kriteria tersebut kemudian dibuat data dengan kriteria tambahan, yaitu : - 50% container light memiliki berat 10 ton dan 50% sisanya memiliki berat 15 ton. - 50% container medium memiliki berat 20 ton dan 50% sisanya memiliki berat 25 ton. - 50% container heavy memiliki berat 30 ton dan 50% sisanya memiliki berat 35 ton. 6.2 Hasil Eksperimen Eksperimen pengujian algoritma dengan 5 macam kasus dilakukan dengan parameter N = 5000, alpha = 0,01, dan beta = 0,1. Stopping criteria yang digunakan adalah besarnya standar deviasi dan jumlah iterasi. Ketika jumlah iterasi kurang dari 100, maka stopping criteria adalah standar deviasi kurang dari 1. Ketika jumlah iterasi lebih dari 100, maka stopping criteria adalah standar deviasi kurang dari 1 atau nilai fitness elite bee tidak berubah selama 100 iterasi. Berikut ini adalah hasil eksperimen dan perbandingannya dengan solusi optimal : • Kasus 1
BSO modifikasi
rata-rata
14548.8
14488.8
terbaik
14490
14436
rata-rata
17311.5
17221.5
terbaik
17268
17190
50
• Kasus 8 Tabel 6.5. Tabel perbandingan BSO - BSO modifikasi - jurnal untuk kasus 8 BSO
BSO modifikasi
rata-rata
19930.5
19857
terbaik
19908
19818
jurnal 19440
• Kasus 9 Tabel 6.6. Tabel perbandingan BSO - BSO modifikasi - jurnal untuk kasus 9 BSO
BSO modifikasi
rata-rata
19906.5
19875
terbaik
19854
19842
gap 19470
16584
Tabel 6.7. Tabel performansi untuk semua kasus
13854
Tabel 6.3. Tabel perbandingan BSO - BSO modifikasi - jurnal untuk kasus 2 BSO modifikasi
18096
Jurnal
Jurnal
• Kasus 2
BSO
0
Jurnal
6.2 Analisis Algoritma Bee Swarm Optimization dapat digunakan untuk menyelesaikan Container Stowage Problem dengan melakukan penambahan penalti. Penalti tersebut digunakan untuk mengontrol sampel agar sesuai dengan permasalahan yang diselesaikan. Penalti ditambahkan pada nilai fitness sehingga sampel yang terkena penalti akan memiliki nilai fitness yang lebih besar. Jadi, solusi terbaik yang diperoleh telah sesuai dengan permasalahan Container Stowage Problem. Dari hasil eksperimen pada lima kasus, secara umum algoritma Bee Swarm Optimization menghasilkan solusi yang mendekati solusi optimal. Hal itu dapat dilihat dari rata-rata %gap dan gap seperti pada Tabel 6.7 berikut ini.
Tabel 6.2. Tabel perbandingan BSO - BSO modifikasi - jurnal untuk kasus 1 BSO
Tabel 6.4. Tabel perbandingan BSO - BSO modifikasi - jurnal untuk kasus 3
BSO-jurnal Kasus
%error
gap
BSO modifikasi-jurnal %error
gap
10
1
5.02%
636
4.58%
582
2
4.39%
684
3.84%
606
3
2.39%
396
2.25%
360
8
2.52%
468
2.15%
378
9
2.24%
384
2.08%
372
rata-rata
3.31%
513.6
2.98%
459.6
Pada permasalahan Container Stowage Problem untuk kasus sedang, algoritma Bee Swarm Optimization memiliki %gap rata-rata sebesar 3,31% dan selisih solusi terbaik dengan solusi optimal selama 513,6 detik atau 8,56 menit. Algoritma Bee Swarm Optimization yang dikembangkan belum bisa menghasilkan solusi yang sama dengan solusi optimal. Karena dalam proses pencarian solusi, ada kemungkinan terjebak lokal optimal. Nilai fitness elite bee yang tidak berubah selama 100 iterasi (stopping criteria) menunjukkan bahwa algoritma telah mencapai kondisi stagnation. Hal itu bisa terjadi karena solusi yang dimunculkan oleh algoritna ini sangat bergantung pada solusi random di kelompok scout. Scout dapat memunculkan kandidat solusi yang berbeda signifikan sehingga dapat menghindari local optimal. Namun, ketika scout memunculkan kandidat solusi yang tidak berbeda signifikan, maka ada kemungkinan algoritma mengalami stagnation. Karena kandidat solusi baru yang dimunculkan dari experienced forager dan onlooker cenderung tidak berbeda signifikan. Pada algoritma Bee Swarm Optimization untuk Container Stowage Problem ini juga ditambahkan modifikasi,yaitu dengan menukar posisi container sehingga container berat yang di atas akan bertukar tempat dengan container ringan yang di bawahnya. Dengan penambahan modifikasi ini, solusi terbaik yang dihasilkan lebih baik dari solusi terbaik algoritma Bee Swarm Optimization tanpa modifikasi. Karena modifikasi yang dilakukan dapat mencegah munculnya sampel yang pasti tidak memenuhi konstrain berat container. Sehingga sampel baru yang dibangkitkan tidak akan terkena penalti. Jika sampel tidak terkena penalti, maka nilai fitness menjadi lebih kecil dan solusi terbaik yang dihasilkan menjadi lebih baik.
7. Kesimpulan dan Saran 7.2 Kesimpulan 1. Algoritma Bee Swarm Optimization berhasil dikembangkan untuk menyelesaikan permasalahan Container Stowage Problem. 2. Hasil algoritma Bee Swarm Optimization belum bisa sama dengan solusi optimal karena ada kemungkinan terjebak local optimal. 3. Penambahan langkah membalikkan urutan dapat memperbaiki solusi akhir karena sampel baru yang dibangkitkan hanya sampel yang memenuhi konstrain berat. 7.3 Saran 1. Penelitian selanjutnya dapat dilakukan dengan memodifikasi algoritma sehingga kemungkinan terjebak local optimal (stagnation) lebih kecil. 2. Penelitian selanjutnya dapat diaplikasikan untuk kasus nyata atau kasus yang sangat besar dengan jumlah container mencapai 5000 TEU. 9. Referensi Akbari, R., Mohammadi, A., & Ziarati, K.
(2009). A novel bee swarm optimization algorithm for numerical function optimization. Ambrosino, D., Anghinolfi, D., Paolucci, M., & Sciomachen, A. (2010). An Experimental Comparison of Different Heuristics for the Master Bay Plan Problem. Ambrosino, D., Sciomachen, A., & Tanfani, E. (2004). Stowing a containership: the master bay plan problem. Avriel, M., Penn, M., & Shpirer, N. (2000). Container ship stowage problem : complexity and connection to the coloring of circle graphs. Dubrovsky, O., Levitin, G., & Penn, M. (2002). A Genetic Algorithm with a Compact Solution Encoding for the Container Ship Stowage Problem. Imai, A., Sasaki, K., Nishimura, E., & Papadimitriou, S. (2002). Multiobjective simultaneous stowage and load planning for a container ship with container rehandle in yard stacks.
11
Li, F., Tian, C., Cao, R., & Ding, W. (2008). An Integer Linear Programming for Container Stowage Problem. Martins, P. T., Lobo, V. J., & Vairinhos, V. (2009). Container Stowage Problem Solution for Short Sea Shipping. Ramadhani, N. (2008). Pengembangan rancang bangun perangkat lunak untuk penataan pemuatan peti kemas ke kapal peti kemas multi tujuan. Santosa, B. & Willy, P., 2011. Metode Metaheuristik Konsep dan Implementasi. Surabaya : Penerbit Guna Widya. Teodorovic, D., Davidovic, T., & Selmic, M. (2011). Bee Colony Optimization: The Applications Survey. Wilson, I. D., Roach, P. A., & Ware, J. A. (2001). Container stowage pre-planning : using search to generate solutions, a case study.
12
