chapter ii

BAB 2

LANDASAN TEORI

2.1. Optimalisasi

Optimalisasi merupakan suatu proses untuk mengoptimalkan suatu solusi agar

ditemukannya solusi terbaik dari sekumpulan alternatif solusi yang ada dengan

menggunakan formulasi matematika. Optimalisasi dilakukan dengan memaksimalkan

atau meminimalkan suatu fungsi objektif dengan tidak melanggar batasan yang ada

(Sianturi, 2012). Dengan adanya optimalisasi, suatu sistem dapat meningkatkan

efektifitasnya seperti meminimalisir biaya, meningkatkan keuntungan, meminimalisir

waktu proses, dan sebagainya.

2.2. Bin Packing Problem

Bin Packing Problem adalah sebuah permasalahan optimalisasi kombinatorial yang

termasuk dalam jenis Non-deterministic Polynomial-time (NP) hard yang pertama kali

diperkenalkan oleh Garey dan Johnson pada tahun 1979. Bin Packing memiliki peran

penting dalam menyelesaikan beberapa persoalan di dunia nyata seperti perencanaan

transportasi, pemuatan kontainer, alokasi sumber daya, penjadwalan, serta kargo

pesawat dan kapal (Yesodha & Amudha, 2013). Pada permasalahan bin packing,

diberikan sebuah bin dengan kapasitas tertentu V yang digunakan sebagai tempat dari

seluruh objek n yang memiliki ukuran berbeda-beda, dan tujuannya adalah untuk

meminimalkan bin yang digunakan agar seluruh objek n dapat ditempatkan ke dalam

bin tersebut (Swain et al., 2014).

2.2.1. Two dimensional bin packing problem (2DBPP)

Pada 2DBPP, sebuah item atau objek hanya memiliki dua buah variabel seperti

panjang dan lebar. Penyusunan item atau objek pada 2DBPP hanya berdasarkan

Universitas Sumatera Utara

7

kepada dua variabel tersebut. 2DBPP biasanya digunakan untuk menyusun barang

pada lantai ruang dan tidak adanya penumpukan barang. 2DBPP bisa juga digunakan

untuk menyusun barang dengan adanya penumpukan, tetapi semua barang tersebut

harus memiliki variabel tinggi yang sama, sehingga variabel tinggi tersebut tidak akan

mempengaruhi penyusunan barang yang memiliki variabel panjang dan lebar yang

berbeda.

2.2.2. Three dimensional bin packing problem (3DBPP)

Pada 3DBPP, satu atau lebih bin yang tersedia dipilih untuk memuat barang-barang

secara tiga dimensi sehingga ruang pada bin dapat dimaksimalkan (Li et al., 2014).

Berbeda dengan 2DBPP yang hanya menggunakan dua variabel, 3DBPP

menggunakan tiga variabel yaitu panjang, lebar, dan tinggi barang dalam melakukan

penyusunan barang. Hal ini menyebabkan tingkat kesulitan 3DBPP lebih tinggi dari

2DBPP. Setiap item atau objek pada 3DBPP harus disusun sedemikian rupa agar item

tersebut dapat dimuat ke dalam bin yang juga memiliki batasan panjang, lebar, dan

tinggi. Jika pada 2DBPP penyusunan barang lebih ditekankan kepada penyusunan

bidang segi empat pada dasar ruang (rectangle-to-floorplan packing), 3DBPP lebih

ditekankan kepada penyusunan bangun segi empat pada ruang (box-to-room packing)

(Sweep, 2003). 3DBPP juga termasuk ke dalam permasalahan pemuatan kontainer

(Container Loading Problem).

Pada 3DBPP penyusunan barang dapat dibedakan menjadi single bin atau

multiple bins. Pada single bin, penyusunan barang yang dilakukan hanya

menggunakan sebuah bin, sehingga tujuan penyusunan hanya untuk meminimalkan

sisa ruang kosong pada bin tersebut. Sementara pada multiple bins, penyusunan

barang yang dilakukan menggunakan lebih dari satu bin, sehingga tujuan

