Solveur de problème de conditionnement de boîtes 2D
Ce calculateur en ligne essaye de résoudre les problème de conditionnement d'une boîte en deux dimensions (2D) en utilisant l'algorithme heuristique des rectangles maximaux
Cette page existe grâce aux efforts des personnes suivantes :
 | Timur
|
Gaulthier Marrel
|
Ce calculateur en ligne devrait vous aider à répondre aux questions telles que, de combien de dalles avez-vous besoin si vous conditionnez des séries de rectangles plus petits de longueurs et largeurs (Lxl) diverses dans des rectangles plus grands avec des longueurs et largeurs (Lxl) fixées.
Par exemple, si vous êtes fabricants de comptoirs de cuisine et si vous avez besoin de savoir de combien de dalles d'une certaine taille vous avez besoin afin de faire le travail. Ainsi, la quantité de matériel nécessaire peut être divisée en séries de rectangles plus petits.
Ci-dessous, vous devez entrer les dimensions de la dalle principale dans le format Longueur x Largeur, puis les dimensions des pièces rectangulaires ainsi que leur quantité dans le format Longueur x Largeur x Quantité, un type de rectangle par ligne.
En fait, c'est un problème de conditionnement de boîtes rectangulaires en deux dimensions. Le calculateur essayera de trouver la meilleure disposition qu'il peut, mais malheureusement il ne garantit pas la solution optimale. Pour les détails scientifiques, référez-vous à la théorie en-dessous du calculateur.
Solveur de problème de conditionnement d'une boîte 2D
Dimensions de la boîte
Rectangles à conditionner
Conditionnement de boîtes rectangulaires en deux dimensions
Bien, donc ici nous faisons face à un problème de conditionnement de boîtes rectangulaires en deux dimensions. Dans chaque problème de conditionnement de boîtes, vous avez un genre de conteneur (dans notre cas le conteneur est une zone rectangulaire 2D) et un ensemble d'objets (une fois de plus, dans notre cas des rectangles plus petits) qui doivent être conditionnés dans un conteneur ou plus. Généralement, le but est de conditionner tous les objets en utilisant le moins de conteneurs possible.
Si l'ensemble d'objets à conditionner est connu à l'avance, le problème est appelé "hors-ligne" contrairement à un problème "en ligne" où les objets apparaissent les uns après les autres. Donc ici, nous faisons face à un problème de conditionnement de boîtes rectangulaires 2D "hors-ligne".
C'est l'un des problèmes classiques en optimisation combinatoire et il a été prouvé qu'il est NP-difficile. Ainsi, nous pouvons uniquement approximer la solution optimale avec des algorithmes heuristiques.
Cette implantation particulière d'un solveur de problème de conditionnement de boîtes 2D repose sur les Algorithmes des rectangles maximaux. Cet heuristique est une extension de la division heuristique par guillotine et donne d'excellents résultats pour le conditionnement "hors-ligne"1
L'éidée de l'heuristique des rectangles maximaux est de garder une trace de tous les espaces rectangulaires maximaux libres qui sont toujours disponibles après avoir placé un objet dans le conteneur (voir image ci-dessous)
Il y a différentes règles pour choisir quel rectangle placé dans quelle boîte. Ici, nous utilisons l'approche globale ce qui signifie qu'à chaque étape, nous calculons le 'score' pour chaque rectangle restant et pour chaque espace libre restant et nous choisissons la combinaison qui nous donne le meilleur score. Concernant les règles de placement, cette implantation en utilise quatre, puis choisit ensuite la règle qui produit le meilleur résultat (soit l'utilisation du plus petit nombre de boîtes).
Les règles de placement sont :
- Coin inférieur gauche - la coordonnées y du côté supérieur du rectangle doit être la plus petite. En cas d'égalité, celle avec la valeur de coordonnée x la plus petite est utilisée.
- Meilleur ajustement latéral court - la surface de l'espace libre doit avoir la longueur minimale du côté restant le plus court.
- Meilleur ajustement latéral long - la surface de l'espace libre doit avoir la longueur minimale du côté restant le plus long
- Meilleur ajustement de surface - la surface de l'espace libre doit être la plus petite des surfaces dans lesquelles placées le rectangle suivant. En cas d'égalité, la règle du Meilleur ajustement latéral court est utilisée.
-
Un millier de façon de conditionner des boîtes - Une approche pratique au conditionnement de boites rectangulaires en deux dimensions par Jukka Jylänki ↩
commentaires