Abstappelfunktion von Paketen auf eine Palette

[Domlla]

Hallo,
wir haben die Aufgabe aus vorgegebenen Paketgrößen ein Programm zu schreiben, dass diese optimal auf einer Palette absetzt.
Nun habe ich das Programm soweit, dass es mir die Breite und die Länge des Karton von der Palette abzieht und mir den Punkt ausgibt an dem die linke untere Ecke abgesetzt werden soll.
Die Höhe klappt auch schon. Nun soll z.B. noch aus dem Wert 600300250 wobei die 600 für die Breite steht, die 300 für die Länge und die 250 für die Höhe, geschaut werden ob das Paket vielleicht besser nicht gedreht werden soll und ob neben ein Paket mit der Höhe 500 nicht zwei passen mit der Höhe von 250.
Wie kann ich das am Besten realisieren? Das ganze soll später auch noch auf einer Grafikoberfläche ausgegeben werden. Gibt es hierfür Tipps?
Die Werte stehen so in einer Liste 600300250, 600300250, ... kann man die Werte von 600 und 300 einfach Tauschen?
Vielen Dank!

[rogerb]

@Domlla,

das ist eine ziemlich ungünstige Art solche Daten zu speichern. Das sind ja drei Werte in einem Wert vereint. Damit machst du dir das Leben nur unnötig schwer.

Wie wäre es mit einer Klasse "Paket" die die Attribute Länge, Breite, Höhe enthält. Dann kann man auch Methoden wie drehe() anbieten.
Die Methode drehe() würde dann je nachdem um welche Achse gedreht werden soll, die Werte für Länge, Breite Höhe tauschen.

[rogerb]

@Domilla,
vielleicht so etwas:

Code: Alles auswählen

class Box():
    def __init__(self, width, depth, height):
        self.width = width      # x
        self.depth = depth      # y
        self.height = height    # z

    def rotate_x(self):
        self.depth, self.height = self.height, self.depth

    def rotate_y(self):
        self.width, self.height = self.height, self.width

    def rotate_z(self):
        self.depth, self.width = self.width, self.depth

    def __repr__(self):
        return f"<Box width: {self.width}, depth: {self.depth}, height: {self.height}>"


box = Box(10, 20, 30)
print(box)
box.rotate_x()
print(box)
box.rotate_y()
print(box)
box.rotate_z()
print(box)

"""
Ausgabe:

<Box width: 10, depth: 20, height: 30>
<Box width: 10, depth: 30, height: 20>
<Box width: 20, depth: 30, height: 10>
<Box width: 30, depth: 20, height: 10>
"""

Zusätzlich müsste man wahrscheinlich noch die x, y, z Position im Raum als Attribut anlegen.

[frogi001]

Hallo,
ist das Problem mathematischer, oder programmiertechnischer Natur?
Also, wie das Problem mathematisch zu lösen ist steht fest, nur wie man es
in ein Programm umsetzt ist unklar, oder die Umsetzung in ein Programm ist möglich, aber
die mathematischen Berechnungen sind das Problem? ... oder beides?

gedreht werden soll und ob neben ein Paket mit der Höhe 500 nicht zwei passen mit der Höhe von 250

... hört sich nach dreidimensional an?

Das ganze soll später auch noch auf einer Grafikoberfläche ausgegeben werden. Gibt es hierfür Tipps?

Reicht es, wenn das Ergebnis z.B. als Bild dargestellt wird, oder soll das ganze Programm in einer GUI
laufen?
Wenn zweidimensionales Bild: Python Pillow

[rogerb]

@frogi001,

Also, wie das Problem mathematisch zu lösen ist steht fest

Oh, kannst du mich mal aufschlauen wie das geht?

[Domlla]

Code: Alles auswählen

palettenlaenge = 0
palettenbreite = 0
palettenhoehe = 0
palettengrenzlaenge = 1200 #x
palettengrenzbreite = 800 #y
palettengrenzhoehe = 1500  # z


auftrag = [600300200, 600300200, 600300200, 600300200, 600300200, 600300200, 600300200, 600300200, 600300200, 600300200, 600300200, 600300200, 600300200, 600300200, 600300200, 600300200, 600300200, 600300200, 600300200, 600300200, 600300200, 600300200, 600300200, 600300200, 600300200, 600300200, 600300200, 600300200, 600300200] #500250200, 500250200, 500250200, 500250200, 500250200]
i=1
absetzpunktx = 0
absetzpunkty = 0
absetzpunktz = 0
lage= 1

