<?xml version="1.0" encoding="UTF-8"?>
<!DOCTYPE article PUBLIC "-//OASIS//DTD DocBook XML V4.2//EN" "http://www.oasis-open.org/docbook/xml/4.2/docbookx.dtd">
<article lang="de"><title>Optimale Ladeeinheitenbildung für eine automatische Kommissionierungsanlage im Warendistributionszentrum </title><articleinfo><authorblurb><para role="author">Dr.-Ing. Hua Li</para><para role="author">Prof. Dr. Michael ten Hompel</para><para role="authorinfo">Fraunhofer Institut für Materialfluss und Logistik in Dortmund</para></authorblurb><abstract lang="de"><para role="abstractDE"><phrase role="abstractDE Char">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:</phrase></para></abstract><authorgroup><author><firstname>Hua</firstname><surname>Li</surname><affiliation><orgname>Fraunhofer Institut für Materialfluss und Logistik in Dortmund</orgname></affiliation></author><author><firstname>Michael</firstname><surname>ten Hompel</surname><affiliation><orgname>Fraunhofer Institut für Materialfluss und Logistik in Dortmund</orgname></affiliation></author></authorgroup><biblioid class="uri">urn:nbn:de:0009-12-6077</biblioid><biblioid class="doi">DOI 10.2195/LJ_Not_Ref_Li_102006</biblioid><keywordset><keyword>10.2195/LJ_Not_Ref_Li_92006</keyword></keywordset><subjectset scheme=""><subject></subject></subjectset><legalnotice><title>Lizenz</title><para>Jedermann darf dieses Werk unter den Bedingungen der Digital Peer Publishing Lizenz elektronisch übermitteln und zum Download bereitstellen. Der Lizenztext ist im Internet abrufbar unter der Adresse http://www.dipp.nrw.de/lizenzen/dppl/dppl/DPPL_v2_de_06-2004.html</para></legalnotice><titleabbrev></titleabbrev><volumenum>2006</volumenum><issuenum>September</issuenum><biblioset relation="journal"><issn>ISSN:1860-5923</issn><title>Logistics Journal</title></biblioset></articleinfo><section><title><phrase role="GEN_upcast-HEADINGNUMBER">1.	</phrase>Einleitung</title><para role="text">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.</para><para role="text">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.</para><para role="text">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 </para><para role="text">automatischer Warenzufuhr und </para><para role="text">automatischem Stapeln der Waren auf der Palette</para><para role="text">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. </para></section><section><title><phrase role="GEN_upcast-HEADINGNUMBER">2.	</phrase>Problemstellung</title><para role="text">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. </para><para role="Abbildung" /><para role="Abbildung" /><para role="Abbildung"><mediaobject><imageobject><imagedata width="158.76mm" depth="37.15mm" fileref="dippArticle-1.png" format="PNG" srccredit="embed" /></imageobject><caption><para role="caption">Abbildung <phrase role="GEN_SEQ">1</phrase>: Schematische Darstellung der Ladeeinheitenbildung von heterogenen Packobjekten</para></caption></mediaobject> </para><para role="text">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.</para><para role="text">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.</para><para role="text">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. </para><section><title><phrase role="GEN_upcast-HEADINGNUMBER">2.1.	</phrase>Relevante Einflussfaktoren</title><para role="text">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.</para></section><section><title><phrase role="GEN_upcast-HEADINGNUMBER">2.2.	</phrase>Die Geometrie und die Maße der Waren</title><para role="text">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.</para><para role="Abbildung"><mediaobject><imageobject><imagedata width="158.76mm" depth="24.45mm" fileref="dippArticle-2.png" format="PNG" srccredit="embed" /></imageobject><caption><para role="caption">Abbildung <phrase role="GEN_SEQ">2</phrase>: Packobjekte mit  unterschiedlichen Eigenschaften wie Geometrie, Gewicht, Tragfähigkeit, Festigkeit etc. (Beispiel)</para></caption></mediaobject></para><para role="text" /><para role="text">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.</para><para role="text">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.</para><para /></section><section><title><phrase role="GEN_upcast-HEADINGNUMBER">2.3.	</phrase>Das Gewicht und die Tragfähigkeit der Waren</title><para role="text">Das Gewicht eines Packobjektes erstreckt sich von einigen 100 g bis zu 25 kg. Es ist von Packobjekt zu Packobjekt sehr unterschiedlich. </para><para role="text">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.</para><para role="text">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.</para><para /></section><section><title><phrase role="GEN_upcast-HEADINGNUMBER">2.4.	</phrase>Stabilität des Packobjektes und der gebildeten Ladeeinheit</title><para role="text">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.</para><para role="text">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 <link linkend="Bortfeld1999">[Bortfeldt1999]</link>. 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 <link linkend="Strommer1992">[Strommer1992]</link>. 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.</para><para role="text">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 <emphasis role="bold">Teilflächen</emphasis> 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ß.</para><para role="Abbildung"><mediaobject><imageobject><imagedata width="158.76mm" depth="63.86mm" fileref="dippArticle-3.png" format="PNG" srccredit="embed" /></imageobject><caption><para role="caption">Abbildung <phrase role="GEN_SEQ">3</phrase>: Teilung der Grundfläche eines Packobjektes</para></caption></mediaobject></para><para role="text">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.</para><para role="text">Ein Packobjekt ist an sich stabil, wenn mindestens vier Teilflächen in der in Abbildung 4 gezeigten Art von unteren Objekten gestützt werden. </para><para role="text" /><para role="text" /><para role="Abbildung"><mediaobject><imageobject><imagedata width="158.76mm" depth="16.58mm" fileref="dippArticle-4.png" format="PNG" srccredit="embed" /></imageobject><caption><para role="caption">Abbildung <phrase role="GEN_SEQ">4</phrase>: Sichere Unterstützung eines Packobjektes von unteren Objekten</para></caption></mediaobject></para><para role="text">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. </para><para role="Abbildung"><mediaobject><imageobject><imagedata width="105.84mm" depth="16.58mm" fileref="dippArticle-5.png" format="PNG" srccredit="embed" /></imageobject><caption><para role="caption">Abbildung <phrase role="GEN_SEQ">5</phrase>: Sichere Unterstützung eines Packobjektes von unteren Objekten</para></caption></mediaobject></para><para role="text">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.</para><para role="Abbildung"><mediaobject><imageobject><imagedata width="125.24mm" depth="66.33mm" fileref="dippArticle-6.png" format="PNG" srccredit="embed" /></imageobject><caption><para role="caption">Abbildung <phrase role="GEN_SEQ">6</phrase>: Zwei Ladeeinheiten aus homogenen Packobjekten; links Säulenstapelung und rechts Verbundstapelung</para></caption></mediaobject></para><para role="text" /><para role="text">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.</para><para /><para role="text" /><para role="text">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:</para><itemizedlist mark="disc" spacing="normal"><listitem><para role="text">100, wenn das Packobjekt auf zwei Packobjekten unterer Lage oder auf der Palette steht.</para></listitem><listitem><para role="text">100, wenn das Packobjekt ein oder mehrere Packobjekte trägt, die wiederum von anderen Packobjekten getragen werden.</para></listitem><listitem><para role="text">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 <link linkend="Davies1999">[Davies1999]</link>.</para></listitem><listitem><para role="text">50, wenn das Packobjekt andere Objekte an einer Seite berührt.</para></listitem><listitem><para role="text">20, wenn das Packobjekt keine Berührung an anderen Objekten in der Ebene hat.</para></listitem></itemizedlist><para role="text">Der maximale Wert des Stabilitätsgrades <inlinemediaobject><imageobject><imagedata width="4.22mm" depth="6.35mm" fileref="dippArticle-7.png" format="PNG" srccredit="embed" /></imageobject></inlinemediaobject> 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:</para><para role="text"><inlinemediaobject><imageobject><imagedata width="24.33mm" depth="11.98mm" fileref="dippArticle-8.png" format="PNG" srccredit="embed" /></imageobject></inlinemediaobject></para><para role="text">mit </para><informaltable frame="none"><tgroup cols="3"><colspec colname="col1" colwidth="41.4pt" colnum="1" /><colspec colname="col2" colwidth="36.0pt" colnum="2" /><colspec colname="col3" colwidth="386.9pt" colnum="3" /><tbody><row><entry colname="col1" valign="top" rowsep="0" colsep="0" align="left"><para role="formelinfo"><inlinemediaobject><imageobject><imagedata width="6.69mm" depth="6.0mm" fileref="dippArticle-9.png" format="PNG" srccredit="embed" /></imageobject></inlinemediaobject></para></entry><entry colname="col2" valign="top" rowsep="0" colsep="0" align="left"><para role="formelinfo">=</para></entry><entry colname="col3" valign="top" rowsep="0" colsep="0" align="left"><para role="formelinfo">Stabilitätsgrad der Gesamtladeeinheiten</para></entry></row><row><entry colname="col1" valign="top" rowsep="0" colsep="0" align="left"><para role="formelinfo"><inlinemediaobject><imageobject><imagedata width="4.22mm" depth="6.35mm" fileref="dippArticle-10.png" format="PNG" srccredit="embed" /></imageobject></inlinemediaobject></para></entry><entry colname="col2" valign="top" rowsep="0" colsep="0" align="left"><para role="formelinfo">=</para></entry><entry colname="col3" valign="top" rowsep="0" colsep="0" align="left"><para role="formelinfo">Stabilitätsgrad des Packobjektes i</para></entry></row><row><entry colname="col1" valign="top" rowsep="0" colsep="0" align="left"><para role="formelinfo">n</para></entry><entry colname="col2" valign="top" rowsep="0" colsep="0" align="left"><para role="formelinfo">=</para></entry><entry colname="col3" valign="top" rowsep="0" colsep="0" align="left"><para role="formelinfo">Anzahl der Packobjekte in der Ladeeinheit</para></entry></row></tbody></tgroup></informaltable><para role="text" /><para role="text">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.</para><para /></section><section><title><phrase role="GEN_upcast-HEADINGNUMBER">2.5.	</phrase>Warengruppen hinsichtlich des Entpackprozesses </title><para role="text">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.</para><para /></section></section><section><title><phrase role="GEN_upcast-HEADINGNUMBER">3.	</phrase>Optimierungsverfahren</title><para role="text">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.</para><para /><section><title><phrase role="GEN_upcast-HEADINGNUMBER">3.1.	</phrase>Bewertung und Selektion eines Packobjektes </title><para role="text">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.</para><para role="text">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.</para><para role="text">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):</para><para role="text"><inlinemediaobject><imageobject><imagedata width="32.09mm" depth="5.63mm" fileref="dippArticle-11.png" format="PNG" srccredit="embed" /></imageobject></inlinemediaobject></para><para role="text">mit</para><para role="text" /><informaltable frame="all"><tgroup cols="2"><colspec colname="col1" colwidth="59.4pt" colnum="1" /><colspec colname="col2" colwidth="401.2pt" colnum="2" /><tbody><row><entry colname="col1" valign="top" rowsep="1" colsep="1" align="left"><para role="formelinfo">TragKl</para></entry><entry colname="col2" valign="top" rowsep="1" colsep="1" align="left"><para role="formelinfo">Klasse der Tragfähigkeit eines Packobjektes</para></entry></row><row><entry colname="col1" valign="top" rowsep="1" colsep="1" align="left"><para role="formelinfo">z</para></entry><entry colname="col2" valign="top" rowsep="1" colsep="1" align="left"><para role="formelinfo">Höheposition z in der Ladeeinheit</para></entry></row></tbody></tgroup></informaltable><para role="text" /><para role="Abbildung"><mediaobject><imageobject><imagedata width="158.76mm" depth="103.83mm" fileref="dippArticle-12.png" format="PNG" srccredit="embed" /></imageobject><caption><para role="caption">Abbildung <phrase role="GEN_SEQ">7</phrase>: Bewertungswerte der Tragfähigkeit in Abhängigkeit von der Höheposition z in der Ladeeinheit</para></caption></mediaobject></para><para role="text">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).</para><para role="text">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:</para><para><inlinemediaobject><imageobject><imagedata width="53.24mm" depth="6.69mm" fileref="dippArticle-13.png" format="PNG" srccredit="embed" /></imageobject></inlinemediaobject></para><para><inlinemediaobject><imageobject><imagedata width="45.16mm" depth="12.7mm" fileref="dippArticle-14.png" format="PNG" srccredit="embed" /></imageobject></inlinemediaobject></para><para role="text">mit</para><para role="text" /><informaltable frame="none"><tgroup cols="2"><colspec colname="col1" colwidth="104.4pt" colnum="1" /><colspec colname="col2" colwidth="356.1pt" colnum="2" /><tbody><row><entry colname="col1" valign="top" rowsep="0" colsep="0" align="left"><para role="formelinfo">f(TragKls,z)</para></entry><entry colname="col2" valign="top" rowsep="0" colsep="0" align="left"><para role="formelinfo">Funktion zur Bewertung der Tragfähigkeit des Packobjektes in Abhängigkeit</para><para role="formelinfo">von der Höheposition in der Ladeeinheit</para></entry></row><row><entry colname="col1" valign="top" rowsep="0" colsep="0" align="left"><para role="formelinfo">FctTragKls</para></entry><entry colname="col2" valign="top" rowsep="0" colsep="0" align="left"><para role="formelinfo">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</para></entry></row><row><entry colname="col1" valign="top" rowsep="0" colsep="0" align="left"><para role="formelinfo">f(GewKls,z)</para></entry><entry colname="col2" valign="top" rowsep="0" colsep="0" align="left"><para role="formelinfo">Funktion zur Bewertung des Gewichtes des Packobjektes in Abhängigkeit von der Höheposition in der Ladeeinheit</para></entry></row><row><entry colname="col1" valign="top" rowsep="0" colsep="0" align="left"><para role="formelinfo">FctGewKls</para></entry><entry colname="col2" valign="top" rowsep="0" colsep="0" align="left"><para role="formelinfo">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</para></entry></row><row><entry colname="col1" valign="top" rowsep="0" colsep="0" align="left"><para role="formelinfo">f(WGrp,z)</para></entry><entry colname="col2" valign="top" rowsep="0" colsep="0" align="left"><para role="formelinfo">Funktion zur Bewertung der Warengruppe des Packobjektes in Abhängigkeit von der Höheposition in der Ladeeinheit</para></entry></row><row><entry colname="col1" valign="top" rowsep="0" colsep="0" align="left"><para role="formelinfo">FctWGrp</para></entry><entry colname="col2" valign="top" rowsep="0" colsep="0" align="left"><para role="formelinfo">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</para></entry></row><row><entry colname="col1" valign="top" rowsep="0" colsep="0" align="left"><para role="formelinfo">z</para></entry><entry colname="col2" valign="top" rowsep="0" colsep="0" align="left"><para role="formelinfo">Höheposition z in der Ladeeinheit</para></entry></row></tbody></tgroup></informaltable></section><section><title><phrase role="GEN_upcast-HEADINGNUMBER">3.2.	</phrase>Kraftübertragung und „Relationship Matrix“</title><para role="text">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. </para><para role="Abbildung"><mediaobject><imageobject><imagedata width="86.44mm" depth="75.15mm" fileref="dippArticle-15.png" format="PNG" srccredit="embed" /></imageobject><caption><para role="caption">Abbildung <phrase role="GEN_SEQ">8</phrase>: Abbildung zur Ermittlung der Kraftverteilung (Beispiel für ein Packobjekt, das auf zwei anderen Packobjekten steht)</para></caption></mediaobject></para><para role="text">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).</para><para role="text" /><para role="text" /><para role="text">Die Kraftanteile f1 und f2 werden über folgende Formel ermittelt (siehe Abb. 8):</para><para><inlinemediaobject><imageobject><imagedata width="34.19mm" depth="12.7mm" fileref="dippArticle-16.png" format="PNG" srccredit="embed" /></imageobject></inlinemediaobject></para><para role="text">mit</para><informaltable frame="none"><tgroup cols="2"><colspec colname="col1" colwidth="104.4pt" colnum="1" /><colspec colname="col2" colwidth="356.1pt" colnum="2" /><tbody><row><entry colname="col1" valign="top" rowsep="0" colsep="0" align="left"><para role="formelinfo"><anchor id="OLE_LINK1" />f1, f2</para></entry><entry colname="col2" valign="top" rowsep="0" colsep="0" align="left"><para role="formelinfo">der Kraftanteil an das Packobjekt 1 und 2 (siehe Abb. 8)</para></entry></row><row><entry colname="col1" valign="top" rowsep="0" colsep="0" align="left"><para role="formelinfo">f0</para></entry><entry colname="col2" valign="top" rowsep="0" colsep="0" align="left"><para role="formelinfo">das Gewicht des betrachteten Packobjektes</para></entry></row><row><entry colname="col1" valign="top" rowsep="0" colsep="0" align="left"><para role="formelinfo">dx1, dx2</para></entry><entry colname="col2" valign="top" rowsep="0" colsep="0" align="left"><para role="formelinfo">Abstand der Wirkungspunkte für f1 und f2 zum Mittepunkt des betrachteten Packobjektes. dx1 und dx2 lassen sich über die Position der Packobjekte ermitteln.</para></entry></row></tbody></tgroup></informaltable><para role="text" /><para role="text">In der Abb. 9 steht das betrachtete Packobjekt auf drei darunter stehenden Packobjekten. Die Kraftanteile <emphasis>f1</emphasis>, <emphasis>f2</emphasis> und <emphasis>f3</emphasis> können ähnlich ermittelt werden.</para><para role="Abbildung"><mediaobject><imageobject><imagedata width="93.84mm" depth="55.74mm" fileref="dippArticle-17.png" format="PNG" srccredit="embed" /></imageobject><caption><para role="caption">Abbildung <phrase role="GEN_SEQ">9</phrase>: Ein Packobjekt steht auf drei unteren Packobjekten (Beispiel)</para></caption></mediaobject></para><para role="text">Im Allgemeinen muss folgendes lineares Gleichungssystem zur Ermittlung der Kraftanteile auf jedem darunter stehenden Packobjekte aufgestellt und gelöst werden:</para><para role="text" /><informaltable frame="none"><tgroup cols="1"><colspec colname="col1" colwidth="230.3pt" colnum="1" /><tbody><row><entry colname="col1" valign="top" rowsep="0" colsep="0" align="justify"><para role="text"><inlinemediaobject><imageobject><imagedata width="57.15mm" depth="6.35mm" fileref="dippArticle-18.png" format="PNG" srccredit="embed" /></imageobject></inlinemediaobject></para></entry></row><row><entry colname="col1" valign="top" rowsep="0" colsep="0" align="justify"><para role="text"><inlinemediaobject><imageobject><imagedata width="56.43mm" depth="6.35mm" fileref="dippArticle-19.png" format="PNG" srccredit="embed" /></imageobject></inlinemediaobject></para></entry></row><row><entry colname="col1" valign="top" rowsep="0" colsep="0" align="justify"><para role="text">...</para></entry></row><row><entry colname="col1" valign="top" rowsep="0" colsep="0" align="justify"><para role="text"><inlinemediaobject><imageobject><imagedata width="56.43mm" depth="6.35mm" fileref="dippArticle-20.png" format="PNG" srccredit="embed" /></imageobject></inlinemediaobject></para></entry></row><row><entry colname="col1" valign="top" rowsep="0" colsep="0" align="justify"><para role="text" /></entry></row></tbody></tgroup></informaltable><para role="text"><emphasis>n</emphasis> steht für die Anzahl der darunter stehenden Packobjekte. Die Beiwerte <emphasis>a11</emphasis>, <emphasis>a12</emphasis> etc. werden aus der Position des betrachteten Packobjektes und der darunter stehenden Packobjekte im Programm ermittelt. <emphasis>f1</emphasis>, <emphasis>f2</emphasis>,..., <emphasis>fn</emphasis> sind die Kraftanteile an den Packobjekten und damit die zu bestimmenden Parameter. Die Lösung dieses Liniengleichungssystems kann über das Gauss-Seidel-Verfahren <link linkend="WIKIPEDIA2005">[WIKPEDIA2005]</link> im Rechner ermittelt werden. </para><para role="text">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.</para><para role="text">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.</para><para role="text" /></section><section><title><phrase role="GEN_upcast-HEADINGNUMBER">3.3.	</phrase>Anordnung der Packobjekte im Packraum</title><para role="text">Für die Anordnung der Packobjekte auf der Palette werden einige grundlegende Strategien und Prioritäten ausgearbeitet. Diese Strategien sind im Optimierungsprogramm umgesetzt worden.</para><para role="text">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.</para><para role="Abbildung"><mediaobject><imageobject><imagedata width="130.54mm" depth="84.32mm" fileref="dippArticle-21.png" format="PNG" srccredit="embed" /></imageobject><caption><para role="caption">Abbildung <phrase role="GEN_SEQ">10</phrase>: Bildung von Block 1 und 2 auf der hinteren Seite der Palette</para></caption></mediaobject></para><para role="text">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). </para><para role="text">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. </para><para role="Abbildung">Im Packraum für den Block 4 werden ebenfalls Packobjekte erfasst, die eine ähnliche Höhe aufweisen (siehe das rechte Bild in Abb. 11). </para><para role="Abbildung"><mediaobject><imageobject><imagedata width="159.04mm" depth="40.24mm" fileref="dippArticle-22.png" format="PNG" srccredit="embed" /></imageobject><caption><para role="caption">Abbildung <phrase role="GEN_SEQ">11</phrase>: Anordnung der Packobjekte in Block 3 und 4 sowie die Restrume nach der Anordnung</para></caption></mediaobject></para><para role="text">Die Packhöhe der Blöcke kann übrigens unterschiedlich sein.</para><para role="text">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. </para><para role="text">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.</para><para role="text">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.</para><para role="text">Dieser Prozess wird solange durchgeführt, bis entweder </para><itemizedlist mark="disc" spacing="normal"><listitem><para>alle Packobjekte auf der Palette angeordnet werden,</para></listitem><listitem><para>das maximale Gewicht auf der Palette erreicht wird,</para></listitem><listitem><para>die Tragfähigkeit eines Packobjektes im unteren Bereich ausgeschöpft wird oder</para></listitem><listitem><para>kein Packobjekt in keinem der Resträume mehr passt.</para></listitem></itemizedlist><para role="text">Im Anschluss wird die gebildete Ladeeinheit bewertet (siehe „Bewertung und Selektion eines Packobjektes“) und in der Lösungsliste aufgenommen, wenn sie akzeptabel ist.</para><para role="text">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. </para><para role="Abbildung" /><para role="Abbildung"><mediaobject><imageobject><imagedata width="158.76mm" depth="41.91mm" fileref="dippArticle-23.png" format="PNG" srccredit="embed" /></imageobject><caption><para role="caption">Abbildung <phrase role="GEN_SEQ">12</phrase>: Bildung von ganzen Lagen und großen Blöcken (Beispiel)</para></caption></mediaobject></para><para role="text">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.</para></section></section><section><title><phrase role="GEN_upcast-HEADINGNUMBER">4.	</phrase>Realisierung</title><para role="text">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.</para><para role="text">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.</para><para role="text">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. </para><para role="Abbildung"><mediaobject><imageobject><imagedata width="158.76mm" depth="30.48mm" fileref="dippArticle-24.png" format="PNG" srccredit="embed" /></imageobject><caption><para role="caption">Abbildung <phrase role="GEN_SEQ">13</phrase>: 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.</para></caption></mediaobject></para><para role="text">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.</para><para /><para role="heading">Literatur</para><informaltable frame="none"><tgroup cols="2"><colspec colname="col1" colwidth="120.4pt" colnum="1" /><colspec colname="col2" colwidth="349.1pt" colnum="2" /><tbody><row><entry colname="col1" valign="top" rowsep="0" colsep="0" align="left"><para role="litID"><anchor id="Bortfeld1999" />[Bortfeldt1999]</para></entry><entry colname="col2" valign="top" rowsep="0" colsep="0" align="left"><para role="litText">Bortfeldt, A.: Zwei Heuristiken für Strip-Packing-Probleme. IN. Diskussionsbeiträge des Fachbereichs Wirtschaftswissenschaft der Fernuniversität Hagen, Nr. 266, April 1999</para></entry></row><row><entry colname="col1" valign="top" rowsep="0" colsep="0" align="left"><para role="litID"><anchor id="Davies1999" />[Davies1999]</para></entry><entry colname="col2" valign="top" rowsep="0" colsep="0" align="left"><para role="litText">Davies, A. P.; Bischoff, E. E.:Weight Distribution Considerations in Container Loading. IN: European Journal of Operational Research 114, 1999, S. 509-527</para></entry></row><row><entry colname="col1" valign="top" rowsep="0" colsep="0" align="left"><para role="litID"><anchor id="Strommer1992" />[Strommer1992]</para></entry><entry colname="col2" valign="top" rowsep="0" colsep="0" align="left"><para role="litText">Strommer W. M.: Verfahren zum automatischen Palettieren von quaderförmigen Packstücken im beliebigen Sortenmix. Berlin, Heidelberg: Springer1992</para></entry></row><row><entry colname="col1" valign="top" rowsep="0" colsep="0" align="left"><para role="litID"><anchor id="WIKIPEDIA2005" />[WIKPEDIA2005]</para></entry><entry colname="col2" valign="top" rowsep="0" colsep="0" align="left"><para role="litText"><ulink url="http://de.wikipedia.org/wiki/Gauss-Seidel-Verfahren"><phrase role="Hyperlink">http://de.wikipedia.org/wiki/Gauss-Seidel-Verfahren</phrase></ulink></para></entry></row></tbody></tgroup></informaltable><para role="text" /></section></article>