Combinatorial approaches for the trunk packing problem [Elektronische Ressource] / von Joachim Reichel

Combinatorial Approachesfor theTrunk Packing ProblemDissertationzur Erlangung des Grades desDoktors der Ingenieurwissenschaftender Naturwissenschaftlich-Technischen Fakultätender Universität des SaarlandesvonJoachim ReichelSaarbrücken2006Tag des Kolloquiums: 10. Juli 2006Dekan der Naturwissenschaftlich-Technischen Fakultät I:Prof. Dr.-Ing. Thorsten HerfetVorsitzender des Prüfungsausschusses:Prof. Dr.-Ing. Gerhard WeikumGutachter:Prof. Dr. Elmar SchömerProf. Dr. Kurt MehlhornPromovierter akademischer Mitarbeiter:Dr. Stefan FunkeAbstractIn this thesis we consider a three-dimensional packing problem arising inindustry. The task is to pack a maximum number of rigid boxes with sidelength ratios of 4 : 2 : 1 into an irregularly shaped container. Motivated bythe structure of manually constructed packings so far, we pursue a discreteapproach. We discretize the shape of the container as well as the set ofpossible box placements. This discrete packing problem can be reduced to amaximum stable set problem.First we formulate the problem as an integer linear program, which ad-mittedly can only be solved to optimality within reasonable runtime for verysmall instances. Therefore, we present several heuristics based, for example,on the linear programming relaxation or on local search. Other heuristicsgenerate tight packings for the core of the container, thereby reducing theproblem to a set of smaller subproblems.