Fast jeder Autofahrer kennt das Problem, so viel Ladung wie möglich in einen vorgegebenen Kofferraum zu bekommen. Diese Aufgabe stellt nichts anderes als ein Packproblem dar, welches am häufigsten im dreidimensionalen Fall auftritt. Da jedoch überwiegend beladungstechnisch und aufgrund der Beschaffenheit der Packstücke nur eine einzige senkrechte Richtung möglich ist, wird in den meisten Fällen nur das zweidimensionale Packproblem betrachtet um die Anzahl der Packstücke pro Lage zu maximieren . Solche sogenannten Palettenbeladungsprobleme sind die am häufigsten betrachteten Probleme der betriebswirtschaftlichen Logistik, da hier große Kosteneinsparungen mit relativ geringem Aufwand möglich sind (Logistikkosten betragen im Durchschnitt europäischer Unternehmen immerhin 10% des Umsatzes ). So erwähnt Nelißen, dass bei den Pfanni-Werken durch eine Optimierung der Palettenbeladung eine jährliche Kostenreduzierung um mehr als eine Million DM möglich war .
Sehr häufig betrachtete Sachverhalte sind das Beladen von Frachtcontainern und Lastwagen sowie zweidimensionale Zuschnittprobleme. Doch auch Probleme aus anderen Bereichen werden in der Literatur häufig als Packprobleme dargestellt, u.a. das Füllen von Flüssigkeiten in verschiedene Tanks, Kapitalanlageprobleme, die Einteilung von Werbeblöcken im Fernsehen und sogar Schedulingprobleme.
Wie man sieht, verdienen Packprobleme besondere Aufmerksamkeit, doch schon das eindimensionale Problem ist NP-schwer. Daher ist es nicht möglich, polynomielle Algorithmen zu finden, die exakte Lösungen liefern. Folglich werden in der Realität überwiegend Lösungsheuristiken verwendet.
Die vorliegende Arbeit beschreibt die Wichtigkeit von oberen Schranken für die Lösung von zweidimensionalen homogenen Palettenbeladungsproblemen und beschreibt die bekanntesten Obergrenzen näher. Die folgenden zwei Kapitel dienen dabei der Begriffseinführung und Motivation der Suche nach den oberen Schranken, während in Kapitel 4-7 die verschiedenen Grenzen näher erläutert werden, von elementaren Verfahren bis hin zur Kombination von mehreren Methoden. In Kapitel 8 wird versucht, ein Fazit zu ziehen um zusammenfassend darzulegen, welche Verfahren dominant sind bzw. welches Vorgehen bei der Suche nach bestmöglichen oberen Schranken empfehlenswert ist.
Inhaltsverzeichnis
1 Einleitung
2 Das zweidimensionale homogene Palettenbeladungsproblem
3 Wichtigkeit von oberen Schranken
4 Elementare Verfahren
4.1 Flächenbetrachtung
4.1.1 Verfahren von Dowsland
4.1.2 Verfahren von Exeler und Keber
4.2 Verfahren von Barnes zur Bestimmung der nicht nutzbaren Fläche
4.2.1 Verfahren von Barnett und Kynch
4.2.2 Verfahren von Barnes
4.3 LP-Verfahren von Isermann
4.4 Sukzessive Verkleinerung des Packstücks nach Keber
4.5 Die Naujoks-Schranke
4.6 Vergleich der elementaren Verfahren
5 Dekomposition
6 Betrachtung identischer Strukturen
6.1 Verfahren von Exeler
6.2 Verfahren von Isermann
6.3 Bedeutung des Verhältnisses zwischen den Packstückseiten
7 Kombination der Verfahren
8 Zusammenfassung
Zielsetzung & Themen
Das Hauptziel dieser Seminararbeit ist die Darstellung und Analyse verschiedener mathematischer Verfahren zur Ermittlung oberer Schranken für zweidimensionale homogene Palettenbeladungsprobleme. Dabei wird untersucht, wie durch scharfe Obergrenzen die Optimalität gefundener Lösungsheuristiken nachgewiesen oder der Suchraum für exakte Algorithmen effizient eingegrenzt werden kann.
- Grundlagen des zweidimensionalen Packproblems
- Vergleich elementarer Verfahren (Flächenbetrachtung, Barnes, Isermann, Keber)
- Methoden der Problemdekomposition und Strukturanalyse
- Kombination von Verfahren zur Optimierung der Schrankengüte
- Analyse von Fallbeispielen und Testdaten
Auszug aus dem Buch
3 Wichtigkeit von oberen Schranken
Es gibt zwar effiziente Lösungsheuristiken für das homogene Palettenbeladungsproblem, mit denen meistens schnell eine gute Lösung berechnet werden kann, aber es fehlt dann der Nachweis, dass diese gefundene Lösung optimal ist. Hierbei spielen dann die oberen Schranken eine sehr große Rolle, denn eine scharfe Obergrenze kann zeigen, dass keine bessere Lösung existiert.
Der Nachweis der Optimalität einer gefundenen Lösung kann aber auch durch ein exaktes Verfahren erfolgen. Hierbei werden die oberen Schranken als Abbruchkriterium verwendet, z.B. beim Branch & Bound – Verfahren. Wie man schnell sieht, ist es sinnvoll, wenn man versucht eine möglichst gute Obergrenze für das homogene Palettenbeladungsproblem zu finden um den Lösungsaufwand der Heuristiken (bzw. der exakten Verfahren) zu minimieren. Einige dieser Schranken werden im Folgenden näher erläutert.
Zusammenfassung der Kapitel
1 Einleitung: Die Einleitung verdeutlicht die wirtschaftliche Relevanz von Packproblemen in der Logistik und motiviert die Notwendigkeit mathematischer Obergrenzen zur Validierung von Heuristiken.
2 Das zweidimensionale homogene Palettenbeladungsproblem: In diesem Kapitel werden die mathematischen Definitionen für Paletten, Packstücke und orthogonale Anordnungen sowie der Begriff der effizienten Überdeckung eingeführt.
3 Wichtigkeit von oberen Schranken: Es wird dargelegt, dass obere Schranken entscheidend sind, um den Nachweis der Optimalität zu führen und den Rechenaufwand bei exakten Lösungsverfahren zu reduzieren.
4 Elementare Verfahren: Dieses Kapitel vergleicht verschiedene Ansätze, von der einfachen Flächenbetrachtung bis hin zu komplexen Verfahren von Isermann und Barnes, um Obergrenzen für das Problem zu bestimmen.
5 Dekomposition: Die Dekomposition beschreibt einen Ansatz, bei dem das Ausgangsproblem in kleinere, leichter lösbare Subprobleme aufgespalten wird.
6 Betrachtung identischer Strukturen: Hier wird ausgenutzt, dass Probleme mit identischer Struktur gleiche optimale Lösungen besitzen, um durch Transformationen oder Verhältnisanpassungen bessere Schranken zu finden.
7 Kombination der Verfahren: Dieses Kapitel zeigt, dass durch die gezielte Verknüpfung mehrerer Ansätze die Güte der oberen Schranke signifikant gesteigert werden kann.
8 Zusammenfassung: Die Arbeit schließt mit einer Bilanz, die hervorhebt, dass sich die Verfahren ergänzen und ihre Kombination die effizienteste Methode zur Bestimmung scharfer Obergrenzen darstellt.
Schlüsselwörter
Palettenbeladungsproblem, Operations Research, Packproblem, obere Schranke, Optimierung, Heuristik, Dekomposition, Flächenbetrachtung, Isermann-Verfahren, orthogonale Anordnung, Effizienz, Logistik, mathematische Modellierung, Branch & Bound, Verschnitt
Häufig gestellte Fragen
Worum geht es in der Arbeit grundsätzlich?
Die Arbeit behandelt die mathematische Optimierung beim Beladen von Paletten mit identischen Packstücken und fokussiert sich dabei auf Methoden zur Berechnung oberer Schranken.
Was sind die zentralen Themenfelder?
Die zentralen Themen sind die theoretische Fundierung von Packproblemen, die Analyse verschiedener Schrankenberechnungsverfahren sowie deren Anwendung und Vergleich.
Was ist das primäre Ziel der Arbeit?
Das Ziel ist es, verschiedene Ansätze zur Bestimmung von Obergrenzen zu vergleichen, um herauszufinden, welches Vorgehen am besten geeignet ist, um die Optimalität von Lösungen bei Packproblemen zu belegen.
Welche wissenschaftlichen Methoden werden verwendet?
Es werden mathematische Modellierungen wie Lineare Programmierung (LP), strukturelle Problemdekomposition und Vergleichsanalysen von Heuristiken verwendet.
Was wird im Hauptteil behandelt?
Der Hauptteil gliedert sich in die Vorstellung elementarer Verfahren, die Dekomposition von Problemen, die Ausnutzung identischer Strukturen und die Kombination dieser Methoden.
Welche Schlüsselwörter charakterisieren die Arbeit?
Wichtige Begriffe sind Palettenbeladungsproblem, orthogonale Anordnung, obere Schranke, Dekomposition und lineare Optimierung.
Was genau ist ein "effizientes Problem"?
Ein Problem wird als effizient bezeichnet, wenn die Menge aller Überdeckungen, die für eine bestimmte Grundfläche definiert sind, nur solche Kombinationen umfasst, bei denen die Packstückanordnungen die Fläche optimal ausnutzen.
Warum ist das Verfahren von Dowsland oft nicht ausreichend?
Das Verfahren von Dowsland basiert auf einer einfachen Flächenbetrachtung, welche die strukturellen Einschränkungen einer orthogonalen Packung nicht berücksichtigt und daher oft zu grobe (zu hohe) Schranken liefert.
Welchen Vorteil bietet die Kombination der Verfahren?
Keines der genannten Verfahren dominiert alle anderen in jeder Situation. Die Kombination erlaubt es, die Stärken verschiedener Ansätze zu nutzen und so in über 95% der Testfälle die exakte obere Schranke zu ermitteln.
- Quote paper
- Matthias Lange (Author), 2005, Obere Schranken für das homogene Palettenbeladungsproblem, Munich, GRIN Verlag, https://www.grin.com/document/82494
