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.

PLANETCALC, Solucionador de Problemas de Empacotamento de Compartimento 2D

Solucionador de Problemas de Empacotamento de Compartimento 2D

Dimensões do Compartimento

Retângulos para Empacotar

Compartimentos necessários
 
O arquivo é muito grande; pode ocorrer lentidão do navegador durante o carregamento e a criação.
O arquivo é muito grande; pode ocorrer lentidão do navegador durante o carregamento e a criação.

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).

Acompanhe os retângulos sobrepostos
Acompanhe os retângulos sobrepostos

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:

  1. 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.
  2. Melhor Ajuste Lateral Curto - a área de espaço livre deve ter o comprimento mínimo do lado restante mais curto.
  3. Melhor Ajuste Lateral Longo - a área de espaço livre deve ter o comprimento mínimo do lado restante mais longo.
  4. 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.

  1. 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 

URL copiado para a área de transferência
PLANETCALC, Solucionador de Problemas de Empacotamento de Compartimento 2D

Comentários