Algorithme d'emballage 3D pour l'expédition de l'article

J'ai reçu la tâche de construire une estimation d'expédition qui suggère le meilleur hébergement de marchandises sur le moins de boîtes possible:

1. Il existe un ensemble fini de tailles de boîtes rétangulaires connues

2. Il existe de nombreux éléments arbitraires retangulaires à emballer dans des boîtes

3. Le moins de boîtes doit être utilisé le mieux. Parce que l'expédition de deux boîtes 1x1x1 est beaucoup plus chère qu'une boîte 1x2x1. Cela devrait être la priorité ici.

4. Il devrait également être optimisé pour utiliser les boîtes plus petites que possible, comme priorité de deuxième niveau. (par exemple: si vous avez le choix entre une plus grande boîte et deux petites, il devrait choisir la plus grande boîte)

5. Les articles peuvent être tournés pour s'adapter à la boîte, mais la rotation doit être limitée à des incréments de 45 ° au minimum (dans mes recherches, il semble que certaines configurations permettent une rotation de 45 degrés pour mieux s'adapter aux boîtes rétangulaires à l'intérieur d'une boîte rétangulaire plus grande) , la rotation à 90 ° étant la norme à prendre.

6. Les boîtes ont une limite de poids et les articles ont des poids arbitraires (par exemple: un article dont la taille est 1x1x1 peut être plus lourd que les autres articles 2x2x2)

J'ai fait des recherches un peu et j'ai trouvé des algorithmes abstraits sur l'emballage des bacs et le problème du sac à dos et je suis venu avec la variation quelque peu bruteforce suivante, similaire à l'algorithme le mieux adapté:

1. Trier les articles en ordre de volume décroissant (le plus grand en premier) sur une liste "articles à emballer"

2. Pour chaque article de cette liste:

   1. Choisissez la petite boîte qui se trouve sur la liste des "boîtes utilisées" et qui a suffisamment de volume et de poids pour s'adapter à l'article (j'utiliserai l'ajustement ici pour signifier l'ajustement des dimensions et du poids)

   2. S'il n'y a pas une telle boîte, créez une nouvelle boîte à partir de l'ensemble connu des tailles de boîte possibles qui est la plus petite taille pouvant s'adapter aux dimensions et au poids de l'article et ajoutez-la à la liste des "boîtes utilisées".

   3. Si une boîte correspond à l'article (en utilisant la fonction d'ajustement ci-dessous), ajoutez-la à la liste des "articles de cette boîte" et supprimez-la de la liste des "articles à ajuster", en marquant sa position 3D relative à l'intérieur de la boîte.

   4. Répétez à partir de 2.1 jusqu'à ce qu'il n'y ait aucun article à installer sur la liste des «articles à emballer».

La fonction de vérification du raccord utilisée à l'étape 2 ci-dessus:

1. Vérifiez si le volume restant de la boîte correspond au volume de l'article. Sinon, retournez false.

2. Vérifiez si la somme du poids des «articles de la boîte» plus le poids actuel de l'article est inférieure ou égale à la limite de poids de la boîte. Sinon, retournez false.

3. Vérifiez la liste des "éléments de la boîte" pour choisir la première coordonnée de boîte qui a le plus petit composant Y et qui a suffisamment d'espace pour la largeur, la profondeur et la hauteur de l'élément, en considérant les autres éléments placés comme espace indisponible.

