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.