Optimale Ladeeinheitenbildung für eine automatische Kommissionierungsanlage im Warendistributionszentrum 

Dr.-Ing. Hua Li
Prof. Dr. Michael ten Hompel
Fraunhofer Institut für Materialfluss und Logistik in Dortmund

Bei der Kommissionierung im Warendistributionszentrum müssen die heterogenen Produkte mit den unterschiedlichsten Eigenschaften stabil gestapelt und dürfen während des Transportes nicht beschädigt werden. Für eine automatische Kommissionieranlage wurde das neue Optimierungsprogramm UNIT_OrderPacking für die Planung und Optimierung der Ladeeinheiten eingesetzt. Nach der Problemstellung werden die Einflussfaktoren analysiert und definiert. Die Strategien zur Berücksichtigung solcher Faktoren im Optimierungsverfahren werden vorgestellt. Das gesamte Optimierungsverfahren wird anschließend in Teilproblemen dargestellt. Für jedes Teilproblem werden die Lösungsstrategien nach der Problemanalyse durch Verallgemeinerung der Lösungsvorgehensweise abgeleitet und zusammengefasst. Folgende Teilprobleme werden relativ ausführlich behandelt:
•	die Bewertung und Selektion eines Packobjektes für jeden Packschritt hinsichtlich der Tragfähigkeit, des Gewichtes und der Warengruppe,
•	die Kraftübertragung der Packobjekte von oben nach unten und die „Relationship Matrix“ der Packobjekte sowie
•	die Strategien und Prioritäten für das Anordnen und Stapeln der Packobjekte im Packraum.
1.	Einleitung
In einem Warendistributionszentrum werden die Waren häufig auftragbezogen auf einer Palette oder in einem Rollcontainer kommissioniert. Die manuelle Kommissionierung der verpackten Waren auf der Palette ist eine körperlich anstrengende Arbeit, da deren Gewicht bis zu 25 kg betragen kann und die Ladeeinheit bis zu zwei Meter hoch gebildet werden kann. Die Qualität der manuell kommissionierten Ladeeinheiten ist zudem stark vom Kommissionierpersonal abhängig. Manche Paletten sind gut – andere sehr schlecht gepackt. Bei der Kommissionierung müssen die Packer Produkte mit den unterschiedlichsten Verpackungsgeometrien stabil stapeln. Das unterschiedliche Gewicht und die unterschiedliche Tragfähigkeit der Packeinheiten müssen ebenfalls berücksichtigt werden. Der Stauraum auf der Palette soll einerseits ausgenutzt werden, andererseits müssen die Produkte vor Transportschäden geschützt sein.
Darüber hinaus kann die Höhe der Palette bei manueller Kommissionierung i.d.R nicht ausgenutzt werden, da die Waren über eine gewisse Höhe hinaus nicht mehr manuell gestapelt werden können. Die Höhe des Transportmittel-Laderaums kann deshalb nicht optimal genutzt werden.
Um diese Probleme zu lösen, wurde eine automatische Kommissionieranlage unserer Projektpartner für die physische Ladeeinheitenbildung entwickelt und in einem Warendistributionszentrum in den Produktionsbetrieb genommen. Diese Anlage mit 
automatischer Warenzufuhr und 
automatischem Stapeln der Waren auf der Palette
bildet optimale Ladeeinheiten und stellt das Bindeglied zwischen Lager- und Transportprozess dar. Für die Planung und Optimierung der Ladeeinheiten übernimmt nun ein neues Optimierungsprogramm die Denkleistung. 
2.	Problemstellung
Hier handelt es sich um eine Packoptimierung mit sehr heterogenen Packobjekten (siehe Abb. 1). Die Packobjekte unterscheiden sich von der Geometrie, Abmessungen, Gewicht, Tragfähigkeit und Warengruppen; letztere sollen möglichst zusammenhaltend in der Ladeeinheit angeordnet werden. 

 
Abbildung 1: Schematische Darstellung der Ladeeinheitenbildung von heterogenen Packobjekten
Der Ladungsträger ist eine flache Palette mit dem Zugang von oben und von allen vier Seiten (beim Rollcontainer von oben und von zwei gegenüberliegenden Seiten) und verfügt über einen quaderförmigen Stauraum mit den Maßen Länge, Breite und Höhe in mm.
Die Bildung der optimalen Ladeeinheiten von heterogenen Objekten im Kommissionierbereich ist ein multikriterielles Optimierungsproblem, das den Packproblemen zugeordnet werden kann. Das Lösen der Packprobleme wird als Packoptimierung bezeichnet. Hier soll einerseits die Anzahl der gebildeten Ladeeinheiten für einen Versandauftrag minimiert werden, anderseits soll die Reihenfolge der Warengruppen beim Entpacken in der Filiale angehalten werden. Darüber hinaus müssen verschiedene Randbedienungen wie die Tragfähigkeit bzw. Festigkeit und das Gewicht der Packobjekte berücksichtigt und die Stabilität der Ladeeinheit gewährleistet werden.
Die Realisierung der Packoptimierung setzt die Entwicklung rechnergestützter Verfahren voraus; sie ist aufgrund der Komplexität des Packproblems und vor allem der vielfältigen kombinatorischen Möglichkeiten und des enormen Rechenaufwands unumgänglich. 
2.1.	Relevante Einflussfaktoren
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.
2.2.	Die Geometrie und die Maße der Waren
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.

