Algorithmes d'empaquetage tridimensionnel
je suis confronté à un problème d'empaquetage tridimensionnel et je suis en train de mener des recherches préliminaires sur les algorithmes/heuristiques qui donnent actuellement les meilleurs résultats. Puisque le problème est NP dur Je ne m'attends pas à trouver la solution optimale dans chaque cas, mais je me demandais:
1) Quels sont les meilleurs résolveurs exacts? Branch and Bound? Quelles tailles d'instance de problème puis-je espérer résoudre avec des ressources informatiques raisonnables?
2) Quels sont les meilleurs résolveurs heuristiques?
3) Quelles sont les solutions disponibles sur le marché pour effectuer certaines expériences?
6 réponses
en ce qui concerne les solutions standard, cochez MAXLOADPRO pour le chargement des camions. Il peut être configuré pour charger un volume rectangulaire, mais je n'ai pas essayé encore. En général, les problèmes d'empaquetage 3D bin ont la complication supplémentaire que les objets peuvent être tournés dans des positions différentes donc pour tout objet avec une longueur, largeur et hauteur donnée, vous devez effectivement créer trois variables représentant chaque position, mais vous n'utilisez qu'une seule dans le solution.
en général, les MIP autonomes (ou branche et liée) ne fonctionnent pas bien pour le problème 2d ou 3d, mais la programmation contrainte a rencontré un certain succès en produisant des solutions exactes pour le problème 2d. Regardez ce abstract . Sans regarder le papier, j'aime l'approche de décomposition pour le problème où vous essayez de minimiser le nombre de bacs de même taille. Je n'ai pas vu autant de résultats pour le problème 3d, mais laissez-nous sachez si vous en trouvez qui sont réalisables.
bonne chance !
j'ai écrit un programme qui teste trois algorithmes différents. En outre, il s'agit d'une bonne source d'information: mille façons d'emballer la corbeille - une approche pratique à deux dimensions Bin emballage . Il est pour la bin rectangle en deux dimensions, mais vous pouvez toujours le transformer en 3D.
à Partir de wikipedia :
bien que ces stratégies simples soient souvent assez bonnes, des algorithmes d'approximation efficaces ont été démontrés qui peuvent résoudre le problème d'empaquetage de la cellule dans n'importe quel pourcentage fixe de la solution optimale pour des entrées suffisamment grandes
Voici les deux sources qu'ils donnent pour ceci:
meilleur solveur exact: utiliser programmation dynamique .
variables D'État:
- articles que vous avez emballés et éliminés.
- espace rempli dans le conteneur.
si le conteneur est une grille parallélépipédique, et que les éléments "correspondent" aux cellules exactes de la grille, vous pouvez utiliser un tableau tridimensionnel pour représenter la variable d'état 2. Autrement, vous devrez utiliser des structures de données plus complexes.
Meilleure heuristique solveurs
Je ne sais pas. Peut-Être Recherche De Quartier Variable . Il y a quelques similitudes entre votre problème et le problème de construction de l'horaire (sur lequel je travaille), donc le même heuristique pourrait être bon pour les deux.
solutions standard pour mener des expériences
je suis désolé, je n'en ai même pas la moindre idée.
votre question est similaire à: "151910920 3d" bin packing "algorithme 151920920"
bien que, parce que vous n'autorisez pas la rotation, vous pouvez obtenir de très bons résultats. Je suggère de regarder plus vers une solution de premier rang-décroissant.
- "151970920 Unique" bin packing
- multi bin packing
- trouver la troisième dimension
- trouver une bin dimensions