for paket in auftrag:
    
    #übergibt werte aus Auftragsliste
    paketlaenge = str(paket)[0:3] #x
    paketbreite = str(paket)[3:6] #y
    pakethoehe = str(paket)[6:9] #z
    
    # zieht bei Palettenanfang Paketgröße von Palettenmaß ab
    if absetzpunktx == 0 and absetzpunkty == 0: 
        palettengrenzlaenge = palettengrenzlaenge - int(paketlaenge) #x
        palettengrenzhoehe = palettengrenzhoehe - int(pakethoehe) #z
        
    # zieht in Y-Achse Paketmaß von Palettenmaß ab und gibt Werte aus     
    palettengrenzbreite = palettengrenzbreite - int(paketbreite) #y
    print ("Paket ", i, "Paketlänge: ", paketlaenge, "mm", "Paketbreite: ", paketbreite, "mm", "Pakethöhe: ", pakethoehe, "mm")
    print ("Paket ", i,  "wird an Punkt", absetzpunktx, ",", absetzpunkty, ",", absetzpunktz, "abgesetzt", ",", "Lage:", lage)
    print ("Restlänge Palette: ", palettengrenzlaenge, "Restbreite Palette: ", palettengrenzbreite, "Resthöhe Palette: ", palettengrenzhoehe, "\n")
    
    #legt restlich verfügbares Palettenmaß nach einer Lage fest
    if palettengrenzlaenge < int(paketlaenge) and (palettengrenzbreite < int(paketbreite) or palettengrenzbreite == 800):
        print("Lage ist voll!", "Lage:", lage)
        palettengrenzlaenge = 1200 - palettengrenzlaenge
        
        
        if lage == 1 and palettengrenzhoehe >= int(pakethoehe):
            lage = lage + 1
            palettengrenzbreiteneu = 800 - palettengrenzbreite
            palettengrenzbreite = palettengrenzbreiteneu
            palettengrenzhoeheneu = 1500 - int(pakethoehe)
            palettengrenzhoehe = palettengrenzhoeheneu
            absetzpunktx = 0
            absetzpunkty = 0
            absetzpunktz = absetzpunktz + int(pakethoehe)
            print ("Verfügbare Palettenlänge:", palettengrenzlaenge, "Verfügbare Palettenbreite:", palettengrenzbreiteneu, "Verfügbare Palettenhöhe:", palettengrenzhoehe,"\n""Neue Lage beginnt bei: ", absetzpunktx, ",", absetzpunkty, ",", absetzpunktz, "\n")
        else :
            lage = lage + 1
            palettengrenzbreiteneu = palettengrenzbreiteneu - palettengrenzbreite
            palettengrenzbreite = palettengrenzbreiteneu
            absetzpunktx = 0
            absetzpunkty = 0
            absetzpunktz = absetzpunktz + int(pakethoehe)
            if palettengrenzhoehe <= int(pakethoehe) and palettengrenzhoehe >0 and absetzpunktx == 0 and absetzpunkty  == 0:
               print ("Palette voll!")
               break
            print ("Verfügbare Palettenlänge:", palettengrenzlaenge, "Verfügbare Palettenbreite:", palettengrenzbreiteneu, "Verfügbare Palettenhöhe:", palettengrenzhoehe,"\n""Neue Lage beginnt bei: ", absetzpunktx, ",", absetzpunkty, ",", absetzpunktz,"\n")
            
    # zieht Paketmaß von Palettenmaß in Y-Richtung ab und erhöht den Absetzpunkt um Paketmaß
    elif palettengrenzbreite >= int(paketbreite):
        absetzpunkty = absetzpunkty + int(paketbreite)
    
    # Setzt Nullpunkt in Y-Richtung und erhöht den Absetzpunkt in x-Richtung um Paketmaß  
    elif palettengrenzbreite <= int(paketbreite) and lage == 1:
        palettengrenzbreite = 800 #option suchen
        absetzpunkty = 0
        absetzpunktx = absetzpunktx + int(paketlaenge)
        palettengrenzlaenge = palettengrenzlaenge - int(paketlaenge)
        
    # Setzt Nullpunkt in Y-Richtung und erhöht den Absetzpunkt in x-Richtung um Paketmaß
    elif palettengrenzbreite <= int(paketbreite):
        palettengrenzbreite = palettengrenzbreiteneu #option suchen
        absetzpunkty = 0
        absetzpunktx = absetzpunktx + int(paketlaenge)
        palettengrenzlaenge = palettengrenzlaenge - int(paketlaenge) 
        print(palettengrenzlaenge)
   
    i=i+1