4. Si l'élément ne tient pas à son orientation actuelle, faites-le pivoter sur l'une des 6 rotations possibles, sans supposer une rotation de 45 ° pour plus de simplicité. (Les rotations qui aboutissent à des tailles qui, lorsqu'elles étaient déjà testées, peuvent être ignorées. Par exemple: la rotation d'une boîte à 180 ° donne les mêmes dimensions que la position d'origine, car toutes les boîtes et tous les articles ont la même taille pour les faces opposées et peuvent donc être ignorés.)

5. Si l'élément n'a pas été pivoté de toutes les manières possibles pour revenir à son orientation d'origine, réessayez à partir de l'étape 3.

6. Si toutes les rotations ont été essayées et qu'aucun ajustement n'a été trouvé, considérez la coordonnée actuelle comme l'espace indisponible.

7. S'il n'y a pas d'espace disponible pour vérifier, retournez false. Sinon, réessayez à partir de l'étape 3.

Je veux savoir s'il peut y avoir une meilleure solution à mon problème, compte tenu des contraintes présentées.

Cela semble fonctionner sur la théorie mais je ne l'ai pas essayé sur le code. Je souhaite savoir si je vais dans la bonne direction ou s'il existe de meilleures façons de le faire.

Les références seraient formidables.

Modifier:

J'ai trouvé des API tierces intéressantes qui font ce que je veux, mais cela devra être déconnecté, donc je n'aurai pas accès à celles-ci.

Certains exemples sont:

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

Modifier 2:

Un exemple réel de problème à résoudre serait:

• J'ai 4 tailles de boîte LxHxP: 10x12x18, 12x16x24, 16x20x30, 24x32x40
• J'ai une commande de 4 articles, dont 1 de taille 6x8x10, 2x 22x14x30 et 1x 22x4x20

Comment puis-je placer ces articles dans n'importe quelle quantité de boîtes d'une ou plusieurs tailles en utilisant le moins de boîtes possible, en utilisant les plus petites boîtes possibles et en laissant moins d'espace libre que possible?

L'emballage des bacs est très difficile à calculer. Pensez à la moitié du problème: vous voulez emballer le produit dans des boîtes d'expédition sans gaspillage dans la boîte. Une solution optimale pour cela nécessiterait de passer par tous les sous-ensembles possibles et tous les arrangements 3D possibles du produit qui doit être expédié dans un seul camion. Je vais vous donner la solution optimale pour cela car j'ai un ami qui fait six choses impossibles avant le petit déjeuner.

Il ne vous reste plus qu'à récupérer toutes les boîtes sur le camion sans gaspillage. Mon ami fait sa deuxième chose impossible et vous donne la solution. Malheureusement, avec les tailles de boîtes que vous avez sélectionnées ci-dessus, il y a un espace vide dans le camion qui pourrait être réduit si vous aviez choisi différentes boîtes (plus grandes ou plus petites) dans la première tâche. Si vous changez la taille d'une boîte, vous devrez au mieux remballer le camion; au pire, vous devrez peut-être reconditionner toutes les boîtes, ce qui est tout aussi difficile que le problème avec lequel nous avons commencé. Et, comme pour la première étape, vous devrez essayer tous les arrangements 3D possibles.

J'ai trouvé que le manuel de conception d'algorithmes de Skiena était utile pour réfléchir à la classe d'algorithmes qui convient à quels types de problèmes, mais j'ai surtout appris que de bonnes solutions pour des problèmes même banals explosent devant vous avec des difficultés de calcul. La plupart de ce dont vous avez besoin s'inscrit dans la classe des problèmes d'emballage de bacs et cet article est un bon point de départ. Il convient de noter que certains des meilleurs algorithmes pour cela sont des produits commerciaux, car cette tâche apparaît partout dans la logistique (quel est le plus petit nombre de voitures de train dans lesquelles puis-je faire entrer mes marchandises? Et autres). Il y a beaucoup d'argent à faire si la bonne heuristique peut faire économiser à un constructeur 100 voitures de train par mois.

Malheureusement, la littérature sur l'optimisation de l'heuristique n'est pas aussi grande que pour les algorithmes. Si vous essayez de faire cavalier seul, je vous garantis que vous rêverez de déplacer des prismes rectangulaires d'ici votre deuxième mois. J'ai eu un problème de stock que si je devais refaire, je ferais probablement appel aux experts (ou à leur logiciel propriétaire).

Merci à @JTrana pour la belle expansion de mon commentaire.

Lors de la création de nouveaux algorithmes, et je viens de faire un algorithme d'empaquetage par moi-même (je sais qu'il a encore un certain potentiel d'optimisation), je fais toujours l'approche la plus simple:

Comment le ferais-je en tant qu'humain et essayer de le traduire en un algorithme: De mon professeur d'IA (robotique) Rolf Pfeifer, je garde toujours à l'esprit que l'intelligence apparente peut parfois être créée avec des règles très simples, donc au lieu de suringénierie J'essaye de sous-ingénier

1. Identifiez les articles trop gros (articles qui ne rentrent pas dans une boîte donnée)
2. Essayez de trouver la meilleure boîte possible (en comparant le volume total et les dimensions de l'article)
3. Commandez les articles du grand au petit et les boîtes (espaces) du petit au grand
4. Placez le plus gros article dans le plus petit espace possible
5. Si le plus gros article ne le trouve pas, sautez dessus et essayez le suivant jusqu'à ce qu'il n'y ait plus rien

6. Pour les éléments restants, recherchez la nouvelle meilleure case. ...

   X. pensez toujours aux événements exceptionnels (articles surdimensionnés, formulaires étranges, si une boîte ne contient qu'un seul article, ne serait-il pas préférable d'envoyer un article sans boîte?, Etc.) mais vous pouvez également faire une heuristique sous la forme d'une décision arbre.

Bien sûr, il y a d'autres mises en garde au fur et à mesure que vous obtenez, je donne juste ces idées comme point de départ. De là, il existe de nombreuses façons possibles. Une alternative serait de diviser une boîte en petits cubes (par exemple 5cmx5cmx5cm) et de les suivre comme occupés / libres, une autre approche pourrait être appelée 3d tetris, etc.

Avec cette approche, vous n'avez pas nécessairement à vous soucier de l'explosion combinatoire. D'un autre côté, une explosion combinatoire pourrait se produire si nous parlons de trains d'articles, mais là encore: pensez-vous vraiment qu'une entreprise vérifiera la liste de colisage article par article? Non, ils n'aborderont pas une solution de division et de conquête: divisez la complexité en utilisant des volumes standardisés (par exemple, des palettes ou des boîtes de taille fixe). Donc, même pour des raisons pratiques, tenez compte du fait que non seulement les trains, parfois le temps des employés, c'est aussi de l'argent. un train peut charger x palettes, chaque palette a un volume fixe, alors mettez les articles dans la palette, mais là encore, peut-être qu'un palet se compose de plusieurs ordres, alors utilisez des boîtes fixes pour les articles, qui sont ensuite chargés dans des palettes, qui sont ensuite chargés dans les trains.

Au moins, c'est ainsi que moi, en tant qu'humain, je gérerais la tâche, j'obtiendrais la meilleure boîte, puis je placerais le plus grand élément un par un dans le plus petit espace disponible (et ajouter un peu d'aperçu).

Comme dans mon algorithme, au final, vous n'aurez probablement pas la meilleure solution, mais une bonne heuristique que vous pourrez ensuite affiner.

Parfois, il est plus facile de commencer par la première étape et d'éliminer les problèmes sur votre chemin, bien sûr, idéalement pas une sorte d'étape par-dessus bord, mais un peu intelligent ... parfois vous pouvez être forcé, d'explorer des alternatives et de choisir le meilleur ou mettre en œuvre un «recul».

Mais comme je l'ai appris de mon professeur d'IA (Rolf Pfeifer, désolé de m'embêter à nouveau avec ça): Parfois, vous pouvez créer un comportement intelligent apparent avec des règles très simples et peu nombreuses> un comportement émergent dans l'exemple mentionné, ils ont programmé de petites voitures à distance pour tourner à gauche si ils détectent un obstacle sur le côté droit, tournent à droite s'il y a un obstacle sur le côté gauche et vont tout droit s'il n'y a pas d'obstacle ou si l'obstacle est devant. 3 ou 4 robots comme ça, placés dans un carré de 3m x 3m avec beaucoup de balles de ping-pong conduisent au fait étonnant que les robots semblaient se nettoyer, poussant les balles de ping-pong dans les coins, même si les robots sont uniquement programmé pour éviter les obstacles.

PD: La seule déviation du monde réel que j'ai trouvée de cette approche est quand je travaillais à temps partiel comme machiniste pour de grands concerts comme metallica, iron maiden, britney spears, paul mcCartney, U nommez-le ... Les camionneurs travaillant sur le les tournées internationales ont des listes de colisage précises article par article. Les calculs sont effectués une fois (je ne sais pas par les humains ou les machines), puis répliqués. Parfois, lorsqu'ils emballent pour la première fois, ils font même des images couche par couche et les collent dans le camion juste pour que les équipes locales sachent exactement quelle boîte doit être chargée quand et où. Mais c'est aussi un besoin d'emballage spécifique car pour une tournée, ils travaillent toujours avec les mêmes boîtes et camions.

L'heuristique que vous mentionnez dans votre article semble intéressante.

Je suggérerais quelques modifications afin d'améliorer la solution finale.

Étant donné une solution avec tous les articles emballés dans une boîte, essayez de fusionner le contenu de deux petites boîtes dans une boîte plus grande (cela devrait aider à améliorer vos critères d'utilisation du moins de boîtes possible).

Alternativement, chaque fois que vous démarrez une nouvelle boîte, au lieu d'utiliser la plus petite boîte qui peut contenir l'élément actuel, vous pouvez choisir la plus grande boîte qui peut le contenir, et une fois que chaque élément est affecté à une boîte, essayez d'affecter tous les éléments d'un boîte à une boîte plus petite.

De plus, dans votre fonction d'ajustement, au lieu de considérer la position de vos autres boîtes comme fixe, vous pourriez imaginer changer la séquence de chargement. Cela devrait vous permettre de trouver de meilleures solutions au détriment d'une durée de fonctionnement plus longue.