Um stabile, sichere, dichte und möglichst hohe Ladeeinheiten bilden zu können, müssen zuerst Einflussfaktoren analysiert und definiert werden, damit sie bei der Packoptimierung genau berücksichtigt werden können. Die relevanten Einflussfaktoren werden hier in der vorliegenden Arbeit beschrieben bzw. definiert.

Die zu packenden bzw. stapelnden Waren werden Packobjekte genannt. Die Packobjekte im Distributionszentrum strecken sich von Konservendosen, Marmeladengläser und technischen Geräten im Umkarton, über Schrumpfeinheiten von Flaschen, Faltschachteln im Tray, bis zu Papiersäcken und Schrumpfeinheiten von Küchenpapieren etc (siehe Abb. 2). Sie sind sehr vielfältig in Geometrie und Form und sehr unterschiedlich hinsichtlich ihrer Größe bzw. Dimensionen. Um diese Objekte automatisch auf der Palette zu stapeln, muss ihre Geometrie genau berücksichtigt werden.

Abbildung 2: Packobjekte mit unterschiedlichen Eigenschaften wie Geometrie, Gewicht, Tragfähigkeit, Festigkeit etc. (Beispiel)

Die Analyse der Auftragstruktur zeigt, dass es hier um sehr stark heterogene Packobjekte handelt. Diese Heterogenität zeigt sich sowohl in den Geometrien und Abmessungen als auch in der Menge der Packobjekte.

Nach der Analyse der unterschiedlichen Geometrie der Waren werden die Packobjekte in quaderförmiges oder trapezförmiges Objekt vereinfacht. Die Maße eines Packobjektes werden in Länge, Breite, Höhe etc. in mm definiert.

Das Gewicht eines Packobjektes erstreckt sich von einigen 100 g bis zu 25 kg. Es ist von Packobjekt zu Packobjekt sehr unterschiedlich.

Die Tragfähigkeit ist eine Angabe, wie stark das Packobjekt gewichtsmäßig belastet werden kann. Es wird auch häufig von Festigkeit gesprochen. Die Packobjekte sind von der Tragfähigkeit bzw. Festigkeit her ebenfalls sehr unterschiedlich. Manche Produkte können stark belastet werden, andere können überhaupt kein Gewicht tragen. Tendenziell kann ein schweres Packobjekt auch mehr tragen, was aber auch nicht für jedes Produkt gilt. Es gibt Produkte, die zwar schwer sind, aber sie können nicht viel Gewicht tragen. Deswegen müssen das Gewicht und die Tragfähigkeit eines Packobjektes getrennt angegeben und berücksichtigt werden.

Es ist offensichtlich klar, dass ein Packobjekt nicht zu stark durch andere Packobjekte belastet werden darf. Dies fordert, schwerere Packobjekte möglichst nach unten und leichtere Packobjekte, die geringe Tragfähigkeit haben, nach oben zu platzieren.

Um die Stabilität der zu bildenden Ladeeinheit zu gewährleisten, muss zuerst jedes Packobjekt stabil auf andere Packobjekte gelegt werden. Dies erfordert einerseits, dass das Packobjekt eine genügende Auflagefläche aufweist, die von darunter liegenden Packobjekten gestützt wird, und andererseits keine Seite oder Kante des Packobjektes in der Luft hängt. Das Packobjekt darf auch nicht zu schräg (eine Seite hoch und eine Seite unter) angelegt werden. Darüber hinaus soll das Packobjekt möglichst andere Objekte in der Ebene berühren, so dass sich die Packobjekte in der Ladeeinheit nicht frei bewegen können.

Die Stabilität der Packobjekte, die nicht auf dem Boden des Packraums platziert sind, kann dadurch gewährleistet werden, dass ihre Grundfläche mindestens zu einem vorgegebenen Prozentsatz durch darunter liegende Packobjekte gestützt wird [Bortfeldt1999]. Eine andere Definition der stabilen Positionierung ist, dass der Flächenschwerpunkt des Packobjekts innerhalb der konvexen Hülle von Eckpunkten der überdeckten Packobjektflächen liegt [Strommer1992]. Sowohl der Prozentsatz als auch die Betrachtung des Schwerpunktes reichen nicht aus, um die Stabilität des Packobjektes genau zu definieren, denn von dem Packobjekt kann eine Seite in der Luft hängen, was zu Transportschäden führen kann.

Um die Stabilität eines Packobjektes genau zu definieren, wird die Grundfläche des Packobjektes in der vorliegenden Arbeit in 3 x 3 = 9 gleich großen Teilflächen eingeteilt (siehe Abb. 3). Diese Teilung ist eine Kompromisslösung zwischen der Genauigkeit der Stabilitätsprüfung und dem Rechenaufwand. Mit einer Teilung von 4 x 4 = 16 Teilflächen wäre der Rechenaufwand viel zu groß.