[Domlla]

@Domilla,
vielleicht so etwas:

Code: Alles auswählen

class Box():
    def __init__(self, width, depth, height):
        self.width = width      # x
        self.depth = depth      # y
        self.height = height    # z

    def rotate_x(self):
        self.depth, self.height = self.height, self.depth

    def rotate_y(self):
        self.width, self.height = self.height, self.width

    def rotate_z(self):
        self.depth, self.width = self.width, self.depth

    def __repr__(self):
        return f"<Box width: {self.width}, depth: {self.depth}, height: {self.height}>"


box = Box(10, 20, 30)
print(box)
box.rotate_x()
print(box)
box.rotate_y()
print(box)
box.rotate_z()
print(box)

"""
Ausgabe:

<Box width: 10, depth: 20, height: 30>
<Box width: 10, depth: 30, height: 20>
<Box width: 20, depth: 30, height: 10>
<Box width: 30, depth: 20, height: 10>
"""

Zusätzlich müsste man wahrscheinlich noch die x, y, z Position im Raum als Attribut anlegen.

Vielen Dank!

[frogi001]

Hallo,

@rogerb
Wie das Problem zu lösen ist? ... aus dem Stand weiß ich das nicht
... die Frage zielte auf die Art des Problems ab ( Mathe oder Programmieren ).

@Domilla
... habe das Skripte getestet ... es sind 29 Pakete, aber bei 27 Paketen ist
die Pallette voll. Sollen alle Pakete auf die Pallette passen?
Rein vom Volumen her würden (theoretisch) ja 40 Pakete auf die Pallette passen ...

[frogi001]

Hallo,
noch ein "Nachtrag"

@Domilla
Sind die Maßangaben zufällig ... es passen ja wirklich 40 Pakete auf die
Pallette in 5 Lagen:

1 Lage -> 8 Pakete 600 x 200 und 300 hoch ... und das ganze 5 Lagen ... wären 40 Pakete

[Domlla]

Maße sollen sich später an die DHL Standardmaße orientieren. Die eine andere Gruppe mit einem Förderband und Kameras einscannt und die Daten an uns übermittelt.
Die eigentliche Paketbezeichnung enthält dazu noch das Gewicht, die ID, Stauchwert und co. Eigentlich soll das Programm durchlaufen und im besten Fall, wie du schon gesagt hast, ausgeben wie die Pakete am optimalsten zu stapeln wären. Das ganze soll dann an einem Display ausgegeben werden, an dem ein Mitarbeiter quasi dann sieht wie er die Pakete zu stapeln hat.
Ich weis momentan leider nicht weiter. Es ist momentan auch noch ein Fehler drin, da er zur Zeit nur die erste Länge des Paketes an der Palette abzieht.
Quasi soll das Programm durch drehen der Pakete die beste Auslastung herausfinden und auch schauen ob Pakete mit unterschiedlicher Höhe z.B. 500 und 250, das quasi die 250 doppelt genommen werden können.
Gehe ich das Programm so überhaupt richtig an?
Vielen Dank für eure Hilfe.

[__deets__]

Nach meiner Einschätzung ist das eine Instanz des Rucksackproblems. https://de.wikipedia.org/wiki/Rucksackproblem Und damit ist das alles andere als trivial.

Ich denke da wirst du etwas mehr Gehirnschmalz reinstecken müssen. Im Wikipedia-Artikel sind ja eine Reihe von Verfahren und weiterführende links zu finden.

[__deets__]

Und nochmal die Frage: wer hat sich denn diese komische Kodierung für die Paketformate ausgedacht? Das muss doch so nicht sein, ein Tupel (600, 300, 200) wäre doch viel einfacher.

[frogi001]

Hallo,

ich bin noch ziemlich neu im Forum, und weiß nicht genau, ob man hier einfach über ein Problem - das sich
wahrscheinlich nicht nur auf die Programmiersprache Python beschränkt - weiterdiskutieren darf?

An einer Datenstruktur, wie von @rogerb angegeben, wird man wohl kaum vorbeikommen ... soll man
ja auch nicht, weil es Operationen wie das Drehen in jeder Richtung, unheimlich erleichtert.

Habe gerade den Beitrag von @__deets__ gelesen ... das wird kein 10-Zeiler ...

[frogi001]

Hallo,
vielleicht sollte man das Problem zuerst "vereinfachen" ... also, was ist die beste Belegung
mit Paketen für eine halbe, viertel oder achtel Pallette?
Wenn man für diese Größe eine akzeptable Lösung gefunden hat, dann weiter mit
der restlichen (Teil)Pallette ...

