Solucionador de Problemas de Empacotamento de Compartimento 2D
Esta calculadora online tenta resolver um problema de empacotamento bidimensional (2D) offline utilizando o algoritmo Heurístico de Retângulos Máximos
Esta calculadora online deve ajudá-lo a responder a perguntas como quantas placas são necessárias caso você encaixe uma série de retângulos menores de várias dimensões de comprimento e largura (CxL) em retângulos maiores com dimensões fixas de comprimento e largura (CxL).
Por exemplo, você é um fabricante de bancadas e precisa descobrir quantas placas de um determinado tamanho precisa pedir para um trabalho específico. Deste modo, a quantidade de material necessária deve ser separada em uma série de pequenos retângulos (veja este pedido).
A seguir, você deve inserir as dimensões da placa mestre no formato Comprimento x Largura, em seguida as dimensões das peças retangulares e suas quantidades, no formato Comprimento x Largura x Quantidade um tipo de retângulo por linha.
Na verdade, este é um problema de Empacotamento de Compartimento Retangular Bidimensional. A calculadora irá tentar encontrar o melhor layout que conseguir, mas ela não garante a solução ideal. Para ter acesso aos detalhes científicos, vá até a seção de teoria abaixo da calculadora.
Solucionador de Problemas de Empacotamento de Compartimento 2D
Dimensões do Compartimento
Retângulos para Empacotar
Empacotamento de Compartimento Retangular Bidimensional
Ok, então aqui lidamos com o problema de empacotamento de compartimento retangular bidimensional. Em qualquer problema de empacotamento de compartimento, você recebe alguns contêineres (em nosso caso, o contêiner é uma região retangular 2D). Um conjunto de objetos (novamente, em nosso caso, são retângulos menores) deve ser empacotado em um ou mais contêineres. O objetivo geralmente é empacotar todos os objetos utilizando o mínimo de contêineres possível.
Se o conjunto de objetos a serem empacotados for conhecido de antemão, o problema é chamado de 'offline', ao contrário do problema 'online', onde os objetos aparecem um a um. Então, aqui precisamos lidar com o problema de empacotamento do compartimento retangular 2D offline.
Este é um dos problemas clássicos em otimização combinatória e provou ser NP-difícil. Dessa forma, só podemos aproximar a solução ótima através de algoritmos heurísticos.
Esta implementação particular do solucionador de problemas de empacotamento de compartimento 2D se baseia nos Algoritmos de Retângulos Máximos. Esta heurística é uma extensão da heurística Guillotine Split e mostra excelentes resultados para empacotamento offline1
A ideia da heurística de Retângulos Máximos é manter o controle de todos os espaços retangulares livres máximos, que ainda estão disponíveis após a colocação de um objeto no contêiner (veja a imagem abaixo).
Também existem regras diferentes para escolher qual retângulo colocar em qual compartimento. Aqui nós usamos a abordagem global, o que significa que em cada etapa, calculamos a 'pontuação' para cada retângulo remanescente e cada espaço livre restante, e então escolhemos a combinação que nos dá a melhor pontuação. Quanto à regra de colocação específica, esta implementação verifica quatro delas e, em seguida, escolhe a regra que produz o melhor resultado (ou seja, utiliza uma quantidade mínima de compartimentos).
As regras de colocação são:
- Inferior Esquerdo - a coordenada y do lado superior do retângulo deve ser a menor. Em caso de empate, aquele com o menor valor de coordenada x é usado.
- Melhor Ajuste Lateral Curto - a área de espaço livre deve ter o comprimento mínimo do lado restante mais curto.
- Melhor Ajuste Lateral Longo - a área de espaço livre deve ter o comprimento mínimo do lado restante mais longo.
- Melhor Ajuste de Área - a área de espaço livre deve ser a menor na área para colocar o próximo retângulo. Em caso de empate, a regra do Melhor Ajuste Lateral Curto é utilizada.
-
A Thousand Ways to Pack the Bin (Mil Maneiras de Empacotar o Compartimento) - A Practical Approach to Two-Dimensional Rectangle Bin Packing (Uma Abordagem Prática para Empacotamento de Compartimentos Retangulares Bidimensionais) por Jukka Jylänki ↩
Comentários