Packing a trunk - now with a Twist!

are faced with the challenge of placing a maximum number of
uniform rigid rectangular boxes in the interior of a car
trunk. The problem is of practical importance due to a
European industry norm which requires car manufacturers
to state the trunk volume according to this measure.

No really satisfactory automated solution for this problem has been
known in the past. In spite of its NP hardness, combinatorial
optimization techniques, which consider only grid-aligned placements,
produce solutions which are very close to the one achievable by a
human expert in several hours of tedious work. The remaining gap is
mostly due to the constraints imposed by the chosen grid.

In this paper we present a new approach which combines the grid-based
combinatorial method with \emph{Simulated Annealing} on a continuous
model. This allows us to explore arbitrary orientations and placements
of boxes, hence closing the gap even further, and -- in some cases --
even surpass the manual expert solution.

The implemented software system allows our industrial partner to
incorporate the trunk volume in a very early stage of the car design
process without relying on a repeated and cumbersome manual evaluation
of the volume.