blognya komarudin bin sayuti

blognya komarudin bin sayuti header image 2

Three Dimensional Bin Packing Problem

September 17th, 2011 · 17 Comments

Pernahkah anda menghadapi keadaan ketika anda perlu memuat sejumlah barang ke dalam kardus? Seperti pindahan rumah misalnya. Kalau kita tidak telaten dan tidak terbiasa mengepak seperti istri saya, barang dengan panjang, lebar dan tinggi yang berbeda-beda akan menimbulkan banyak ruang-ruang kosong. Akibatnya, jumlah kardus yang kita pakai bisa jadi lebih banyak dari jumlah kardus yang kita butuhkan. 

Mungkin karena hal ini hanya terjadi sekali-sekali, maka kita tidak perlu terlalu memikirkan efisiensi dari proses ini. Saya pribadi hanya perlu minta tolong sama istri saya yang baik hati dan tidak sombong. Lain halnya dengan industri layanan kurir dan logistik yang sehari-hari harus memuat berbagai macam barang dengan ukuran yang berbeda-beda ke dalam truk, kontainer, atau kabin barang pesawat. Begitu juga dengan perusahaan (workshop) yang mengekspor ke luar negeri produk-produk customized seperti perusahaan ini [1].

Untungnya, permasalahan ini telah dimodelkan oleh para ahli dengan nama three dimensional bin packing problem (3D-BPP), atau terkadang disebut juga container loading problem. Model ini adalah model dasar yang dapat dikembangkan menjadi model-model turunan yang lebih kompleks.

Pada model 3D-BPP, kita memiliki barang dengan ukuran berbeda-beda yang kita sebut dengan box dengan jumlah tertentu. Selain itu, kita memiliki sejumlah wadah/tempat/kardus/kontainer sebagai tempat memuat barang tersebut yang kita sebut dengan bin. Pada permasalahan ini, kita ingin meminimumkan jumlah bin yang kita gunakan agar semua box dapat dimuat ke dalamnya. Sehingga, keputusan yang perlu diambil adalah mengatur lokasi (sumbu-x, sumbu-y, dan sumbu-z) box-box di dalam bin.

Pada model ini, terdapat beberapa kendala yang harus dipenuhi, yakni:

  • Setiap box diletakkan hanya di salah satu bin
  • Setiap box tidak boleh diletakkan di dalam box yang lain (tidak boleh beririsan)
  • Setiap box diletakkan di dalam bin (tidak boleh ada bagian box yang keluar bin)

Selain itu, seorang modeler juga bisa menambahkan kendala-kendala lain misalnya ada sejumlah barang yang harus diletakkan di bawah, ada barang yang tidak boleh diputar, dan lain sebagainya.

Berikut adalah hasil penelitian saya bersama mahasiswa saya Fadhillah Meizi Ramadhan (kerja di mana ni anak sekarang yak). Metode yang digunakan sebenarnya ada dua bagian. Bagian pertama akan mengatur urutan peletakan barang, sementara bagian kedua menggunakan aturan extreme point method [2] untuk meletakkan barang di posisi yang paling menguntungkan. Untuk bagian pertama kami menyediakan sebagian metode pengurutan heuristik sebagamana pada paper. Selain itu, kami juga mengimplementasikan algoritma genetika guna mendapatkan solusi yang lebih bagus untuk bagian yang pertama.

Untuk programnya, mangga didonlod di dieu:

GABPP

Pada file zip di atas, ada contoh problem sebagai berikut:

Ukuran Bin: 8 x 8 x 5

Jumlah Box: 20

Ukuran Box:

  • box 1: 1 4 2
  • box 2: 2 5 2
  • box 3: 1 3 3
  • box 4: 3 2 2
  • box 5: 2 1 2
  • box 6: 2 4 1
  • box 7: 2 5 3
  • box 8: 3 3 3
  • box 9: 4 2 3
  • box 10: 2 5 2
  • box 11: 3 4 5
  • box 12: 2 5 2
  • box 13: 3 2 3
  • box 14: 3 2 5
  • box 15: 2 1 2
  • box 16: 1 5 1
  • box 17: 2 5 2
  • box 18: 3 3 2
  • box 19: 3 2 2
  • box 20: 2 4 2

Ketika digunakan, tampilan programnya akan seperti ini:

Sori saya nggak buat gambar 3D-nya, ada yg mau tugas akhir mengimplementasikan 3D library dan menggabungkannya dg program di atas? 🙂

 

[1] Perusahaan ini adalah salah satu awal kisah cinta saya dengan si dia, cuit cuit…

[2] Teodor Gabriel Crainic, Guido Perboli, and Roberto Tadei. 2008. Extreme Point-Based Heuristics for Three-Dimensional Bin Packing. INFORMS J. on Computing 20, 3 (July 2008), 368-384. DOI=10.1287/ijoc.1070.0250 http://dx.doi.org/10.1287/ijoc.1070.0250

