Combinatorial approaches for the trunk packing problem

Abstract

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.