ALCOMFT-TR-03-113

Friedrich Eisenbrand, Stefan Funke, Joachim Reichel and Elmar Schömer
Packing a Trunk
MPI. Work packages 4 and 5. November 2003.

Abstract: We report on a project with a German car manufacturer. The task is to compute (approximate) solutions to a specific large-scale packing problem. Given a polyhedral model of a car trunk, the aim is to pack as many identical boxes of size 4 x 2 x 1 units as possible into the interior of the trunk. This measure is important for car manufacturers, because it is a standard in the European Union.

\noindent First, we prove that a natural formal variant of this problem is NP-complete. Further, we use a combination of integer linear programming techniques and heuristics that exploit the geometric structure to attack this problem. Our experiments show that for all considered instances, we can get very close to the optimal solution in reasonable time.

Postscript file: ALCOMFT-TR-03-113.ps.gz (357 kb).