Abbildung 3: Teilung der Grundfläche eines Packobjektes

Um die Stabilität eines Packobjektes an einer gegebenen Position zu prüfen, wird die Unterstützung unter jeder Teilfläche (außer Teilfläche 9) ermittelt. Eine Teilfläche gilt als gestützt, wenn mindestens ein Punkt unterhalb dieser Teilfläche von anderen Objekten gestützt wird.

Ein Packobjekt ist an sich stabil, wenn mindestens vier Teilflächen in der in Abbildung 4 gezeigten Art von unteren Objekten gestützt werden.

Abbildung 4: Sichere Unterstützung eines Packobjektes von unteren Objekten

Theoretisch ist ein Packobjekt in der Regel auch stabil, wenn nur drei Teilflächen in der in Abbildung 5 gezeigten Art von darunter liegenden Packobjekten gestützt werden. Aus Festigkeitsgrund kann solche Konstruktion jedoch in unterem Bereich der Ladeeinheit nicht zugelassen werden, denn die Packobjekte können ansonst zerdrückt werden.

Abbildung 5: Sichere Unterstützung eines Packobjektes von unteren Objekten

Darüber hinaus muss auch geprüft werden, ob eine Seite des Packobjektes zu weit in der Luft hängt. Es ist ebenfalls nicht erlaubt, dass eine Ecke des Packobjektes zu weit in der Luft hängt. Die maximale Größe der Seite bzw. Ecke, die in der Luft hängen darf, wird über Parameter definiert und bei der Packoptimierung genau geprüft.

Abbildung 6: Zwei Ladeeinheiten aus homogenen Packobjekten; links Säulenstapelung und rechts Verbundstapelung

Die gebildete Ladeeinheit ist jedoch auch nicht stabil, wenn alle Packobjekte an sich stabil sind, aber voneinander getrennt in Säule bzw. Türme gestapelt werden (siehe linkes Bild in Abb. 6). Um die Turmbildung möglichst zu vermeiden, muss versucht werden, die Packobjekte möglichst verbunden zu stapeln. Eine hundertprozentige Verbundstapelung entsteht, wenn jedes Packobjekt auf mehr als einem Packobjekt unterer Lage steht (siehe rechtes Bild in Abb. 6 als Beispiel). Eine Verbundstapelung ist stabiler, weil die Packobjekte gegen das Rutschen bzw. Bewegen sich gegenseitig verhindern.

Die Stabilität einer Ladeeinheit beruht auf der Stabilität aller Packobjekte in der Ladeeinheit. Der Stabilitätsgrad eines Packobjektes, das auf darunter liegenden Packobjekten stabil gelegt wird, wird in der vorliegenden Arbeit mit folgenden Werten definiert:

Der maximale Wert des Stabilitätsgrades für ein Packobjekt liegt bei 100. Aus dieser Betrachtung wird der Stabilitätsgrad für jedes Packobjekt ermittelt. Betrachtet man alle Packobjekte in der Ladeeinheit in dieser Art, entsteht folgende Formel zur Ermittlung des Stabilitätsgrades der Ladeeinheit:

mit

Je größer der Stabilitätsgrad der Gesamtladeeinheit ist, desto stabiler ist die Ladeeinheit. Unter gewisser Grenze des Stabilitätsgrades wird die gebildete Ladeeinheit nicht akzeptiert, da sie zu wackelig ist.

Eine Warengruppe enthält Produkte, die in unterschiedlichen Entpackbereichen im Laden bzw. Filialen von der Palette abgenommen und ins Regal gestellt werden. Diese Warengruppen müssen bei der Optimierung ebenfalls berücksichtigt werden. Alle Waren von einer Warengruppe sollten einerseits auf der Palette möglichst zusammen liegen, andererseits haben die Warengruppen auch eine Reihenfolge, die von der Verteilung der Waren im Laden bzw. Filialen bestimmt wird. Diese Reihenfolge soll möglichst angehalten werden, denn das spart dem Einzelhändler Wege beim späteren Einsortieren der Ware.

Idealerweise werden die tragfähigen Packobjekte nach unten, wenig belastbare Packobjekte nach oben angeordnet. Dabei sollen die Warengruppen, die durch eine Vorgabe bestimmt wird, auch möglichst zusammengehalten werden. Das Anhalten von dieser Reihenfolge führt teilweise zum Konflikt, denn die Packobjekte, die in der ersten Warengruppe stehen und in unterem Bereich der Ladeeinheit gepackt werden sollen, haben nicht unbedingt die erforderliche Tragfähigkeit. Für diesen Fall müssen die Packobjekte aus der zweiten Warengruppe zuerst in unterem Bereich der Ladeeinheit angeordnet werden. Daher darf dem Zusammenhalt der Waren in einer Warengruppe keine zu hohe Priorität erteilt werden.

