Algoritmo de embalagem 3d para envio de itens

Recebi uma tarefa para criar uma estimativa de remessa que sugira a melhor acomodação de mercadorias com o menor número possível de caixas:

1. Existe um conjunto finito de tamanhos de caixas retangulares conhecidos

2. Há muitos itens retangulares arbitrários para serem embalados dentro de caixas

3. O menor número de caixas deve ser usado da melhor maneira. Como enviar duas caixas 1x1x1 é muito mais caro que uma caixa 1x2x1. Essa deve ser a prioridade aqui.

4. Também deve ser otimizado para usar as caixas menores quanto possível, como uma prioridade de segundo nível. (por exemplo: se for apresentada uma escolha entre uma caixa maior e duas pequenas, deverá escolher a caixa maior)

5. Os itens podem ser girados para caber na caixa, mas a rotação deve ser limitada a incrementos de 45 ° no mínimo (em minhas pesquisas, parece que algumas configurações permitem uma rotação de 45 graus para melhor encaixar as caixas retangulares dentro de uma caixa retangular maior) , sendo rotações de 90 ° o padrão a ser adotado.

6. As caixas têm um limite de peso e os itens têm pesos arbitrários (por exemplo: um item com tamanho de 1x1x1 pode ser mais conveniente do que outro item de 2x2x2)

Pesquisei um pouco e encontrei alguns algoritmos abstratos sobre empacotamento de lixeira e o problema da mochila e vim com a seguinte variação de força bruta, semelhante ao algoritmo de melhor ajuste:

1. Classifique os itens em ordem decrescente de volume (maior primeiro) na lista "itens a serem embalados"

2. Para cada item desta lista:

   1. Escolha a caixa menor que está na lista "caixas usadas" e tem limite de volume e peso restante suficiente para caber no item (usarei fit aqui para significar o ajuste das dimensões e peso)

   2. Se não houver essa caixa, crie uma nova caixa a partir do conjunto conhecido de possíveis tamanhos de caixa, que seja o menor tamanho que possa caber nas dimensões e peso do item e adicione-o à lista de "caixas usadas".

   3. Se uma caixa couber no item (usando a função de encaixe abaixo), adicione-a à lista de "itens desta caixa" e remova-a da lista "itens a caber", marcando sua posição 3d relativa dentro da caixa.

   4. Repita do item 2.1 até que não exista nenhum item na lista "itens a serem embalados".

A função de verificação de encaixe usada na etapa 2 acima:

1. Verifique se o volume restante da caixa corresponde ao volume do item. Caso contrário, retorne false.

2. Verifique se a soma do peso dos "itens da caixa" mais o peso do item atual é menor ou igual ao limite de peso da caixa. Caso contrário, retorne false.

3. Marque a lista "itens da caixa" para escolher a primeira coordenada da caixa que tenha o menor componente Y e que tenha espaço suficiente para a largura, profundidade e altura do item, considerando os outros itens colocados como espaço indisponível.

4. Se o item não se encaixar na orientação atual, gire-o em uma das 6 rotações possíveis, não assumindo rotações de 45 ° por simplicidade. (As rotações que resultam em tamanhos que já testados podem ser pulados. Por exemplo: girar uma caixa 180 ° fornece as mesmas dimensões da posição original, porque todas as caixas e itens têm o mesmo tamanho para faces opostas e, portanto, podem ser pulados.)

5. Se o item não tiver sido rotacionado de todas as formas possíveis, de volta à sua orientação original, tente novamente a partir da etapa 3.

6. Se todas as rotações foram tentadas e nenhum ajuste foi encontrado, considere a coordenada atual como espaço indisponível.

7. Se não houver espaço disponível para verificação, retorne false. Caso contrário, tente novamente a partir da etapa 3.

Quero saber se pode haver uma melhor solução para o meu problema, dadas as restrições apresentadas.

Isso parece funcionar na teoria, mas eu não tentei no código. Desejo saber se estou indo na direção certa ou se há maneiras melhores e com melhor desempenho.

Referências seria ótimo.

Editar:

Encontrei algumas APIs de terceiros interessantes que fazem o que eu quero, mas isso precisa ser desconectado, por isso não terei acesso a elas.

