Struktur und algorithmische Behandlung von praxisorientierten dreidimensionalen Packungsproblemen

Wottawa, Michael (1996) Struktur und algorithmische Behandlung von praxisorientierten dreidimensionalen Packungsproblemen. PhD thesis.

Abstract

Fast jedes Kind besitzt in seiner Spielzeugsammlung in irgendeiner Form einen Satz Bauklötze, mit dem es außer dem Bauen von unterschiedlichen Figuren auch noch eine weitere Fertigkeit erlernt: Das Packen der Bauklötze in eine für diese bereitstehende Kiste. Die dabei angewendeten 'Verfahren' wie Backtracking oder Sortieren nach der Größe sind uns somit von frühester Kindheit an vertraut, auch wenn wir sie nie als solche erkannt und benannt haben. Prinzipiell ist das zugrunde liegende mathematische Problem aber schon in seiner eindimensionalen Version NP-schwer und gehört somit zu den schwierigen Problemen. Sollen Computer zur Lösung eines dreidimensionalen Packungsproblems eingesetzt werden, so sind dazu Algorithmen notwendig, die die dem menschlichen Gehirn eigene Assoziationsfähigkeit durch geeignete Regeln bezüglich der Struktur der erzeugten Muster ersetzen. In der Praxis kommen Packungsprobleme vor allem im Logistikbereich vor. Neben den dort auftretenden dreidimensionalen Problemen des Beladens von Frachtcontainern, Lastwagen oder Kommissionierpaletten haben aber auch vornehmlich zweidimensionale Zuschnittprobleme der Stahl-, Holz- und Glasindustrie eine große Bedeutung. Darüberhinaus werden in der Literatur auch die folgenden Anwendungen als Packungsprobleme modelliert: Die Ausführung von Programmen auf mehreren gleichen Prozessoren (1D, siehe M. Hofri [Information and Control , 45 (1980)]), Die Ausführung von Programmen auf einem Prozessor mit fester Speicherkapazität (2D, nach H. Dyckhoff [European Journal of Operational Research , 44 (1990)]), Schneiden von Graphit-Blöcken für Anoden (3D, nach P.C. Gilmore and R.E. Gomory [Operations Research, 13 (1965)]), Einteilung der Werbeblöcke in Hörfunk und Fernsehen (1D), Das Füllen von Flüssigkeiten in unterschiedliche Tanks. In der Formulierung als Packungsproblem werden die Tanks in die jeweilige Flüssigkeitsmenge 'gepackt' (1D, siehe N. Christofides, A. Mingozzi und P. Toth [Combinatorial Optimisation, (1988)]), Die Plazierung von Werbung auf Zeitungsseiten (2D, nach J. Beasley [Operations Research, 33 (1985)]), Kapitalanlageprobleme (nach H. Dyckhoff [European Journal of Operational Research, 44 (1990)]). Eine bessere Packung ermöglicht dabei in allen diesen Bereichen große Kosteneinsparungen. Durch die zunehmende Verbreitung der Datenverarbeitung in der Auftragsabwicklung von Speditionen und Luftfracht-Gesellschaften haben diese inzwischen auch die notwendigen Informationen über das zu verschickende Frachtgut, so daß der Einsatz von EDV-gestützten Packungsverfahren auch technisch möglich wird. Ein- und zweidimensionale Packungsprobleme sind schon lange Gegenstand der Forschung und werden auch in einigen Bereichen der Industrie schon praktisch umgesetzt. Dagegen existieren für dreidimensionale Probleme erst sehr wenige Algorithmen, obwohl die praktischen Problemstellungen der Logistik in fast allen Fällen dreidimensional sind. In dieser Arbeit werden wir die wichtigste Variante der Packungsprobleme untersuchen, bei der sowohl die zu beladenden als auch die zu verladenden Objekte quaderförmig sind. Im ersten Kapitel geben wir zunächst einen Überblick über die in der Praxis und der Literatur behandelten Packungsprobleme und führen eine neue Klassifizierung für die in dieser Arbeit betrachteten orthogonalen Packungsprobleme ein, die sowohl der Vereinfachung der Notation dient, als auch eine effiziente Klassifizierung bestehender Algorithmen ermöglicht. Weiterhin werden die wichtigsten Heuristiken vorgestellt, für deren Lösungen Güteschranken bekannt sind. Im zweiten Kapitel werden mögliche Darstellungen von Packmustern diskutiert. Dabei wird besonderes Augenmerk auf die Datenstrukturen des Berührgraphen und des Sichtbarkeitsgraphen gelegt, da diese neben den notwendigen Informationen über die Plazierung der Kisten auch umfangreiche Informationen über die Nachbarschaftsstruktur jeder Kiste des Packmusters enthalten, und somit besonders geeignet für den praktischen Einsatz sind. Für die Berührgraphen können wir eine Charakterisierung aller Graphen angeben, für die es eine Darstellung als Packmuster gibt. Die beiden folgenden Kapitel behandeln zwei sehr einfach strukturierte Probleme, deren Komplexitätsstatus unbekannt ist. Dies ist zum einen das Packen möglichst vieler gleichgroßer Quadrate in ein einfach zusammenhängendes Polygon und zum anderen das Packen möglichst vieler gleichgroßer Rechtecke in ein größeres Rechteck ('Pallet Loading'). Wir beschreiben strukturelle und algorithmische Ansätze für diese beiden Probleme. Beim Packen von Polygonen kann die Struktur des Originalproblems erheblich reduziert werden. Beim Pallet-Loading-Problem können wir für drei Klassen von Probleminstanzen alle optimalen Packmuster angeben und haben somit erste Informationen über die Komplexität der Struktur der optimalen Packmuster gewonnen. Für die dreidimensionale Variante des Pallet Loadings entwickeln wir ein neues heuristisches Verfahren. Kapitel vier beschäftigt sich mit Verfahren zur Lösung von ein- und zweidimensionalen Problemen. Insbesondere wird eine Fallstudie zum Packen von Badewannen und Duschwannen vorgestellt, die für einen Industriepartner durchgeführt wurde, und die sich inzwischen im praktischen Einsatz befindet. Die letzten beiden Kapitel behandeln Verfahren zur Lösung von dreidimensionalen Packungsproblemen. In Kapitel sechs stellen wir mit dem Teilfolgen-Verfahren einen Algorithmus vor, der auf einem neuen Ansatz basiert, bei dem das Problem bezüglich zweier Dimensionen durch effiziente zweidimensionale Verfahren gepackt wird, während durch eine geschickte Auswahl der an diese übergebenen Kisten auch die dritte Dimension optimiert wird. Im siebten Kapitel wird die in Kapitel 2 vorgestellte Datenstruktur des Sichtbarkeitsgraphen benutzt, um einen effizienten Verbesserungsalgorithmus zu erstellen.


Actions:
Download: [img] Postscript - Published Version
Download (1MB) | Preview
Editorial actions: View Item View Item (Login required)
Deposit Information:
ZAIK Number: zpr97-311
Depositing User: Archive Admin
Date Deposited: 02 Apr 2001 00:00
Last Modified: 19 Dec 2011 09:46
URI: http://e-archive.informatik.uni-koeln.de/id/eprint/311