2D Behälterverpackungsproblem
Dieser Online-Rechner löst ein offline 2-Dimensionales (2D) Behälterverpackungsproblem , unter Verwendung des Heuristischer Algorithmus für maximale Rechtecke.
这个页面的存在是由于以下各位的努力:
 | Timur
|
Stefan Roesner
|
Dieser Online-Rechner sollte helfen, die Frage „Wie viele Platten sind benötigt, wenn man eine Reihe von kleineren Rechtecken mit verschieden Längen und Breiten (LxB) in größere Rechtecke mit fixen Längen und Breiten (LxB) Dimensionen.“ Beantworten möchte.
Zum Beispiel muss ein Arbeitsplattenhersteller berechnen, wie viele Platten einer bestimmten Größe für deinen Auftrag benötigt werden. Hierfür sollte die Menge des benötigten Materials in eine Reih von kleineren Rechtecken unterteilt werden (siehe diese Anfrage).
Untern sollte man die Dimension der Hauptplatte im Format Länge x Breite eingeben, gefolgt von den Dimensionen der rechteckigen Teile und deren Mengen im Format Länge x Breite x Menge , ein Rechteck nach dem anderen.
Tatsächlich ist dies ein Zwei-Dimensionales Verpackungsproblem für Rechteckbehälter. Der Rechner wird das beste Layout finden, aber es ist garantiert, dass dies die beste Lösung ist. Für wissenschaftliche Details sollte man sich den Theorieteil unter dem Rechner anschauen.
2D Behälterverpackungsproblem
Behälter-Dimensionen
Rechtecke zum Packen
Zwei-Dimensionales Behälterpacken von Rechtecken
Hier handelt es sich also um ein Problem für ein Zwei-Dimensionales Behälterpacken von Rechtecken. Für jegliche Probleme mit Behälterverpackung hat man eine gegebene Anzahl von Containern (in diesem Fall ist der Container ein 2D rechteckiger Bereich). Ein Satz von Objekten (in diesem Fall sind es kleine Rechtecke) sollen in einen oder mehreren Containern gepackt werden. Das Ziel ist es, alle Objekte in so wenige Container wie möglich zu packen.
Falls der Satz Objekte, der verpackt werden soll, vorher bekannt ist, wird das Problem als Offline bezeichnet. Im Gegensatz dazu erscheint im Online-Problem ein Objekt nach dem anderen. Hier handelt es sich um ein Offline-Problem für ein 2D Dimensionales Behälterpacken von Rechtecken.
Dies ist eins der klassischen Probleme der kombinatorischen Optimierung und ist als NP-hart erwiesen. Dies bedeutet, dass man die optimale Lösung nur durch approximieren mit dem heuristischen Algorithmus ermitteln kann.
Diese bestimmte Ausführung des 2D Behälterverpackungsproblem Lösers beruht auf den maximalen Rechteckalgorithmus. Diese Heuristik ist eine Erweiterung von der Guillotine Split Heuristik und zeigt hervorragende Ergebnisse für das Offline-Packen.
Die Idee der maximalen Rechteckheuristik ist es, den genauen maximalen freien Rechtsbereich zu verfolgen, der noch verfügbar ist, nachdem ein Objekt in den Container platziert wurde (siehe das untere Bild).
Es gibt auch verschieden Regeln, welche Rechtecke in welchen Container platziert werden sollen. Hier wird der globale Ansatz verwendet. Dies bedeutet, dass man für jeden Schritt eine Punktzahl für jeden übriges Rechteck und jede übrige Fläche berechnet wird – und man wählt die Kombination mit der besten Punktzahl. Bezüglich der bestimmten Platzierungsregel prüft diese Ausführung vier von ihnen, und wählt dann die Regel aus, die das beste Ergebnis erzielt (z.B. verwendet die minimale Anzahl von Containern).
Die Platzierungsregeln sind:
- Unten-Links – die y-Koordinate von der oberen Seite des Rechtecks sollte die Kleinste sein. Sollte es mehrere gleichgroße geben, soll die mit dem kleinen x-Koordinatenwert genommen werden.
- Beste kurzseitige Passform- die freie Fläche sollte die Mindestlänge von der kürzeren Restseite haben.
3 Beste langseitige Passform- die freie Fläche sollte die Mindestlänge von der längeren Restseite haben. - Beste Flächenpassform- die freie Fläche sollte die kleinste Fläche sein, um das nächste Rechteck zu platzieren. Sollte es gleichgroße geben, folgt man der besten kurzseitige Passform.
评论