penyusunannya adalah untuk meminimalkan jumlah bin yang digunakan.

2.3. Permasalahan Optimalisasi Penyusunan Barang pada Mobil Box

2.3.1. Gambaran umum objek

Terdapat dua buah objek yang digunakan pada permasalahan optimalisasi penyusunan

barang pada mobil box yaitu mobil box dan barang. Mobil box yang digunakan harus

berbentuk segi empat yang memiliki panjang, lebar, tinggi, serta beban maksimal


8

mobil. Mobil yang digunakan hanya satu buah (single bin). Gambaran umum objek

mobil box dapat dilihat pada Gambar 2.1.

Gambar 2.1. Gambaran Mobil Box dalam Koordinat Tiga Dimensi

(Susanto, 2009)

Pada Gambar 2.1. dapat dilihat bahwa koordinat awal penyusunan (titik 0,0,0)

berada di depan, kiri, dan bawah mobil. Sumbu x mewakili lebar mobil, sumbu y

mewakili tinggi mobil, dan sumbu z mewakili panjang mobil.

Barang yang akan disusun merupakan barang tiga dimensi berbentuk segi

empat yang memiliki panjang, lebar, dan tinggi. Setiap barang juga memiliki berat

sebagai batasan agar mobil box tersebut tidak membawa beban yang melebihi

kapasistasnya. Gambaran umum objek barang dapat dilihat pada Gambar 2.2.

Gambar 2.2. Objek Barang


9

Pada Gambar 2.2. dapat dilihat bahwa barang i memiliki dimensi 1 yang

sejajar dengan sumbu x, dimensi 2 yang sejajar dengan sumbu y, dan dimensi 3 yang

sejajar dengan sumbu z. Dimensi masing-masing barang ini ditentukan oleh perotasian

barang. Apabila suatu barang i tidak dapat dirotasi maka barang tersebut hanya akan

memiliki satu variasi nilai dimensi yaitu dimensi 1 sebagai panjang barang, dimensi 2

sebagai tinggi barang, dan dimensi 3 sebagai lebar barang. Namun, apabila suatu

barang i dapat dirotasi maka barang tersebut akan memiliki enam variasi nilai

dimensi. Pertukaran nilai dimensi untuk suatu barang yang dapat dirotasi dapat dilihat

pada Gambar 2.3.

Gambar 2.3. Variasi Perotasian Barang (Susanto, 2009)

Pada Gambar 2.3. dapat dilihat bahwa pada enam variasi perotasian tersebut,

nilai dimensi masing-masing posisi diubah sesuai dengan arah perputarannya. Seperti

contoh pada Variasi 1, nilai dimensi 1 sama dengan AC yang merupakan panjang

barang. Sedangkan pada Variasi 3 nilai dimensi 1 sama dengan CD yang merupakan

tinggi barang. Nilai dimensi ini yang akan digunakan untuk proses penyusunan barang

di dalam mobil box. Adapun gambaran umum penempatan objek barang pada mobil

box dapat dilihat pada Gambar 2.4.


10

Gambar 2.4. Penempatan Barang pada Mobil Box

Pada Gambar 2.4. dapat dilihat bahwa penempatan suatu barang i di dalam

mobil box didasarkan pada dimensi barang tersebut. Dimensi 1 barang akan

menempati posisi lebar mobil, dimensi 2 barang akan menempati posisi tinggi mobil,

serta dimensi 3 barang akan menempati posisi panjang mobil.

2.3.2. Fungsi objektif

Dalam melakukan penyusunan barang dengan berbagai ukuran pada mobil box, perlu

dilakukannya optimalisasi agar penyusunan yang dilakukan optimal. Di dalam

permasalahan optimalisasi ada beberapa hal yang harus ditentukan, yaitu fungsi

objektif (objective function) dan batasan (constraint). Fungsi objektif merupakan suatu

fungsi matematika yang merupakan tujuan utama pada permasalahan optimalisasi

yang harus diminimalkan atau dimaksimalkan. Sebuah solusi yang dapat

