Algoritmo de embalagem 3d para envio de itens

24

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:

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?

Ricardo Souza
fonte
4
Não há necessidade de uma packingtag relacionada; algorithmssufixos :)
Chris Cirefice
Estou curioso, a embalagem real será realizada por robôs ou humanos? Nesse caso, a otimização do espaço valerá o tempo necessário para descobrir como girar cada caixa para encaixá-la?
Fora do dia
Boa pergunta. A embalagem real será feita por humanos, mas o software sugerirá a ordem e a posição da embalagem de cada caixa. Não será necessário ter experiência em embalagem para analisar o layout fornecido e colocar as mercadorias dentro da caixa. A princípio, algum tempo será gasto para se acostumar, mas não será necessário pensar na melhor disposição.
Ricardo Souza
11
Acho que tudo o que a @msw está dizendo é que esse tipo de problema é improvável para uma solução "perfeita", mas para uma solução aceitável encontrada em um período razoável de tempo com heurísticas baseadas nas regras que você forneceu. Do ponto de vista matemático, isso geralmente significa que você o aborda com um conjunto diferente de algoritmos e ferramentas, então acho que ele está recomendando isso. Por exemplo, algoritmos genéticos, recozimento simulado e outros métodos para seguir uma curva de descida de gradiente aproximando o espaço da solução em relação à sua heurística podem fornecer benefícios aqui.
precisa
11
Estou postando apenas uma ideia aqui. Caso você não ache que será eficaz, pode ignorá-lo. Essa solução (é mais como uma otimização) realmente depende de quão semelhante será a entrada do seu algoritmo. Então, explore o fato de que sua contribuição terá algumas semelhanças ao longo do tempo. Você pode armazenar / armazenar em cache os resultados calculados (que possuem uma complexidade de cálculo dispendiosa) e compará-los com a sua entrada; se você tiver uma correspondência completa ou parcial, precisará fazer apenas alguns cálculos para reordenar alguns objetos de tamanho menor. É claro que isso causa novos problemas.
JAAAY 22/09

Respostas:

4

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.

msw
fonte
Obrigado pelo seu feedback. Como eu disse sobre a questão, eu já pesquisei sobre esse assunto e me deparei com uma mistura de alguns algoritmos para propor esse acima. Estou preocupado apenas com a própria embalagem. Todas essas caixas serão enviadas por meio de serviços de correio. Felizmente, não precisarei lidar com o carregamento de caminhões.
Ricardo Souza
Essa foi uma boa parte da minha explicação. Você não pode "extrair" o algoritmo de empresas que desejam que você pague pelo serviço deles. As duas empresas listadas possuem uma API, mas a compactação é feita em seus servidores e você não tem acesso ao código de implementação, exceto por roubo. E é bom que você não precise empacotar os caminhões, agora seu problema é apenas metade do difícil, e é por isso que as empresas querem vender uma solução e as pessoas estão dispostas a comprar o serviço.
msw
11
Acho que temos uma falta de comunicação aqui. Talvez eu não tenha me expressado bem (como você deve ter notado, o inglês não é minha língua materna). Eu não estou pedindo para roubar os algoritmos. Eu vim aqui para esclarecimentos sobre o assunto. Eu fiz algumas pesquisas e coloquei no exemplo acima para análise. Talvez haja alguém que tenha encontrado os mesmos problemas que possa me dar uma orientação melhor. Se minha solução não for aplicável, o que posso fazer para obter melhores resultados? Esta é a minha verdadeira pergunta lá em cima. Espero ter me deixado mais claro agora.
Ricardo Souza
Seu ingles é bom; Eu acho que o problema é que estamos falando sobre diferentes camadas da tarefa. Você está pensando em implementação e estou pensando em explosão combinatória. Acho que resolver o seu Edit 2 o ajudará a entender melhor o problema da maneira como estou olhando para ele. Você pode resolver isso como indicado? Sem desperdício, com um número mínimo de caixas do tamanho mínimo? Esse é o problema de multi-otimização que mencionei antes, o qual disse ser impossível de executar: você terá que sacrificar pelo menos um desses fatores para otimizar outro.
msw
Obrigado. Eu acho que entendi agora. Não tentei codificá-lo. Eu estava pensando em não perder tempo codificando antes de surgir uma solução mais concreta ou pelo menos um feedback positivo sobre a minha proposta, já que isso é, inicialmente, para uma cotação. Ainda estou pesquisando, mas tenho medo de obter uma dessas APIs e ver se os dispositivos (coletores de dados que executam o Win CE 6.0) podem funcionar conectados à Internet. A primeira informação que recebi do cliente afirmou que eles não terão acesso à Internet no local de trabalho.
Ricardo Souza
1

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.

Canelo Digital
fonte
1

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.

Renaud M.
fonte
Isso parece melhorias interessantes. Não mexo nesse problema há muito tempo. Talvez eu deva tentar um dia desses. Obrigado.
Ricardo Souza