Angesichts der unterschiedlichen Gewichte, Tragfähigkeit und Warengruppen ist es wichtig, für jeden Packschritt das richtige Packobjekt zu nehmen bzw. zu selektieren. Die Selektion des Packobjektes ist ebenfalls ein multikriterielles Optimierungsproblem, da die unterschiedliche Gewichte, Tragfähigkeiten und Warengruppen dabei berücksichtigt werden. Welches Packobjekt an einer bestimmten Position selektiert wird, soll wesentlich von der Höheposition abhängig gemacht werden. Die Funktion zur Bewertung der Packobjekte in Abhängigkeit von der Höheposition muss daher entwickelt werden. Durch diese Bewertung wird bei jedem Schritt der Optimierung entschieden, welches Packobjekt an welcher Position am besten zu wählen ist.

Um möglichst hohe Ladeeinheit zu bilden, muss die Tragfähigkeit der Packobjekte ausgenutzt werden. Die Tragfähigkeit wird in der vorliegenden Arbeit in sechs Stufen bzw. Klassen (Tragfähigkeitsklassen) eingeteilt. Die Packobjekte, die mehr tragen können, sollen möglichst nach unten angeordnet werden. Dagegen müssen die Packobjekte, die wenig bzw. kein Gewicht tragen können, möglichst in oberem Bereich der Ladeeinheit gestapelt werden. Dies wird durch die Einführung folgender Funktion gewährleistet (siehe Abb. 7):

mit

Abbildung 7: Bewertungswerte der Tragfähigkeit in Abhängigkeit von der Höheposition z in der Ladeeinheit

Die Packobjekte von der ersten Tragfähigkeitsklasse (TragKls = 1) werden zum Beispiel in unterem Bereich sehr hoch bewertet (siehe Abb. 7). Dagegen werden die Packobjekte von sechsten Tragfähigkeitsklasse (TragKls = 6) in oberem Bereich sehr hoch bewertet (siehe Abb. 7).

Analog zur Funktion für die Bewertung der Tragfähigkeit werden auch Funktionen für das Gewicht und Warengruppe eingeführt. Zur Selektion eines Packobjektes wird dann folgende Formel als Zielfunktion verwendet:

mit

Um die Packobjekte vor Transportschäden zu schützen, darf der maximale Wert der Tragfähigkeit von keinem Packobjekt überschritten werden. Um dies zu gewährleisten, muss die Kraftübertragung von oberen Objekten zu unteren Objekten untersucht und definiert werden.

Abbildung 8: Abbildung zur Ermittlung der Kraftverteilung (Beispiel für ein Packobjekt, das auf zwei anderen Packobjekten steht)

Für die Ermittlung der Kraftübertragung wird angenommen, dass sich das Gewicht im Packobjekt selbst gleich verteilt. Der Schwerpunkt des Packobjekts wird dementsprechend an seinem geometrischen Mittelpunkt liegen. Auch die Verteilung der Kraft im Auflagebereich ist gleichmäßig. Daher liegt der Wirkungspunkt der Schwerkraft auf dem Mittepunkt der Auflagefläche. In unterer Abbildung gilt dann x1=x2 und x3=x4(siehe Abb. 8).

Die Kraftanteile f1 und f2 werden über folgende Formel ermittelt (siehe Abb. 8):

mit

In der Abb. 9 steht das betrachtete Packobjekt auf drei darunter stehenden Packobjekten. Die Kraftanteile f1, f2 und f3 können ähnlich ermittelt werden.

Abbildung 9: Ein Packobjekt steht auf drei unteren Packobjekten (Beispiel)

Im Allgemeinen muss folgendes lineares Gleichungssystem zur Ermittlung der Kraftanteile auf jedem darunter stehenden Packobjekte aufgestellt und gelöst werden:

n steht für die Anzahl der darunter stehenden Packobjekte. Die Beiwerte a11, a12 etc. werden aus der Position des betrachteten Packobjektes und der darunter stehenden Packobjekte im Programm ermittelt. f1, f2,..., fn sind die Kraftanteile an den Packobjekten und damit die zu bestimmenden Parameter. Die Lösung dieses Liniengleichungssystems kann über das Gauss-Seidel-Verfahren [WIKPEDIA2005] im Rechner ermittelt werden.

Die Kraftübertragung von oberen Packobjekten auf den unteren Packobjekten für die Gesamtladeeinheit wird dann in einer dynamischen Matrix gespeichert. Diese Matrix wird als „Relationship Matrix“ bezeichnet, weil sie die Beziehung der Packobjekte von oben nach unten darstellt.