meminimalkan atau memaksimalkan (sesuai tujuan utama permasalahan) fungsi

objektif adalah solusi optimal (Kumar, 2014). Fungsi objektif pada permasalahan

optimalisasi penyusunan barang adalah untuk memaksimalkan penggunaan ruang

yang tersedia yaitu total volume barang yang dapat disusun pada suatu mobil box.

Fungsi objektif tersebut dapat dilihat pada persamaan 2.1.

(2.1)


11

Dimana : = Fungsi Objektif

= Indeks Barang

= Jumlah Barang

= Masing-masing panjang, lebar, dan tinggi barang i

= Variabel biner yang mengidentifikasi dapat atau tidaknya barang

disusun pada mobil box. Bernilai 1 jika barang berada di mobil, 0

jika tidak.

Fungsi objektif berdasarkan persamaan 2.1. di atas digunakan sebagai nilai

fitness yang dihasilkan masing-masing kandidat solusi. Namun, jika pada suatu kasus

terdapat beberapa solusi yang memiliki nilai fitness yang sama, maka akan dilakukan

pencarian nilai fitness kedua untuk menghitung total volume barang yang disusun

pada ketinggian 0 – ½ tinggi mobil box. Kandidat solusi yang memiliki nilai fitness

yang sama tersebut akan dibandingkan. Kandidat solusi yang menghasilkan total

volume barang pada ketinggian 0 – ½ tinggi mobil box lebih besar akan diambil

sebagai kandidat solusi dengan solusi terbaik. Keputusan tersebut diambil karena

mempertimbangkan kepadatan benda yang berada di bawah. Semakin padat barang-

barang yang berada di bawah, maka semakin bagus pola susunannya (Oktorini, 2008).

Contoh dua solusi yang memiliki nilai fitness sama besar dapat dilihat pada Gambar

2.5.

(a)

(b)

Gambar 2.5. (a) Susunan I; (b) Susunan II (Oktorini, 2008)


12

Pada Gambar 2.5. dapat dilihat bahwa susunan I dan susunan II memiliki nilai

fitness yang sama besar jika menggunakan perhitungan fitness dengan menghitung

total volume barang yang dapat disusun. Namun, jika dilihat dari pola susunan

penumpukan, maka susunan II lebih baik untuk diterapkan karena terdapat lebih

sedikit ruang kosong di antara tumpukan benda yang berada di bawah.

2.3.3. Batasan (constraints)

Selain menentukan fungsi objektif, pada permasalahan optimalisasi juga harus

ditentukan batasan permasalahan (constraint). Batasan atau constraint merupakan

suatu kondisi yang harus dipenuhi pada permasalahan optimalisasi. Solusi yang

dihasilkan dari fungsi objektif tidak boleh melanggar batasan-batasan tersebut.

Constraint dalam permasalahan penyusunan barang dapat dibagi menjadi dua jenis,

yaitu hard constraint dan soft constraint. Hard constraint digunakan untuk

mendefinisikan batasan yang digunakan pada proses optimalisasi, sedangkan soft

constraint digunakan untuk membentuk fungsi objektif suatu permasalahan

optimalisasi (Hicks et al., 2006).

Hard Constraint

Hard constraint merupakan batasan yang harus selalu dipenuhi. Pola penyusunan

yang melanggar hard constraint disebut solusi yang tidak layak (Bortfeldt & Wascher,

2012). Batasan-batasan dalam penyusunan barang tiga dimensi yang dikategorikan

sebagai hard constraint adalah sebagai berikut :

1. Orientasi Barang

Barang yang disusun harus berbentuk kubus atau balok yang memiliki tiga

dimensi yaitu panjang, lebar, dan tinggi. Khusus barang berbentuk balok yang

memiliki nilai berbeda untuk setiap dimensinya, terdapat barang yang bisa dan

tidak bisa dirotasi penempatannya di dalam mobil box. Barang-barang yang

dapat dirotasi akan mengalami pertukaran dimensi sebanyak enam variasi

orientasi. Sedangkan barang yang tidak dapat dirotasi tidak boleh mengalami

