Quelqu'un connaît-il un logiciel ou un algorithme permettant de calculer la taille d'un colis pour l'expédition de plusieurs articles ?
J'ai un certain nombre d'articles dans notre base de données d'inventaire avec des dimensions de longueur, de largeur et de hauteur définies. Compte tenu de ces dimensions, je dois calculer le nombre d'articles achetés qui entreront dans des boîtes de taille prédéfinie.
Il s'agit d'un Emballage des bacs et il est NP-hard. Pour un petit nombre d'objets et de paquets, il est possible d'utiliser la méthode de la force brute en essayant toutes les possibilités. Au-delà, vous devrez utiliser une sorte d'heuristique. L'article de Wikipedia contient quelques détails, ainsi que des références à des articles que vous voudrez probablement consulter.
L'autre solution, bien sûr, est de commencer par un algorithme très simple (comme simplement "empiler" des articles) et de calculer une limite supérieure raisonnable pour l'expédition à l'aide de cet algorithme, puis si vos emballeurs humains peuvent faire mieux, vous réalisez un léger bénéfice. Ou bien de réduire légèrement les prix calculés en partant du principe que l'emballage n'est pas idéal.
La littérature sur le "3D Bin packing" est abondante. Vous pouvez obtenir une bonne vue d'ensemble en suivant les publications de Professeur David Pisinger . Il a également publié l'une des rares implémentations de haute qualité du bin packing avec le code source : 3dbpp.c
Ma propre boîte à outils logistique pyShipping est accompagné d'une implémentation de l'emballage en 3D pour les applications d'entreposage. Il s'agit en fait d'une implémentation 4D Bin Packing (taille et poids en 3D) qui permet d'obtenir une solution acceptable pour des commandes typiques (quelques dizaines de colis) en moins d'une seconde d'exécution. Il est utilisé en production (c'est-à-dire dans un entrepôt) depuis quelques mois pour déterminer la limite supérieure des caisses d'expédition à utiliser. Les magasiniers sont souvent capables d'emballer un peu plus efficacement, mais cela ne me dérange pas.
Bonjour @Qwertie, je pense avoir trouvé le code source ici : hjemmesider.diku.dk/~pisinger/3dbpp.c
Essayez-vous de déterminer combien d'exemplaires d'un type donné peuvent entrer dans un emballage d'une taille particulière, ou essayez-vous de mélanger les types ?
On dirait que vous essayez de résoudre le problème de la Problème de Knapsack . Vous pourriez trouver des algorithmes qui pourraient être adaptés à vos besoins spécifiques. Comprenez simplement qu'il sera difficile de trouver un efficace car le problème est NP complet (bien que, selon vos besoins spécifiques, vous puissiez trouver une approximation efficace, ou que vos données d'entrée soient suffisamment petites pour que cela n'ait pas d'importance).
Votre description et le lien référencé sont également exacts. Comme dans le cas du problème de l'emballage des bacs mentionné par Arachnid, il peut y avoir un nombre extrême de solutions possibles, aggravées par la possibilité de tourner les articles sur le côté dans la boîte.
Peut-être que ce truc que j'ai hacké ces dernières heures peut aider : http://github.com/yetzt/boxing
Les métaheuristiques sont utiles pour traiter les problèmes d'emballage de bacs dans le monde réel lorsqu'il y a de nombreux paquets et/ou de nombreuses contraintes. Une implémentation Java open source est Planificateur Drools .
Prograide est une communauté de développeurs qui cherche à élargir la connaissance de la programmation au-delà de l'anglais.
Pour cela nous avons les plus grands doutes résolus en français et vous pouvez aussi poser vos propres questions ou résoudre celles des autres.
0 votes
Question intéressante. J'ai d'abord pensé à calculer la surface de chaque objet par rapport à la surface disponible dans la boîte, mais cela ne fonctionne pas vraiment lorsque les objets ne sont pas, par exemple, des cubes parfaits... Il peut rester de la place dans la boîte sans qu'elle soit utilisable l'espace. Hrm...
0 votes
Merci à Rich B pour avoir amélioré le titre de cette question. En particulier, il a ajouté le mot "programmatiquement" à la manière d'un récent podcast de SO.