Die Prüfung der Tragfähigkeit jedes Packobjektes für jeden Packschritt wird über diese Matrix durchgeführt. Das Gewicht jedes Packobjektes wird über die „Relationship Matrix“ von oben nach unten verteilt. Ist die Grenze der Tragfähigkeit eines Packobjektes erreicht, wird kein Packobjekt an der geprüften Stelle angeordnet. Dadurch ist gewährleistet, dass kein Packobjekt überlastet wird.

Für die Anordnung der Packobjekte auf der Palette werden einige grundlegende Strategien und Prioritäten ausgearbeitet. Diese Strategien sind im Optimierungsprogramm umgesetzt worden.

Die Anordnung der Packobjekte auf der Palette hat zum Ziel, die Packobjekte zuerst auf der hinteren Seite der Palette unter Berücksichtigung der Tragfähigkeit, des Gewichtes und der Warengruppe so anzuordnen, dass die gebildete Blöcke möglichst groß sind. Ein Block besteht aus einem oder mehreren Packobjekten, die zwar unterschiedliche Längen und Breiten haben können, aber ähnliche Höhen aufweisen, wobei die erforderliche Höhe auch durch Kombination von Packobjekten erreicht werden kann. Auf der hinteren Seite der Palette können meistens zwei Blöcke aus unterschiedlichen Packobjekten gebildet werden (siehe Abb. 10). Die ungenutzten Räume im Packraum werden als Resträume bezeichnet. Am Anfang steht ein Packraum zur Verfügung.

Abbildung 10: Bildung von Block 1 und 2 auf der hinteren Seite der Palette

Der Block 1 fängt von der linken hinteren Ecke an und wächst nach rechts und nach vorne. Der Block 2 fängt von der rechten hinteren Ecke an und wächst nach links und nach vorne. Mit der Anordnung der Packobjekte in Block 1 und 2 wird der Packraum verkleinert und auch geteilt. Danach wird der Restraum für den Block 3 bereitgestellt (siehe das linke Bild in Abb. 11).

Im Packraum für den Block 3 werden wieder Packobjekte erfasst, die eine ähnliche Höhe aufweisen (siehe das mittlere Bild in Abb. 11). Danach wird der Raum für den Block 4 bereitgestellt.

Im Packraum für den Block 4 werden ebenfalls Packobjekte erfasst, die eine ähnliche Höhe aufweisen (siehe das rechte Bild in Abb. 11).

Abbildung 11: Anordnung der Packobjekte in Block 3 und 4 sowie die Restrume nach der Anordnung

Die Packhöhe der Blöcke kann übrigens unterschiedlich sein.

Bei der Anordnung der Packobjekte in jedem Block werden alle zur Verfügung stehenden Packobjekte nach den definierten Funktionen bewertet (siehe „Bewertung und Selektion eines Packobjektes“). Für jedes Packobjekt werden alle ähnlichen Packobjekte ausgesucht und im Packraum angeordnet.

Es wird versucht, in jedem Block so viele Packobjekte wie möglich anzuordnen, damit die Blöcke möglich groß gebildet werden können. Nach der Bildung von Block 1 bis 4 werden die Resträume erfasst, gespeichert und für den nächsten Packschritt bereitgestellt.

Auf den Resträumen werden weitere Packobjekte angeordnet. Danach entstehen wieder weitere Resträume. Das Erfassen und die Verwaltung der Resträume ist eine der Hauptaufgaben der Packoptimierung. Nach jedem Packschritt ändern sich die Resträume und sie müssen erneut erfasst, bewertet und eventuell zusammengefasst werden. Grundsätzlich dürfen keine Resträume vernachlässigt werden, egal ob sie klein oder groß sind.

Dieser Prozess wird solange durchgeführt, bis entweder

Im Anschluss wird die gebildete Ladeeinheit bewertet (siehe „Bewertung und Selektion eines Packobjektes“) und in der Lösungsliste aufgenommen, wenn sie akzeptabel ist.

Für die Packoptimierung wird ständig versucht, die Blöcke möglichst groß wachsen zu lassen. So entstehen z.B. ganze Lagen, die auf der Palette angeordnet werden können (siehe das linke Bild in Abb. 12). Um diese zu erreichen, werden alle Packobjekte mit einer ähnlichen Höhe für jeden Packschritt ausgesucht, angeordnet und anschließend bewertet.

Abbildung 12: Bildung von ganzen Lagen und großen Blöcken (Beispiel)

Beim Packen in einem Block werden die Packobjekte so dicht wie möglich angeordnet. Nach der Anordnung werden die Packobjekte innerhalb eines Blockes jedoch möglichst auseinander gezogen, damit die Resträume für die nächsten Packschritte am größten bleiben. Diese gilt insbesondere für die ganzen Lagen (siehe das linke Bild in Abb. 12), denn die Staufläche auf der Palette würde ansonst immer kleiner werden. Dies würde zur schlechten Nutzung des Packraums führen.