pertukaran dimensi, sehingga hanya memiliki satu variasi orientasi.

2. Beban Maksimum Mobil

Setiap mobil box memiliki batas beban maksimum yang dapat ditampung

mobil sehingga barang-barang yang disusun di dalam mobil tersebut tidak


13

boleh memiliki total berat yang melebihi beban maksimum yang dapat

ditampung mobil. Model matematika dapat dilihat pada persamaan 2.2.

(2.2)

Dimana : = Indeks Barang

= Jumlah Barang

= Berat barang i

= Beban maksimum mobil box

= Variabel biner yang mengidentifikasi dapat atau tidaknya

barang i disusun pada mobil box. Bernilai 1 jika barang

berada di mobil, 0 jika tidak.

3. Kapasitas Ruang Mobil Box

Penyusunan barang-barang pada penelitian ini hanya menggunakan satu buah

mobil box (single bin). Batasan kapasitas ruang mobil box digunakan agar

barang-barang yang disusun pada mobil box memiliki ukuran yang lebih kecil

atau sama dengan ukuran mobil box. Volume dari barang-barang yang disusun

tidak boleh melebihi volume box mobil. Model matematika dapat dilihat pada

persamaan 2.3.

(2.3)

Masing-masing dimensi panjang, lebar, dan tinggi barang juga tidak boleh

melebihi lebar, panjang, dan tinggi mobil. Model matematika dapat dilihat

pada persamaan 2.4.

(2.4)


14

Dimana : = Indeks Barang

= Jumlah Barang

= Masing-masing panjang, lebar, dan tinggi barang i

= Masing-masing panjang, lebar, dan tinggi mobil box

= Variabel biner yang mengidentifikasi dapat atau

tidaknya barang i disusun pada mobil box. Bernilai 1

jika barang berada di mobil, 0 jika tidak.

Soft Constraint

Soft constraint merupakan batasan yang tidak harus selalu dipenuhi untuk kondisi

tertentu. Pola penyusunan yang melanggar soft constraint masih dapat disebut solusi

layak, tetapi sedapat mungkin untuk dipenuhi dan tidak melanggar batas tertentu

(Bortfeldt & Wascher, 2012). Salah satu batasan dalam penyusunan barang tiga

dimensi yang dikategorikan sebagai soft constraint adalah stabilitas beban (load

stability). Stabilitas beban digunakan sebagai pendukung fungsi objektif dalam

menemukan solusi penyusunan yang lebih baik. Batasan ini digunakan untuk

mengurangi ruang-ruang kosong yang berada pada susunan bawah mobil sehingga

barang-barang yang berada di atasnya bisa lebih didukung oleh barang-barang yang

berada di bawahnya. Batasan ini juga digunakan untuk mengurangi kemungkinan

ambruknya barang yang berada di atas karena banyaknya ruang kosong yang berada

pada susunan di bawahnya. Solusi yang digunakan untuk menjaga stabilitas beban

mobil box adalah dengan memilih susunan yang memiliki ruang kosong paling sedikit

pada ketinggian 0 – ½ tinggi mobil box.

2.4. Algoritma Firefly

Algoritma Firefly merupakan salah satu jenis dari Swarm Intelligence. Algoritma ini

dikembangkan oleh Dr Xin-She Yang di Cambridge University pada tahun 2007.

Algoritma yang tergolong algoritma metaheuristik ini terinspirasi oleh tingkah laku

berkedipnya kunang-kunang yang menghasilkan cahaya. Menurut Yang (2009),

algoritma firefly memiliki tiga aturan umum, yaitu:


15

1. Semua kunang-kunang merupakan unisex yang menyebabkan kunang-

kunang dapat tertarik dengan kunang-kunang lain tanpa mempedulikan

gender atau jenis kelaminnya.

2. Ketertarikan kunang-kunang berbanding lurus dengan intensitas

cahayanya dan akan berkurang jika jarak di antara mereka meningkat.

Untuk setiap dua kunang-kunang berkedip, kunang-kunang dengan cahaya

