O objetivo dos problemas de packing é encontrar a melhor maneira de empacotar um conjunto de itens de determinados tamanhos em contêineres com packing fixas. Um aplicativo típico é carregar caixas em caminhões de entrega com eficiência. Muitas vezes, não é possível empacotar todos os itens devido às restrições de capacidade. Nesse caso, o problema é encontrar um subconjunto de itens com tamanho total máximo que caiba nos contêineres.
Há muitos tipos de problemas no empacotamento. Dois dos mais importantes são os problemas de mochila e o pacote de funções.
Problemas com mochila
No problema simples da mochila, há um único contêiner (uma mochila). Os itens têm valores e tamanhos, e a meta é empacotar um subconjunto dos itens que tenha valor total máximo.
Para o caso especial em que o valor é igual ao tamanho, o objetivo é maximizar o tamanho total dos itens embalados.
O OR-Tools fornece vários solucionadores para problemas de knapsack na biblioteca de algoritmos dele.
Há também versões mais gerais do problema da mochila. Aqui estão alguns exemplos:
Problemas de mochila multidimensionais, em que os itens têm mais de uma quantidade física, como peso e volume, e a mochila tem uma capacidade para cada quantidade. Aqui, o termo dimensão não se refere necessariamente às dimensões espaciais normais de altura, comprimento e largura. No entanto, alguns problemas podem envolver dimensões espaciais, por exemplo, encontrar a maneira ideal de empacotar caixas retangulares em uma caixa de armazenamento retangular.
Vários problemas de mochila, em que há várias mochilas, e o objetivo é maximizar o valor total dos itens embalados em todas as mochilas.
Você pode ter um problema multidimensional com uma única mochila ou um problema multidimensional com apenas uma dimensão.
O problema do empacotamento
Um dos problemas de empacotamento mais conhecidos é o bin-packing, em que há vários contêineres (chamados de bins) com a mesma capacidade. Ao contrário do problema de várias mochilas, o número de agrupamentos não é fixo. Em vez disso, o objetivo é encontrar o menor número de agrupamentos que conterão todos os itens.
Veja um exemplo simples para ilustrar a diferença entre o problema com várias mochilas e o problema de empacotamento. Suponha que uma empresa tenha caminhões de entrega, cada um com uma capacidade de peso de 18.000 libras e 130.000 libras de itens para entregar.
Várias mochilas: você tem cinco caminhões e quer carregar um subconjunto dos itens com peso máximo.
Empacotamento de lixo: você tem 20 caminhões (mais do que o suficiente para conter todos os itens) e quer usar o menor número possível de caminhões para conter todos eles.
As seções a seguir mostram como resolver vários tipos de problemas de empacotamento com ferramentas OU, começando com o problema da mochila (link em inglês).