Alguns exemplos são:

• http://v2.3dbinpacking.com/demo/main
• http://www.packit4me.com/api

Edição 2:

Um exemplo do mundo real de problema a ser resolvido seria:

• Tenho 4 tamanhos de caixa LxAxP: 10x12x18, 12x16x24, 16x20x30, 24x32x40
• Tenho um pedido de 4 itens, sendo 1 do tamanho 6x8x10, 2x 22x14x30 e 1x 22x4x20

Como encaixo esses itens em qualquer quantidade de caixas de um ou mais tamanhos usando o menor número possível de caixas, usando as menores caixas possíveis e deixando menos espaço livre possível?

A embalagem do compartimento é muito computacionalmente difícil. Pense na metade do problema: você deseja embalar o produto em caixas de remessa sem desperdício na caixa. Uma solução ideal para isso exigiria passar por todos os subconjuntos possíveis e todos os arranjos 3D possíveis do produto que precisam ser enviados em um caminhão. Darei a solução ideal para isso, porque tenho um amigo que faz seis coisas impossíveis antes do café da manhã.

Agora você só precisa colocar todas as caixas no caminhão sem desperdício. Meu amigo faz a segunda coisa impossível e dá a solução. Infelizmente, com os tamanhos de caixa selecionados acima, há espaço vazio no caminhão que pode ser reduzido se você escolher caixas diferentes (maiores ou menores) na primeira tarefa. Se você alterar o tamanho de uma caixa, na melhor das hipóteses você terá que reembalar o caminhão; na pior das hipóteses, pode ser necessário reembalar todas as caixas, o que é tão difícil quanto o problema com o qual começamos. E, como no primeiro estágio, você teria que tentar todos os arranjos possíveis em 3D.

Achei o Manual de Design de Algoritmos de Skiena útil para pensar sobre que classe de algoritmos se adequa a quais tipos de problemas, mas aprendi principalmente que boas soluções para até mesmo problemas mundanos surgem em você com dificuldade computacional. A maior parte do que você está precisando se encaixa na classe de problemas de embalagem de lixeira e esse artigo é um bom ponto de partida. Vale ressaltar que alguns dos melhores algoritmos para isso são produtos comerciais, porque essa tarefa aparece em toda parte na logística (qual é o menor número de vagões de trem nos quais posso transportar minhas mercadorias? E tal). Há um dinheiro considerável a ser ganho se as heurísticas corretas puderem salvar um fabricante de 100 vagões por mês.

Infelizmente, a literatura sobre otimização de heurísticas não é tão grande quanto em algoritmos. Se você tentar fazer isso sozinho, garanto que estará sonhando com a mudança de prismas retangulares no seu segundo mês. Eu tinha um problema de estocagem que, se tivesse que fazer novamente, provavelmente iria procurar os especialistas (ou o software apropriado).

Obrigado a @JTrana pela boa expansão do meu comentário.

Ao criar novos algoritmos, e recentemente criei um algoritmo de empacotamento sozinho (sei que ele ainda tem algum potencial de otimização), sempre faço a abordagem mais simples:

Como eu faria isso como humano, e tentaria traduzi-lo em um algoritmo: Do ​​meu professor de inteligência artificial (robótica) Rolf Pfeifer Eu ainda tenho em mente que a inteligência aparente às vezes pode ser criada com algumas regras muito simples, então, em vez de superengenharia Eu tento ser engenheiro

1. Identifique itens muito grandes (itens que não cabem em nenhuma caixa)
2. Tente encontrar a melhor caixa possível (comparando o volume total e as dimensões do item)
3. Encomende itens de grande a pequeno e caixas (espaços) de pequeno a grande
4. Coloque o item maior no menor espaço possível
5. Se o item maior não encontrar, pule sobre ele e tente o próximo até que nada mais caiba

6. Para os itens restantes, procure a nova melhor caixa. ...

   X. sempre pense em eventos excepcionais (itens de tamanho grande, formas estranhas, se uma caixa contiver apenas 1 item, não seria melhor enviar item sem caixa ?, etc.), mas você também pode fazer uma heurística na forma de uma decisão árvore.