yang lebih sedikit akan mendekati kunang-kunang dengan cahaya yang

lebih terang. Jika di antara mereka tidak ada salah satu yang cahayanya

lebih terang, maka ia akan bergerak secara acak.

3. Terangnya cahaya dari seekor kunang-kunang ditentukan oleh fungsi

objektif (objective function).

Berdasarkan tiga aturan dasar diatas, langkah-langkah algoritma firefly dapat

diringkas menjadi pseudo code yang dapat dilihat pada Gambar 2.6.

Gambar 2.6. Algoritma Firefly (Yang, 2009)

Algoritma firefly dimulai dengan pembentukan populasi awal firefly dimana

masing-masing firefly akan mewakilkan satu kandidat solusi permasalahan.

Kemudian, algoritma firefly akan bekerja sesuai dengan langkah-langkah yang ada

pada Gambar 2.6. Pada penerapannya, algoritma firefly memiliki tiga konsep utama

yaitu light intensity, distance, dan movement (Yang, 2009).


16

2.4.1. Light intensity (I)

Setiap firefly pada suatu populasi memiliki light intensity atau intensitas cahaya.

Intensitas cahaya tersebut digunakan sebagai penentu apakah firefly akan melakukan

pergerakan atau tidak. Firefly yang memiliki intensitas cahaya lebih besar akan

didekati oleh firefly lain yang memiliki intensitas lebih kecil. Pada permasalahan

optimalisasi penyusunan untuk memaksimalkan fungsi objektif, nilai dari intensitas

cahaya firefly akan sebanding dengan fungsi objektif dan dapat dihitung menggunakan

persamaan 2.5.

(2.5)

Dimana : = Intensitas cahaya firefly i (i = 1, 2, ... , n)

= Fungsi objektif

2.4.2. Distance (r)

Jarak antara dua buah firefly i dan j ditentukan menggunakan tabel Cartessian dan

dapat dihitung menggunakan persamaan 2.6.

(2.6)

Dimana : = Jarak antara firefly i dan firefly j

= Dimensi setiap firefly

= Banyaknya dimensi k

= Posisi firefly i pada dimensi k

= Posisi firefly j pada dimensi k

2.4.3. Movement

Pergerakan firefly terjadi apabila ada suatu firefly yang memiliki nilai intensitas

cahaya lebih kecil daripada firefly didekatnya. Firefly dengan intensitas cahaya lebih

kecil akan bergerak mendekati firefly dengan intensitas cahaya lebih besar. Laju


17

pergerakan suatu firefly i mendekati firefly j untuk mendapatkan posisi baru firefly i

dapat dihitung menggunakan persamaan 2.7.

Dimana : = Posisi firefly i yang baru

= Posisi firefly i sekarang

= Koefisien ketertarikan pada posisi 0

= Koefisien penyerapan cahaya (0.01 < < 100)

= Jarak antara firefly i dan firefly j

= Posisi firefly j

= Koefisien bilangan acak (0 < < 1)

= Bilangan acak (0 < < 1)

2.5. Library StdDraw3D

Standard Draw 3D (StdDraw3D) merupakan salah satu library Java yang digunakan

untuk membuat grafik tiga dimensi. StdDraw3D bertujuan untuk memudahkan

pengguna dalam membuat model, simulasi, dan game dengan visualisasi tiga dimensi

di dalam bahasa pemrograman Java karena script pada library ini dibuat lebih

sederhana (Martirosyan, 2011). StdDraw3D digunakan untuk membuat visualisasi

susunan barang secara tiga dimensi.

2.6. Penelitian Terdahulu

Penelitian mengenai optimalisasi penyusunan barang sudah beberapa kali dilakukan.

Optimalisasi penyusunan barang tersebut dilakukan pada ruangan atau bin yang

berbeda-beda.

Permasalahan penyusunan pallet pada kontainer pernah diselesaikan oleh

Baltacioglu pada tahun 2001. Penelitian ditujukan untuk meminimalkan volume ruang

kosong pada kontainer agar sekumpulan barang dengan ukuran berbeda-beda dapat

