Algorithmus für optimale Verpackung/Paketauslastung

[Heinz Schrot]

Hallo,

ich suche einen Algorithmus zum Berechnen einer optimalen Verpackungsauslastung (Versandpaket).
Limits hierbei sind ein maximales Gurtmaß ( Umfang + längste Länge ) (z.B. max. 300cm) zu beachten ist. Ziel ist das gegebene Gurtmaß durch Stapeln von gleichartigen Quadern (die Quader, welche gestapelt werden sollen haben dieselben Maße) möglichst gut auszunutzen.

Beispiel: 4(Anzahl)* 30cm*100cm*12cm = Produkt. Zu wieviel Prozent ist ein Paket ausgelastet (1%-x00% -> wenn > 100% dann mehr als ein Paket).
Es kann nicht vorkommen, dass Quader mit verschiedenen Maßen verpackt werden.

Danke!
Grüße

 

[engelmarkus]

Hast du dir deine Frage nicht schon selbst beantwortet?

 

[Heinz Schrot]

Naja, im 2d Fall mag das nicht so schwer sein. Aber ich kann ja die Quader auch hintereinander Stapeln, und die X,Y,Z Maße des Kartons sind auch nicht fest, sondern in den gegebenen Limits variabel. Bräuchte daher doch noch weitere Denkanstöße

grüße

 

[Mamphil]

Hallo,

sind die Quadergrößen jetzt bekannt oder auch flexibel in gewissen Maßen zu optimieren?

Das Problem ist ja hauptsächlich, dass die Quader unterschiedliche Ausrichtungen haben können und du deshalb nicht zwingend in Ebenen bauen musst. Einfacher wäre das Problem in meinen Augen, wenn die Größe der Umverpackung bekannt ist und nicht auf das Gurtmaß optimiert werden muss.

Mamphil

 

[Wolfsbein]

http://en.wikipedia.org/wiki/Bin_packing das sollte zum Einstieg helfen. Und deine Restriktion ist schon mal sehr gut.