É claro que existem mais advertências quanto mais você recebe, apenas dou essas idéias como ponto de partida. A partir daí, existem muitas maneiras possíveis. Uma alternativa seria dividir uma caixa em pequenos cubos (por exemplo, 5cmx5cmx5cm) e rastreá-los como ocupados / livres. Outra abordagem poderia ser chamada de 3d tetris, etc.

Com essa abordagem, você não precisa necessariamente se preocupar com explosão combinatória. Por outro lado, uma explosão combinatória pode acontecer se estivermos falando sobre cargas de trem de itens, mas novamente: você realmente acha que uma empresa verificará a lista de embalagem item por item? Não, eles abordarão uma solução de divisão e conquista: divida a complexidade usando volumes padronizados (por exemplo, paletas ou caixas de tamanho fixo). Portanto, mesmo por questões de praticidade, leve em consideração que não apenas os trens, às vezes o tempo dos funcionários também é dinheiro. um trem pode carregar x paletas, cada paleta tem volume fixo, então empacote itens na paleta, mas, novamente, talvez um palete consista em várias ordens; portanto, use caixas fixas para os itens, que serão carregados nos paletes, que serão carregados em trens.

Pelo menos é assim que eu, como humano, lidaria com a tarefa, pegaria a melhor caixa e encaixaria o maior item, um por um, no menor espaço disponível (e acrescentaria um pouco de visualização).

Como no meu algoritmo, no final, você provavelmente não terá a melhor solução, mas uma heurística muito boa que você poderá refinar ainda mais.

Às vezes é mais fácil começar com o primeiro passo e resolver problemas no caminho, bem fora do curso, idealmente não é um tipo de passo além do limite, mas um pouco inteligente ... às vezes você pode ser forçado a explorar alternativas e escolher o melhor ou implementar um "passo atrás".

Mas, como aprendi com meu professor de IA (Rolf Pfeifer, desculpe-me por incomodá-lo novamente): Às vezes, você pode criar um comportamento inteligente aparente com alguns comportamentos emergentes muito simples e com poucos conjuntos de regras no exemplo mencionado, que programaram pequenos carros remotos para virar à esquerda se eles detectam um obstáculo no lado direito, vire à direita se houver um obstáculo no lado esquerdo e siga em frente se não houver nenhum obstáculo ou se o obstáculo estiver na frente. 3 ou 4 robôs assim, colocados em um quadrado de 3m x 3m com muitas bolas de pingue-pongue, levam ao fato surpreendente de que os robôs pareciam estar limpando, empurrando as bolas de ping-pong para os cantos, mesmo que os robôs estejam somente programado para evitar obstáculos.

PD: O único desvio no mundo real que encontrei dessa abordagem é quando eu trabalhava meio período em grandes concertos como metal, donzela de ferro, britney spears, paul mcCartney, U nome ... Os caminhoneiros trabalhando no passeios internacionais têm listas de embalagem precisas item por item. Os cálculos são feitos uma vez (não sei por humanos ou máquinas) e depois replicados. Às vezes, quando fazem as malas pela primeira vez, eles até fazem fotos de camada por camada e a colam no caminhão apenas para que as equipes locais saibam exatamente qual caixa deve ser carregada quando e onde. Mas essa também é uma necessidade específica de embalagem, pois em uma excursão eles sempre trabalham com as mesmas caixas e caminhões.

A heurística mencionada em sua postagem parece interessante.

Eu sugeriria algumas modificações para melhorar a solução final.

Dada uma solução com todos os itens embalados em uma caixa, tente mesclar o conteúdo de duas caixas pequenas em uma caixa maior (isso deve ajudar a melhorar seus critérios de usar o menor número possível de caixas).

Como alternativa, toda vez que você inicia uma nova caixa, em vez de usar a menor caixa que pode acomodar o item atual, você pode escolher a maior caixa que pode acomodá-lo e, uma vez que cada item é atribuído a uma caixa, tente atribuir todos os itens de uma caixa. caixa para uma caixa menor.

Além disso, em sua função de ajuste, em vez de considerar a posição de suas outras caixas como fixa, você pode imaginar alterar a sequência de carregamento. Isso deve permitir que você encontre melhores soluções à custa de um tempo de execução mais longo.