dimuat pada pallet di kontainer. Ia menggunakan algoritma heuristik yaitu gabungan

wall building dan layer in layer packing approach. Wall building digunakan untuk

(2.7)


18

menyusun barang pada layer yang sesuai, sementara layer in layer packing digunakan

untuk menyusun barang pada sisa layer yang masih terdapat ruang kosong. Dimensi

semua barang harus dianalisa terlebih dahulu sebelum penyusunan barang dimulai.

Hal ini dilakukan untuk menemukan beberapa nilai ketebalan layer (layerthickness)

yang paling sesuai untuk keseluruhan barang agar ruang kosong pada kontainer dapat

dikurangi. Penyusunan barang dilakukan sebanyak iterasi yang ada. Banyaknya

jumlah iterasi ditentukan oleh orientasi pallet dan nilai layerthickness. Jumlah

orientasi pallet bergantung pada dimensi pallet. Jika pallet memiliki 3 dimensi yang

sama, maka pallet hanya memiliki 1 orientasi saja. Sedangkan jika pallet memiliki 3

dimensi dengan ukuran yang berbeda-beda, maka akan ada 6 orientasi pallet. Setiap

iterasi dimulai dengan menyusun barang pada layer awal, yaitu layer dengan nilai

layerthicknes pertama yang diambil dari kumpulan layerthickness yang sudah

ditentukan sebelumnya. Jika ada 7 nilai layerthickness yang berbeda dan pallet

memiliki 3 dimensi yang berbeda, maka jumlah iterasi adalah 6*7, yaitu 42 iterasi.

Parameter yang digunakan adalah ukuran barang (panjang, lebar, dan tinggi). Semua

barang dapat dirotasi sebanyak enam orientasi. Constraints yang digunakan hanyalah

kapasitas ruang kontainer, yaitu dimensi barang tidak melebihi dimensi kontainer.

Pada penelitian ini, penyusunan yang tidak stabil diperbolehkan. Hal ini menyebabkan

ada beberapa barang yang tidak memiliki dasar, sehingga barang akan menggantung

(Baltacioglu, 2001).

Pada tahun 2008, Oktorini melakukan penelitian untuk optimalisasi

penyusunan barang dalam ruang tiga dimensi. Pada penelitiannya, ia menggunakan

algoritma Genetika untuk menyusun barang pada ruang tiga dimensi seperti kontainer.

Implementasi algoritma genetika dalam proses penyusunan barang yaitu dengan

meletakkan barang-barang yang diwakili oleh kode dan posisinya pada gen-gen dalam

suatu kromosom lalu memperhatikan bisa atau tidaknya suatu barang menempati

posisi tersebut tanpa mengubah posisi barang. Proses penempatan gen berlangsung

setiap muncul generasi baru sampai iterasi maksimum tercapai. Pada tahapan

reproduksi awal (generasi pertama), proses penempatan gen dilakukan dengan cara

randomize. Mulai generasi 2 sampai terakhir, proses penempatan gen dilakukan sesuai

hasil bilangan acak antara 0-1 yang dibangkitkan untuk mengetahui operator algoritma

genetik yang dipakai sebagai landasan penempatan gen. Individu yang memiliki nilai

fitness terbaik pada setiap generasi diikutsertakan kembali pada generasi berikutnya.


19

Hal-hal yang diperhatikan pada penyusunan barang di penelitian ini adalah beban

maksimum yang dapat ditampung ruang, beban maksimum yang dapat ditampung

barang, perotasian barang, dan letak titik berat suatu posisi barang terhadap barang

dibawahnya agar tumpukan tidak roboh dan menyebabkan kehancuran pada barang.

Nilai fitness yang digunakan didasarkan pada jumlah satuan ruang yang terisi oleh

barang, jumlah barang yang seimbang posisinya, dan jumlah barang yang utuh

(Oktorini, 2008).

Penelitian selanjutnya yang dilakukan oleh Susanto (2009) menerapkan

algoritma Greedy untuk melakukan penyusunan barang dalam kontainer. Ia juga

