Sasaran masalah packing adalah menemukan cara terbaik untuk mengemas sekumpulan item dengan ukuran tertentu ke dalam container dengan packing tetap. Aplikasi standar memuat kotak ke truk pengiriman secara efisien. Sering kali, barang tidak dapat dikemas karena keterbatasan kapasitas. Dalam hal ini, masalahnya adalah menemukan subset item dengan ukuran total maksimum yang akan muat dalam penampung.
Ada banyak jenis masalah pengemasan. Dua yang paling penting adalah masalah knapsack dan pengemasan bin.
Masalah knapsack
Pada soal sederhana, ada satu kontainer (knapsack). Item memiliki nilai serta ukuran, dan tujuannya adalah untuk memaketkan subkumpulan item yang memiliki nilai total maksimum.
Untuk kasus khusus saat nilai sama dengan ukuran, sasarannya adalah memaksimalkan ukuran total item yang dikemas.
OR-Tools menyediakan beberapa pemecah masalah untuk masalah knapsack dalam library algoritma.
Ada juga versi yang lebih umum dari masalah knapsack. Berikut beberapa contohnya:
Masalah ransel multidimensi, ketika item memiliki lebih dari satu kuantitas fisik, seperti berat dan volume, dan knapsack memiliki kapasitas untuk setiap kuantitas. Di sini, istilah dimensi tidak selalu merujuk pada dimensi spasial tinggi, panjang, dan lebar yang biasa. Namun, beberapa masalah mungkin melibatkan dimensi spasial, misalnya, menemukan cara optimal untuk mengemas kotak persegi panjang ke dalam tempat penyimpanan persegi panjang.
Beberapa masalah knapsack, yang memiliki beberapa knapsack, dan tujuannya adalah untuk memaksimalkan total nilai item yang dikemas di semua knapsack.
Perhatikan bahwa Anda dapat memiliki masalah multidimensi dengan satu knapsack, atau beberapa masalah knapsack hanya dengan satu dimensi.
Masalah {i>bin-packing<i}
Salah satu masalah pengemasan yang paling terkenal adalah bin-packing, yang mana ada beberapa kontainer (disebut bin) dengan kapasitas sama. Tidak seperti masalah beberapa knapsack, jumlah tempat sampah tidak tetap. Sebaliknya, tujuannya adalah menemukan jumlah tempat terkecil yang akan menampung semua item.
Berikut ini contoh sederhana untuk mengilustrasikan perbedaan antara masalah {i>multiple knapsack<i} dan masalah {i>bin-packing<i}. Misalkan sebuah perusahaan memiliki truk pengiriman, yang masing-masing memiliki kapasitas berat 18.000 pon, dan 130.000 pon barang untuk dikirimkan.
Beberapa knapsack: Anda memiliki lima truk dan ingin memuat subset item yang memiliki berat maksimum.
Pengemasan tempat sampah: Anda memiliki 20 truk (lebih dari cukup untuk menampung semua barang) dan ingin menggunakan truk paling sedikit yang dapat menampung semuanya.
Bagian berikut menunjukkan cara menyelesaikan berbagai jenis masalah pengemasan dengan OR-Tools, dimulai dengan masalah knapsack.