Bitte benutzen Sie diese Referenz, um auf diese Ressource zu verweisen: doi:10.22028/D291-25883
Titel: Combinatorial approaches for the trunk packing problem
Verfasser: Reichel, Joachim
Sprache: Englisch
Erscheinungsjahr: 2006
SWD-Schlagwörter: Packungsproblem
Dimension 3
Heuristik
Angewandte Mathematik
Freie Schlagwörter: three-dimensional packing problem
heuristic
DDC-Sachgruppe: 004 Informatik
Dokumentart : Dissertation
Kurzfassung: In this thesis we consider a three-dimensional packing problem arising in industry. The task is to pack a maximum number of rigid boxes with side length ratios of 4 : 2 : 1 into an irregularly shaped container. Motivated by the structure of manually constructed packings so far, we pursue a discrete approach. We discretize the shape of the container as well as the set of possible box placements. This discrete packing problem can be reduced to a maximum stable set problem. First we formulate the problem as an integer linear program, which admittedly can only be solved to optimality within reasonable runtime for very small instances. Therefore, we present several heuristics based, for example, on the linear programming relaxation or on local search. Other heuristics generate tight packings for the core of the container, thereby reducing the problem to a set of smaller subproblems. We compare all presented algorithms on real data sets. We achieve very good results for the majority of instances and for some instances we even surpass the manually constructed solutions.
In dieser Arbeit behandeln wir ein dreidimensionales Packungsproblem aus der Industrie. Die Aufgabe besteht darin, möglichst viele starre Quader mit einem Seitenverhältnis von 4 : 2 : 1 in einen unregelmäßig geformten Container zu packen. Motiviert durch die Struktur der bisher manuell erstellten Packungen verfolgen wir einen diskreten Lösungsansatz. Dazu diskretisieren wir sowohl die Form des Containers als auch die Platzierungsmöglichkeiten der Quader. Dieses diskrete Packungsproblem lässt sich auf die Berechnung einer größtmöglichen unabhängigen Knotenmenge reduzieren. Wir formulieren das Problem zunächst als ganzzahliges lineares Programm, das allerdings nur für sehr kleine Instanzen mit angemessenem Rechenaufwand beweisbar optimal gelöst werden kann. Daher stellen wir verschiedene Heuristiken vor, die zum Beispiel auf einer Relaxierung des ganzzahligen linearen Programms oder lokaler Suche basieren. Andere Heuristiken generieren zunächst dichte Packungen für den Kern des Containers und reduzieren so das Problem auf eine Reihe kleinerer Teilprobleme. Wir vergleichen alle vorgestellten Algorithmen an Hand realer Datensätze. In der Mehrzahl der Fälle erreichen wir sehr gute Resultate, bei einigen Instanzen übertreffen wir sogar die manuell erstellten Packungen.
Link zu diesem Datensatz: urn:nbn:de:bsz:291-scidok-12666
hdl:20.500.11880/25939
http://dx.doi.org/10.22028/D291-25883
Erstgutachter: Schömer, Elmar
Tag der mündlichen Prüfung: 10-Jul-2006
SciDok-Publikation: 30-Aug-2007
Fakultät: Fakultät 6 - Naturwissenschaftlich-Technische Fakultät I
Fachrichtung: MI - Informatik
Fakultät / Institution:MI - Fakultät für Mathematik und Informatik

Dateien zu dieser Ressource:
Datei Beschreibung GrößeFormat 
Dissertation_5227_Reic_Joac_2006.pdf14,55 MBAdobe PDFÖffnen/Anzeigen


Alle Ressourcen in diesem Repository sind urheberrechtlich geschützt.