Print Friendly, PDF & Email

Tags: Packaging

17 responses so far ↓

  • 1 raskhy // Dec 10, 2011 at 12:13 pm

    agan, bisa mintaprogramnya yang untuk gambarnya juga???untuk skripsi….kalo bisa tolong kirim ke email saya…terima kasih

  • 2 Komarudin // Dec 10, 2011 at 6:52 pm

    Maaf gan, waktu itu kita juga bikin gambarnya manual

  • 3 Gayatri Ratna // Sep 19, 2014 at 7:39 am

    Pak Komar, sekedar info aja kalau Fadhillah skrg kerja di PT Pamapersada (Mining Company).

  • 4 Komarudin // Sep 23, 2014 at 9:49 am

    Sip, makasih info-nya

  • 5 sukhoi 150 // Jun 15, 2012 at 9:12 pm

    Pak komar kan jago bikin algoritma / source code, sekalian aja bikin di AutoLISP. AutoCad.. dijamin langsung nongoL dah itu Gambar Box disusun susun..
    Salam AnTek.

  • 6 halim // Jul 19, 2012 at 9:11 am

    pak saya mau tanya ni programnya kan bwy box..
    gmn klu kasus yang dihadapi adalah ada sbuah plat dengan panjang dan lebar tertentu , namun kita punya beberapa pola potong yang harus di potong dari plat tersebut..
    untuk mencari pola potong yang maksimal dengan menggunakan jumlah bahan baku (plat awal) tadi..apakah dapat dimodelkan?

  • 7 Komarudin // Jul 19, 2012 at 6:17 pm

    Pak Halim bisa coba mengeksplorasi tentang cutting stock problem, VLSI optimization dan machine layout problem.

  • 8 halim // Aug 6, 2012 at 10:31 am

    ow itu,,bapak ada thrednya?ato cari di google saya??wkkw
     
    oh ya pak saya mau tanya ttg algortima differential evolution untuk pnjdwalan produksi..itu gmn y metode e?mw bwt skripsi saya,,tp masih blum dpt ide bwt judul e @@

  • 9 baiq nurul srifathona // Feb 23, 2015 at 4:03 am

    contoh kasus nyata bpp ini dapat diaplikasikan pada apa ya? seperti perusahaan apa sebagai studi kasusnya. untuk skripsi pak komar. mohon pencerahannya, saya tertarik mengangkat bpp sebagai tema skripsi saya.

  • 10 Komarudin // Feb 23, 2015 at 7:24 pm

    Halo Baiq, perusahaan yg berkutat dengan permasalahan ini biasanya bergerak di bidang transportasi/pengiriman barang.

  • 11 masayu // Mar 13, 2015 at 5:18 am

    Pak, saya pnya TA ttg 3dmnsi juga, pnjgxlebarxtinggi. Nama software ini apa ya pak?

  • 12 Komarudin // Mar 16, 2015 at 12:13 pm

    Halo masayu, namanya GABPP. Silahkan dilihat di file-nya.

  • 13 baiq nurul srifathona // May 3, 2015 at 4:57 am

    Pak Komar, saya ingin mengetahui cara manual proses penyusunan pada bin packing 3D. Sekiranya bolehkan saya meminta kontak email bapak? Terkait TA saya pak. Terimakasih sebelumnya 🙂

  • 14 Komarudin // May 3, 2015 at 4:13 pm

    Halo baiq,
    Cara manualnya bisa dibaca di paper ini:
    Teodor Gabriel Crainic, Guido Perboli, and Roberto Tadei. 2008. Extreme Point-Based Heuristics for Three-Dimensional Bin Packing.

    email saya bisa dilihat di halaman about:
    https://staff.blog.ui.ac.id/komarudin74/about/

  • 15 KRESNA BIMA SUDIRGO // Apr 11, 2019 at 8:14 pm

    Pak Komar, Saya ingin bertanya apakah metode ini dapat digunakan untuk benda2 yang tidak berbentuk box (misal: Drum, Bola, dsb)? jika iya apakah kita harus menganggap benda tersebut sebagai box dengan mengukur panjang lebar dan tinggi?

  • 16 Kresna Bima S // Apr 11, 2019 at 8:22 pm

    Pak Komarudin, Pak apakah software ini hanya khusus untuk cargo berbentuk box? bagaimana untuk cargo seperti drum, bola dsb? dapatkah kita melaakukan pendekatan dengan mengukur dimensi cargo dan mengasumsikan sebagai box?

  • 17 Komarudin // Apr 22, 2019 at 4:50 pm

    Saya belum pernah meneliti untuk yg non-rectangular