New car buying decisions more often than not factor in the capacity of the luggage compartment. Using modern CAD systems, it's only possible to compute continuous volume. However, customers typically like to pack a few bulky objects, such as suitcases or bottle crates, into the trunk compartment. For this issue there are two different standards used to compute usable trunk volume.
In Germany, and the rest of the EU, DIN 70020 is used. It utilizes small boxes sized 200 x 100 x 50 mm, and the requirement is to pack as many boxes as possible into the cargo space. In the US, SAE J1100 is used. This standard asks that boxes of several types and sizes are to be packed. In contrast to the continuous volume computation, this represents an NP-hard problem.
Until recently, car manufacturers used CAD systems to compute trunk space manually, which with time-consuming and inefficient. Trunk capacity is determined very late during the car design process. If it was known earlier in the car design process, this data could be used to adapt the design, and facilitate more efficient space utilization.
In this dissertation we present new algorithms to compute valid trunk dimension according to the US standard SAE J1100. We developed a software package, which can handle these three-dimensional problems. This software can process CAD input data and computes packings according to the standards mentioned above efficiently. As well, we integrated an algorithm topack arbitrary geometries into the trunk.
The algorithm is graph-based, and produces maximum weighted independent sets on a so-called conflict graph. This graph can be derived froma grid discretisation of the trunk space. We present a framework to eliminate a large portion of the vertices of a graph without affecting the quality of the optimal solution.