Packing a Trunk

Friedrich Eisenbrand, Stefan Funke, Joachim Reichel, Elmar Schoemer

We report on an ongoing project with a German car manufacturer. The task is to practically 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 \times 2 \times 1$ units as possible into the interior of the trunk. This measure is important for car manufacturers because it is the standard in the European Union. Our experiments show that for all considered instances we can get very close to the optimal solution in reasonable time.

Proc. 11th Annual European Symposium on Algorithms (ESA) 2003, Budapest (Springer LNCS)