Algorithme d'empilement - Stack objets 3D dans la plus petite zone possible

Question

J'essaie de résoudre le problème de l'empilement des objets dans la taille la plus pratique pour l'affranchissement. La taille et la forme des objets seront variées. La longueur, la largeur et la hauteur de tous les objets sont connues. Par exemple, un client peut commander un objet (longueur x largeur x hauteur) de 200 x 100 x 10 cm (large, long et plat) avec 2 objets (cubes) de 50 x 50 x 50 cm. Si je devais emballer cela, je mettrais l'objet plat large sur le fond et les 2 cubes sur le dessus, côte à côte.

Est-ce que quelqu'un a, ou connaît, une solution algorithmique raisonnablement efficace à cela? Ou même une approche de la façon dont je devrais penser à résoudre cela. J'ai codé toute la semaine, il est tard et mon cerveau est frit. Je ne suis pas encore désespérée mais je veux juste avoir un jour de congé demain. La façon dont je l'envisage serait de créer un tableau représentant un espace 3d, chaque élément du tableau représentant 1 carré/cm dans cet espace. La longueur et la largeur de l'espace 3d seraient basées sur l'objet le plus long et les objets les plus larges. Ensuite, vous travaillez simplement du plus grand objet jusqu'au plus petit objet, en trouvant suffisamment de «trous» et en les remplissant au fur et à mesure.

Bien que je sois certain qu'il y aurait une formule mathématique qui le fait beaucoup plus effiacement.

Des idées?

Answer 1

Ce n'est pas un problème facile et je suppose que c'est même NP-difficile. Vous semblez avoir quelques bonnes idées cependant! Je recommande de lire sur le Knapsack problem pour obtenir plus de théorie et de nouvelles idées.

Answer 2

Je ne pense pas que ce soit trivial. Je crois que le nom propre pour cela est bin packing, et les recherches Google révèlent beaucoup d'articles académiques, mais pas d'algorithmes simples (surtout en 3-D, qui est ce que vous voulez).

Combien d'objets voulez-vous manipuler en pratique? Si c'est relativement peu (pas des centaines dans un conteneur d'expédition TEU, mais peut-être quelques-uns dans une boîte en carton pour Fedexing), alors une approche simple force brute pour une solution de maxima locale peut être la meilleure approche.

Answer 3

Premier conseil - éloignez-vous du clavier, arrêtez le codage, commencez à penser! Deuxième conseil - l'approche que vous proposez (la plus grande en premier, puis la plus grande en second) est une heuristique très respectée et très utilisée pour ce problème. Et, à moins d'avoir un grand nombre de choses à emballer, ou un grand nombre de paquets à faire, ne soyez pas trop préoccupé par l'efficacité de l'exécution, l'efficacité du développement devrait probablement être votre première priorité. Troisième conseil - Google pour bin-emballage mais soyez averti, il y a une énorme quantité de littérature à ce sujet.

Enfin, ne soyez pas si certain qu'il ya une formule mathématique pour cette :-)

Answer 4

Je ne suis pas un expert, mais je pense qu'il est pas possible de trouver le résultat optimal sans utiliser la force brute approche, mais je peux suggérer quelques choses cependant:

1) Si vous commencez à emballer l'objet avec le plus grand volume sur le premier récipient et le deuxième plus grand objet sur le deuxième récipient, le troisième plus grand sur le premier récipient à l'infini, le le résultat sera au plus 14% (ou est-ce 34%? Je ne me souviens pas exactement!) pire que le résultat optimal. J'ai lu ceci quelque part sur le livre "L'homme qui aimait seulement les nombres" par Paul Hoffman.

2) Un algorithme génétique devrait vous fournir des résultats relativement meilleurs au détriment de certaines performances. Il ya aussi quelques entreprises comme Logen Solutions et MaxLoad qui font cela pour vivre, donc si vous êtes prêt à payer, vous pouvez également utiliser leurs services Web.