menerapkan metode wall building approach untuk mengisi kontainer sesuai dengan

layer yang sejajar kedalaman kontainer. Metode ini menerapkan aturan pengurutan

untuk memilih nilai layer. Kotak dengan dimensi terbesar akan dipilih untuk dimuat

pertama dan dimensinya akan dijadikan nilai layer dikarenakan kotak dengan dimensi

terbesar akan sulit untuk dimuat jika diletakkan di urutan terakhir. Setelah nilai layer

ditentukan, maka metode greedy diterapkan untuk melakukan penyusunan barang

secara horizontal di setiap potongan layer. Pada setiap layer, barang yang tersisa akan

dimasukkan secara berurutan sesuai urutan panjang barang yang terbesar terlebih

dahulu. Parameter yang digunakan pada penelitian ini adalah volume dan berat

barang, sedangkan constraint yang harus dipenuhi adalah kapasitas ruang pada

kontainer dan beban maksimal yang dapat ditampung kontainer (Susanto, 2009).

Penelitian terbaru yang dilakukan oleh Harefa (2014) mengenai penyusunan

barang menerapkan algoritma Steepest Ascent Hill Climbing untuk memvisualisasikan

penyusunan barang pada sebuah gudang. Metode tersebut diterapkan untuk

mengurutkan barang berdasarkan beratnya, sehingga urutan barang dimulai dari

barang yang memiliki berat paling besar hingga paling kecil. Barang kemudian

disusun berdasarkan urutannya dengan menggunakan metode block stacking, yaitu

barang akan disusun di atas barang sebelumnya dengan syarat berat barang yang akan

disusun tidak boleh melebihi batas maksimum beban yang dapat ditampung barang

yang berada di bawahnya. Hal-hal yang diperhatikan pada proses penyusunan barang

di penelitian ini adalah beban maksimum yang dapat ditampung barang dan kapasitas

ruang.


20

Algoritma Firefly sudah diterapkan pada permasalahan Bin Packing oleh

Kwesnady pada tahun 2013. Metode tersebut diterapkan dalam penyelesaian Two

Dimensional Bin Packing Problem dengan fungsi objektif adalah meminimalkan

jumlah mobil yang diperlukan dalam pengiriman barang. Penyusunan barang hanya

bersifat satu layer dan tidak adanya penumpukan barang, sehingga dari segi biaya

tidak dapat dihitung nilainya secara aktual. Penempatan barang ke dalam mobil box

juga tidak menggunakan rotasi, sehingga barang tidak dapat berubah posisi dari

horizontal menjadi vertikal, dan sebaliknya. Hasil penyusunan yang diperoleh dari

penggunaan algoritma firefly dapat berbeda-beda setiap kali dijalankan. Hal ini

disebabkan oleh bilangan acak yang dihasilkan pada tahap inisialisasi awal. Parameter

yang digunakan hanya dimensi panjang dan lebar barang (Kwesnady, 2013).

Algoritma firefly juga sudah digunakan untuk menyelesaikan masalah

optimalisasi kombinatorial lain, seperti Travelling Salesman Problem (TSP) oleh

Kumbharana dan Pandey pada tahun 2013. Fungsi tujuan dari permasalahan ini adalah

meminimalkan jarak yang harus ditempuh untuk mengunjungi semua kota yang ada.

Pada penelitian ini algoritma firefly diubah menjadi diskrit untuk menyelesaikan

permasalahan permutasi. Tahapan inisialisasi awal dilakukan dengan menghasilkan

urutan permutasi secara acak yang merupakan urutan kota yang akan dikunjungi.

Kriteria berhenti yang digunakan pada penelitian ini adalah stagnasi, yaitu keadaan

dimana hasil yang didapatkan stabil atau tidak ada lagi terjadi peningkatan. Ia juga

membandingkan kinerja algoritma firefly dengan beberapa algoritma metaheuristik

lain seperti Ant Colony Optimization (ACO), Genetic Algorithm (GA), dan Simulated

Annealing (SA). Hasil yang didapatkan oleh algoritma firefly dari implementasi