2.3.	Das Gewicht und die Tragfähigkeit der Waren
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.

2.4.	Stabilität des Packobjektes und der gebildeten Ladeeinheit
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:
•	100, wenn das Packobjekt auf zwei Packobjekten unterer Lage oder auf der Palette steht.
•	100, wenn das Packobjekt ein oder mehrere Packobjekte trägt, die wiederum von anderen Packobjekten getragen werden.
•	100, wenn das Packobjekt andere Objekte an zwei bis zu vier Seiten berührt. Je mehr es die berührenden Seiten gibt, desto stabiler ist das Packobjekt. Für diesen Punkt siehe das FSL-Kriterium („fully supported boxes with lateral support on at least three sides“) von Davies und Bischoff [Davies1999].
•	50, wenn das Packobjekt andere Objekte an einer Seite berührt.
•	20, wenn das Packobjekt keine Berührung an anderen Objekten in der Ebene hat.
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 
	=	Stabilitätsgrad der Gesamtladeeinheiten	
	=	Stabilitätsgrad des Packobjektes i	
n	=	Anzahl der Packobjekte in der Ladeeinheit	

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.

2.5.	Warengruppen hinsichtlich des Entpackprozesses 
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.

3.	Optimierungsverfahren
Die Lösungen der Packprobleme entstehen durch Kombinationen und Reihen von Lösungselementen. Der Gesamtablauf zur optimalen Ladeeinheitenbildung wird hier in Teilproblemen dargestellt. Für jedes Teilproblem werden die Lösungsstrategien nach der Problemanalyse durch Verallgemeinerung der Lösungsvorgehensweise abgeleitet und zusammengefasst. Die Integration der Strategien zur Lösung der Teilprobleme bildet dann das Gesamtverfahren zur Lösung des gesamten Packoptimierungsproblems.

3.1.	Bewertung und Selektion eines Packobjektes 
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

TragKl	Klasse der Tragfähigkeit eines Packobjektes	
z	Höheposition z in der Ladeeinheit	

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

