[C#] Palettenbeladung

[danieljess88]

Hallo Zusammen,

ich hab von meinem Ausbilder die Aufgabe bekommen, ein Beladungsprogramm zu erstellen, welches Paletten in LKWs stapelt. (Soll natürlich im Programm angezeigt werden wie die Paletten gestapelt werden)

Mein Problem:   Mir ist keine Funktion/Rechenweg eingefallen um die Paletten richtig zu stapeln sodass es am wenigsten Platz verbraucht.

Hoffentlich kann mir hier jemand einen Tipp oder ein Rechenbeispiel zeigen.

 

[arlegermi]

Klingt so ein bisschen nach dem Rucksackproblem - eine wirklich optimale Lösung ist da eher schwierig. Für den Normalfall reicht ja aber eine Näherung.

Eine naive Lösung wäre etwas in der folgenden Art:

var lkw = nächsterLkw;

for(Palette p in allePaletten.SortiereNachGroesse())
  if p.Verladen:
	continue
  if PalettePasstInLkw(lkw, p):
    lkw.Paletten.Add(p)
    lkw.Platz -= p.Groesse
    p.Verladen = true      

Gegebenenfalls dann eben eine Schleife außen drum, die die LKW durchgeht.

So bekommst du natürlich keine gleichmäßige Verteilung auf die Fahrzeuge hin, wenn das gewünscht ist. Und es ist auch keine optimale Platznutzung in den einzelnen LKW gewährleistet.

Bearbeitet 1. April 2019 von arlegermi

[NTC_Baumi]

Ich weiß nicht ob ich gerade zu einfach denke... ich würde einfach Anhand der Grundfläche die Paletten aufteilen? Die Darstellung würde ich mit einer einfachen Variablen machen die jeweils für den "Stack" an Paletten hochzählt. Auch denkbar wäre ein drei Dimensionales Array mit Position X, Position Y und Höhe (Anzahl).

[danieljess88]

Hallo NTC_Baumi,

die Idee hatte ich auch, ist natürlich einfach wenn die Paletten alle gleich groß sind. Hab aber vergessen zu erwähnen das das Programm die Paletten mit unterschiedlichen Größen stapeln können soll. ( Bsp: Europalette: L: 1,2 cm B: 0,8cm. Industriepalette: L: 1,0cm B: 1,2cm. Testpalette(Palette mit ausgedachter Länge und Breite): L: 1,3cm B: 1,4cm) Die Höhe ist fürs erste mal egal.

[NTC_Baumi]

vor 1 Minute schrieb danieljess88:

die Idee hatte ich auch, ist natürlich einfach wenn die Paletten alle gleich groß sind. Hab aber vergessen zu erwähnen das das Programm die Paletten mit unterschiedlichen Größen stapeln können soll. ( Bsp: Europalette: L: 1,2 cm B: 0,8cm. Industriepalette: L: 1,0cm B: 1,2cm. Testpalette(Palette mit ausgedachter Länge und Breite): L: 1,3cm B: 1,4cm) Die Höhe ist fürs erste mal egal.

ich würde die Paletten sortiert abstellen, damit es sich besser auf dem LKW sichern lässt (ich fürchte das war nicht hilfreich)

[danieljess88]

 Ne ist nicht wirklich Hilfreich gewesen.

Aber sortieren ist ein guter Punkt. Wichtig ist es ja das es Platzsparend sortiert wird.

[NTC_Baumi]

vor 18 Minuten schrieb danieljess88:

Ne ist nicht wirklich Hilfreich gewesen

Zu meiner verteidigung, ich bin kein Entwickler.

Hab noch eine sehr sehr "dreckige" Lösung. Errechne mit einem Zufallsalgo. ein paar tausend Lösungen für deine aktuelle Paletten konfiguration und teste durch, welche am besten ist. Solange die Anzahl deiner Paletten im Rahmen bleibt, und du Eingrenzungen machst (z.B. gleiche Paletten übereinander), sollte das zu einem effektiven Ergebnis führen.

[KeeperOfCoffee]

Ist das alles an Vorgaben? Gibt es da nix zu beachten? Vorschriften? Irgendwas von ner Seite zu scannen? Kommt mir jetzt sehr wenig vor die Problembeschreibung

[Minerva/8]

Wie soll das dargestellt werden ? Als 3D Model, 2D mit Top Down View?

[danieljess88]

vor 3 Minuten schrieb KeeperOfCoffee:

Ist das alles an Vorgaben? Gibt es da nix zu beachten? Vorschriften? Irgendwas von ner Seite zu scannen? Kommt mir jetzt sehr wenig vor die Problembeschreibung

Natürlich existiert da noch mehr, aber da möchte ich mich dann auch selber noch dransetzten.

Wichtig für mich wäre im Moment nur ein guter Rechenweg/Funktion. Wenn ich die habe kann ich zumindest weitermachen und mich bei weiteren Problemen wieder hier melden.

 

vor 31 Minuten schrieb Minerva/8:

Wie soll das dargestellt werden ? Als 3D Model, 2D mit Top Down View?

Als 3D Model welches man noch drehen kann in jede beliebige Richtung.

[Whiz-zarD]

vor einer Stunde schrieb danieljess88:

Mein Problem:   Mir ist keine Funktion/Rechenweg eingefallen um die Paletten richtig zu stapeln sodass es am wenigsten Platz verbraucht. 

Es gibt nun mal nicht für alles einen vorgefertigten Lösungsweg.

vor 3 Minuten schrieb danieljess88:

Natürlich existiert da noch mehr, aber da möchte ich mich dann auch selber noch dransetzten.

Die sind aber essentiell für die Lösung. z.B. ist überhaupt nicht klar, ob die Paletten gedreht oder sogar gestapelt werden können oder ob auch die Last im LKW verteilt werden muss, also z.B. ob schwere Paletten unten liegen und dann leichtere Paletten oben drauf?

vor 4 Minuten schrieb danieljess88:

Wichtig für mich wäre im Moment nur ein guter Rechenweg/Funktion. Wenn ich die habe kann ich zumindest weitermachen und mich bei weiteren Problemen wieder hier melden.

Davon war bis jetzt nie die Rede und erfordert mehr als hier bekannt war, denn es muss nicht nur ausgerechnet werden, welche Paletten nun dazu führen, dass die Ladung optimal verteilt werden, sondern es müssen ja noch die Positionen der einzelnen Paletten bestimmt werden, wo sie sich dann im LKW befinden. 

Ich denke auch nicht, dass es hier einen einfachen Rechenweg gibt, sondern hier muss man wohl mit Kombinatorik ran. Sprich, man muss alle Kombinationen durchspielen und überprüfen, was die beste Kombination ist. Ich würde also die Liste der Paletten nehmen und mir die erste Palette schnappen und über ein Interationsverfahren alle Kombinationen mit allen anderen Paletten raussuchen, die die Fläche des LKWs bzw. das Volumen des LKWs, sofern Paletten stapelbar sind, nicht überschreiten, denn das sind die Kandidaten, die in den LKW reinpassen könnten. Nun muss man mit der Liste der Kombinationen rumspielen und schauen, welche der Kombinationen tatsächlich in den LKW passen. Dafür muss dann die Länge, Breite und sofern Stapelbar die Höhe berücksichtigen. Hier steckt der meiste Gehirnschmalz drinnen. Wenn man dann mögliche LKW-Beladungen gefunden hat, wählt man die mit der größten Fläche bzw. mit dem größten Volumen und streicht diese Paletten aus der Gesamtliste und fängt von Vorne an.

[danieljess88]

vor 19 Minuten schrieb Whiz-zarD:

Es gibt nun mal nicht für alles einen vorgefertigten Lösungsweg.

Die sind aber essentiell für die Lösung. z.B. ist überhaupt nicht klar, ob die Paletten gedreht oder sogar gestapelt werden können oder ob auch die Last im LKW verteilt werden muss, also z.B. ob schwere Paletten unten liegen und dann leichtere Paletten oben drauf?

Davon war bis jetzt nie die Rede und erfordert mehr als hier bekannt war, denn es muss nicht nur ausgerechnet werden, welche Paletten nun dazu führen, dass die Ladung optimal verteilt werden, sondern es müssen ja noch die Positionen der einzelnen Paletten bestimmt werden, wo sie sich dann im LKW befinden. 

Ich denke auch nicht, dass es hier einen einfachen Rechenweg gibt, sondern hier muss man wohl mit Kombinatorik ran. Sprich, man muss alle Kombinationen durchspielen und überprüfen, was die beste Kombination ist. Ich würde also die Liste der Paletten nehmen und mir die erste Palette schnappen und über ein Interationsverfahren alle Kombinationen mit allen anderen Paletten raussuchen, die die Fläche des LKWs bzw. das Volumen des LKWs, sofern Paletten stapelbar sind, nicht überschreiten, denn das sind die Kandidaten, die in den LKW reinpassen könnten. Nun muss man mit der Liste der Kombinationen rumspielen und schauen, welche der Kombinationen tatsächlich in den LKW passen. Dafür muss dann die Länge, Breite und sofern Stapelbar die Höhe berücksichtigen. Hier steckt der meiste Gehirnschmalz drinnen. Wenn man dann mögliche LKW-Beladungen gefunden hat, wählt man die mit der größten Fläche bzw. mit dem größten Volumen und streicht diese Paletten aus der Gesamtliste und fängt von Vorne an.

Danke für deine Antwort. Um fürs erste mal die Fragen geklärt zu haben.

- Die Paletten können nicht aufeinander gestapelt werden.

- Die Gewichtsverteilung ist nicht wichtig, wichtig ist nur durch die Flächen bzw. durch die Länge und Breite angaben, die Paletten passend zu sortieren.

- Die Paletten kann man drehen wie man will, halt so drehen damit es Platzsparend ist

 

Die Möglichkeit mit den Kombinationen habe ich schon mal Probiert. (da habe ich mir auch schon ein paar ausgedacht, die auch schon Funktionieren. Ich schaffe aber mit meinen Kombinationen Max. 3 verschiedene Paletten zu beladen).

Ich kann euch ja mal ein Beispiel geben, welches mit dem Programm platzsparend beladen werden soll.

LKW-Ladefläche: 13,6 x 2,4m

Europalette: 1,2 x 0,8m   Anzahl an Paletten: 2

Industriepalette: 1,0 x 1,2m   Anzahl an Paletten: 9

Testpalette: 1,3 x 1,4m     Anzahl an Paletten: 10