menggunakan 6 jenis data rute kota lebih baik, yaitu menghasilkan total jarak tempuh

yang lebih sedikit dibandingkan yang dihasilkan oleh ketiga algoritma tersebut

(Kumbharana dan Pandey, 2013). Rangkuman dari penelitian terdahulu dapat dilihat

pada Tabel 2.1.


21

Tabel 2.1. Penelitian Terdahulu

Constraints :

kapasitas ruang; beban maksimum

ruang; beban maksimum tumpukan

barang; orientasi barang

3. Susanto

(2009)

Algoritma

Greedy

Fungsi objektif :

meminimalkan ruang kosong pada

kontainer

Constraints :


ruang; orientasi barang

4. Harefa

(2014)

Algoritma

Steepest Ascent

Hill Climbing

Fungsi objektif :

memaksimalkan ruang terisi pada

kontainer

Constraints :


tumpukan barang

No. Peneliti

(Tahun)

Metode Keterangan

1. Baltacioglu

(2001)

Wall building

approach dan

Layer-in-layer

packing

Fungsi objektif :

meminimalkan ruang kosong pada

kontainer

Constraints :

kapasitas ruang kontainer

2. Oktorini

(2008)

Algoritma

Genetika

Fungsi objektif :

memaksimalkan ruang terisi, jumlah

barang seimbang, dan jumlah barang

utuh.


22

Tabel 2.1. Penelitian Terdahulu (lanjutan)

No. Peneliti

(Tahun)

Metode Keterangan

5. Kwesnady

(2013)

Algoritma

Firefly

Fungsi objektif :

meminimalkan jumlah mobil box yang

digunakan untuk pengiriman barang

Constraints :

kapasitas ruang

6. Kumbharana

& Pandey

(2013)

Algoritma

Firefly

Fungsi objektif :

meminimalkan jarak yang ditempuh

untuk mengunjungi semua kota

Constraints :

masing-masing kota dikunjungi hanya

sekali

Perbedaan penelitian yang dilakukan dengan penelitian terdahulu adalah

penggunaan algoritma firefly dalam menyelesaikan permasalahan bin packing dengan

penambahan unsur tinggi (three dimensional packing problem). Penyusunan barang

dilakukan pada mobil box dan bersifat tiga dimensi sehingga dapat memungkinkan

terjadinya penumpukan barang. Parameter yang digunakan adalah volume barang,

volume mobil box, berat barang, beban maksimum mobil, dan perotasian barang.

Fungsi objektif yang digunakan pada penelitian ini adalah memaksimalkan total

volume barang yang dapat disusun pada mobil box. Adapun constraints yang

digunakan pada penelitian ini adalah sebagai berikut :

1. Masing-masing barang memiliki posisi yang unik sehingga tidak akan terjadi

barang yang saling tumpang tindih (overlapping).

2. Barang-barang yang tidak berada di dasar mobil box harus didukung oleh

barang yang berada dibawahnya, sehingga tidak akan terjadi barang yang

menggantung atau melayang (overhang).

3. Masing-masing dimensi barang tidak boleh melebihi masing-masing dimensi

mobil box, dan total volume barang tidak boleh melebihi volume ruang pada

mobil box.


23

4. Total berat barang yang disusun pada mobil box tidak boleh melebihi beban

maksimum yang dapat ditampung mobil box.

5. Barang-barang yang memiliki sifat tidak dapat dirotasi tidak boleh mengalami

pertukaran dimensi pada saat penyusunan barang pada mobil box, sementara

barang-barang yang memiliki sifat dapat dirotasi boleh mengalami pertukaran

dimensi sebanyak enam variasi orientasi.

6. Untuk solusi yang menghasilkan nilai fitness yang sama, maka akan dilakukan

pencarian nilai fitness kedua yaitu mencari susunan dengan ruang kosong

paling sedikit di ketinggian 0 - 1/2 tinggi mobil box. Hal ini dilakukan untuk

menjaga keseimbangan barang dan mengurangi resiko barang yang ambruk ke

bawah (load stability).


chapter ii

Documents