f(TragKls,z)	Funktion zur Bewertung der Tragfähigkeit des Packobjektes in Abhängigkeit
von der Höheposition in der Ladeeinheit	
FctTragKls	Gewichtungsfaktor bzw. Steuerparameter für die Tragfähigkeit des Packobjektes. Erhöht man den Faktor FctTragKls, so erhält die Tragfähigkeit des Packobjektes mehr Gewicht für die Bewertung	
f(GewKls,z)	Funktion zur Bewertung des Gewichtes des Packobjektes in Abhängigkeit von der Höheposition in der Ladeeinheit	
FctGewKls	Gewichtungsfaktor bzw. Steuerparameter für das Gewicht des Packobjektes. Erhöht man den Faktor FctGewKls, so erhält das Gewicht des Packobjektes höhere Bewertung bei der Selektion von Packobjekten	
f(WGrp,z)	Funktion zur Bewertung der Warengruppe des Packobjektes in Abhängigkeit von der Höheposition in der Ladeeinheit	
FctWGrp	Gewichtungsfaktor bzw. Steuerparameter für die Warengruppe des Packobjektes. Erhöht man den Faktor FctWGrp, so erhält die Warengruppe des Packobjektes höhere Bewertung bei der Selektion von Packobjekten	
z	Höheposition z in der Ladeeinheit	
3.2.	Kraftübertragung und „Relationship Matrix“
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
f1, f2	der Kraftanteil an das Packobjekt 1 und 2 (siehe Abb. 8)	
f0	das Gewicht des betrachteten Packobjektes	
dx1, dx2	Abstand der Wirkungspunkte für f1 und f2 zum Mittepunkt des betrachteten Packobjektes. dx1 und dx2 lassen sich über die Position der Packobjekte ermitteln.	

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.

3.3.	Anordnung der Packobjekte im Packraum
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 
•	alle Packobjekte auf der Palette angeordnet werden,
•	das maximale Gewicht auf der Palette erreicht wird,
•	die Tragfähigkeit eines Packobjektes im unteren Bereich ausgeschöpft wird oder
•	kein Packobjekt in keinem der Resträume mehr passt.
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.
4.	Realisierung
Eine Grundidee der Strategien der Packoptimierung ist, den Optimierungsprozess durch Steuerparameter in den Zielfunktionen bzw. Bewertungsfunktionen von außen ohne Programmänderungen zu steuern. Sämtliche Steuerparameter (insgesamt ca. 80 Parameter) wurden bei der Implementierung besonders beachtet und im zu erstellenden Programm eingeführt. Durch Einführung von Steuerparametern kann der Optimierungsprozess am besten an das Spektrum von Packobjekten und vom Stauraum angepasst werden.
Die Wirkung der Steuerparameter auf die Optimierungsergebnisse wurde anhand von Testdaten untersucht. Aufgrund der Untersuchung kann die optimale Konstruktion der Steuerparameter für die Testdaten festgelegt werden.
Durch Einsatz des Programms wird nun das günstigste Packmuster für jede Ladeeinheit auf den Millimeter genau errechnet. Position und Orientierung der Objekte werden an das automatische Kommissionierungssystem übergeben. Dieses fordert die Packobjekte dann aus dem automatischen Lagersystem an und ein Roboterarm schichtet sie auf die Palette. Sensoren prüfen, ob an der geplanten Stelle tatsächlich Platz ist. 

Abbildung 13: Gebildete Ladeeinheiten eines Auftrags (von der ersten bis siebten Palette als Beispiel). Die Packobjekte mit dunklen Farben verfügen über eine große Tragfähigkeit. Dagegen sind andere Packobjekte weniger belastbar.
Mit dem Optimierungsprogramm werden bis heute schätzungsweise eine Million Ladeeinheiten bei einer Handelskette in den Vereinigten Staaten geplant und anschließend durch die automatische Palettieranlage physisch realisiert. Das System hat inzwischen die Anfangsschwierigkeiten überwunden und arbeitet jetzt automatisch und reibungslos.

Literatur
[Bortfeldt1999]	Bortfeldt, A.: Zwei Heuristiken für Strip-Packing-Probleme. IN. Diskussionsbeiträge des Fachbereichs Wirtschaftswissenschaft der Fernuniversität Hagen, Nr. 266, April 1999	
[Davies1999]	Davies, A. P.; Bischoff, E. E.:Weight Distribution Considerations in Container Loading. IN: European Journal of Operational Research 114, 1999, S. 509-527	
[Strommer1992]	Strommer W. M.: Verfahren zum automatischen Palettieren von quaderförmigen Packstücken im beliebigen Sortenmix. Berlin, Heidelberg: Springer1992	
[WIKPEDIA2005]	http://de.wikipedia.org/wiki/Gauss-Seidel-Verfahren