[__deets__]

@frogi001 das macht es nicht einfacher. Warum auch? Wenn du eine Lösung für eine Viertel Palette hast, dann nehme ich einfach meine Pakete, halbiere deren Dimensionen, werfe sie dem Löser vor, und skaliere wieder hoch. Und löse damit das ganze Problem Damit ist klar, dass es skaleninvariant ist.

[rogerb]

@Domlla,

Ich habe mal ein bisschen ge-googelt und bin auf das "3d Bin Packing Problem" gestoßen. Ich denke das geht auch in die Richtung des von __deets__ genannten "Rucksackproblems" (und der entsprechend weiter verlinkten).

Auf jeden Fall ist es gar nicht so einfach, besonders wenn man jede beliebige Paketgröße erlauben möchte. Es gibt aber zum Glück Lösungen in Python dazu:
https://github.com/Janet-19/3d-bin-packing-problem
Sie hat auf ihrer github Seite auch zwei wissenschaftliche Artikel zu dem Thema verlinkt.

Mit dem Programm kann man so ein Problem jedenfalls (heuristisch) lösen.
Das könnte schonmal ein Ansatz in die richtige Richtung sein. Denn damit werden die Pakete auf der Palette platziert und deren Position ausgegeben. Falls es nicht passt, werden die übrigen Pakete ausgegeben.
Ich habe mal ein bisschen damit gespielt und es funktioniert eigentlich ganz gut.

[rogerb]

@Domlla,

ich glaube das github repository hat wohl doch ein Problem.
Besser ist das:
https://pypi.org/project/py3dbp/
Auch das ist etwas merkwürdig programmiert, aber es scheint auf den ersten Blick ein sinnvolles Ergebnis zu liefern.

Hier eine Lösung für die von dir angegebenen Maße: (Ich habe es aber nicht im Detail geprüft)

Code: Alles auswählen

from py3dbp import Packer, Bin, Item

packer = Packer()

packer.add_bin(Bin("Palette", 1200, 800, 1500, 50))

for i in range(29):
    packer.add_item(Item("Paket", 600, 300, 200, 1))

packer.pack()

for b in packer.bins:
    print(b.string())

    print("FITTED ITEMS:")
    for item in b.items:
        print(f"====> {item.string()}")

    print("UNFITTED ITEMS:")
    for item in b.unfitted_items:
        print(f"====> {item.string()}")

"""
Ausgabe:

Palette(1200.000x800.000x1500.000, max_weight:50.000) vol(1440000000.000)
FITTED ITEMS:
====> Paket(600.000x300.000x200.000, weight: 1.000) pos([0, 0, 0]) rt(0) vol(36000000.000)
====> Paket(600.000x300.000x200.000, weight: 1.000) pos([Decimal('600.000'), 0, 0]) rt(0) vol(36000000.000)
====> Paket(600.000x300.000x200.000, weight: 1.000) pos([0, Decimal('300.000'), 0]) rt(0) vol(36000000.000)
====> Paket(600.000x300.000x200.000, weight: 1.000) pos([Decimal('600.000'), Decimal('300.000'), 0]) rt(0) vol(36000000.000)
====> Paket(600.000x300.000x200.000, weight: 1.000) pos([0, Decimal('600.000'), 0]) rt(2) vol(36000000.000)
====> Paket(600.000x300.000x200.000, weight: 1.000) pos([Decimal('300.000'), Decimal('600.000'), 0]) rt(2) vol(36000000.000)
====> Paket(600.000x300.000x200.000, weight: 1.000) pos([Decimal('600.000'), Decimal('600.000'), 0]) rt(2) vol(36000000.000)
====> Paket(600.000x300.000x200.000, weight: 1.000) pos([Decimal('900.000'), Decimal('600.000'), 0]) rt(2) vol(36000000.000)
====> Paket(600.000x300.000x200.000, weight: 1.000) pos([0, 0, Decimal('200.000')]) rt(0) vol(36000000.000)
====> Paket(600.000x300.000x200.000, weight: 1.000) pos([Decimal('600.000'), 0, Decimal('200.000')]) rt(0) vol(36000000.000)
====> Paket(600.000x300.000x200.000, weight: 1.000) pos([0, Decimal('300.000'), Decimal('200.000')]) rt(0) vol(36000000.000)
====> Paket(600.000x300.000x200.000, weight: 1.000) pos([Decimal('600.000'), Decimal('300.000'), Decimal('200.000')]) rt(0) vol(36000000.000)
====> Paket(600.000x300.000x200.000, weight: 1.000) pos([0, Decimal('600.000'), Decimal('600.000')]) rt(2) vol(36000000.000)
====> Paket(600.000x300.000x200.000, weight: 1.000) pos([Decimal('300.000'), Decimal('600.000'), Decimal('600.000')]) rt(2) vol(36000000.000)
====> Paket(600.000x300.000x200.000, weight: 1.000) pos([Decimal('600.000'), Decimal('600.000'), Decimal('600.000')]) rt(2) vol(36000000.000)
====> Paket(600.000x300.000x200.000, weight: 1.000) pos([Decimal('900.000'), Decimal('600.000'), Decimal('600.000')]) rt(2) vol(36000000.000)
====> Paket(600.000x300.000x200.000, weight: 1.000) pos([0, 0, Decimal('400.000')]) rt(0) vol(36000000.000)
====> Paket(600.000x300.000x200.000, weight: 1.000) pos([Decimal('600.000'), 0, Decimal('400.000')]) rt(0) vol(36000000.000)
====> Paket(600.000x300.000x200.000, weight: 1.000) pos([0, Decimal('300.000'), Decimal('400.000')]) rt(0) vol(36000000.000)
====> Paket(600.000x300.000x200.000, weight: 1.000) pos([Decimal('600.000'), Decimal('300.000'), Decimal('400.000')]) rt(0) vol(36000000.000)
====> Paket(600.000x300.000x200.000, weight: 1.000) pos([0, Decimal('600.000'), Decimal('1200.000')]) rt(5) vol(36000000.000)
====> Paket(600.000x300.000x200.000, weight: 1.000) pos([Decimal('600.000'), Decimal('600.000'), Decimal('1200.000')]) rt(5) vol(36000000.000)
====> Paket(600.000x300.000x200.000, weight: 1.000) pos([0, 0, Decimal('600.000')]) rt(0) vol(36000000.000)
====> Paket(600.000x300.000x200.000, weight: 1.000) pos([Decimal('600.000'), 0, Decimal('600.000')]) rt(0) vol(36000000.000)
====> Paket(600.000x300.000x200.000, weight: 1.000) pos([0, Decimal('300.000'), Decimal('600.000')]) rt(0) vol(36000000.000)
====> Paket(600.000x300.000x200.000, weight: 1.000) pos([Decimal('600.000'), Decimal('300.000'), Decimal('600.000')]) rt(0) vol(36000000.000)
====> Paket(600.000x300.000x200.000, weight: 1.000) pos([0, 0, Decimal('800.000')]) rt(0) vol(36000000.000)
====> Paket(600.000x300.000x200.000, weight: 1.000) pos([Decimal('600.000'), 0, Decimal('800.000')]) rt(0) vol(36000000.000)
====> Paket(600.000x300.000x200.000, weight: 1.000) pos([0, Decimal('300.000'), Decimal('800.000')]) rt(0) vol(36000000.000)
UNFITTED ITEMS:
"""

Auf jeden Fall scheint alles zu passen

[frogi001]

Hallo,
ich musste erst mal nachsehen, was Skaleninvarianz ist
Stimmt, das löst das Problem nicht.
Ich habe das Skript von @Domlla genommen, und die
Pallettengröße halbiert, geviertelt und geachtelt.

Code: Alles auswählen

laenge = [1200,600]
breite = [800,400]
hoehe = [1500,1200,900,600]
groesse = list(product(laenge,breite,hoehe))

Ergebnis:
1. Pallette schreibt man mit einem "l"
2. Es passen mehr Pakete auf die Palette ( 14 Pakete auf halbe Pal. -> 28 auf ganze Palette )
3. In einem Fall passen sogar 96 Pakete auf die Palette, obwohl vom Volumen her nur 40 Pakete Platz haben
Aber so kommt man auf alle Fälle nicht auf 40 Pakete ...

[Domlla]

Vielen Dank an alle

@rogerb

Ich glaube das ist genau das wonach wir gesucht haben. Leider habe ich nun ein Problem mit dem Installieren von py3dbp.
Ich gebe doch in die cmd einfach "pip install py3dbp", was er auch macht. Jedoch findet er das Modul später nicht. Wie kann ich das beheben?
Vielen Dank!

[__deets__]

Indem du es für das richtige Python installierst, das du auch später verwendest. Also die exakt gleiche Version, und ggf. auch das virtual env (falls eines benutzt wird, zb von pycharm)