Fully Automatic Trunk Packing with Free Placements

Ernst Althaus, Peter HachenbergerarXiv 2010 · arXiv

Abstract

Determining the cargo volume of a vehicle is a critical design task governed by international standards. Traditional manual methods are time-consuming, while automated grid-based approaches suffer from discretization errors or computational intractability. This paper presents a novel algorithm for fully automatic trunk packing using "free placements." By leveraging Minkowski sums and linear programming, the method achieves superior packing density in small cargo spaces compared to existing automated and manual techniques.

Introduction

The cargo volume of a car is a key specification for consumers and designers alike. Standards such as SAE J1100 define this volume by the number of standardized suitcases—ranging from large trunks to small "H-boxes"—that can be packed into the space. Historically, this process was a manual, multi-day endeavor.

Standardized suitcases and trunk models used in the SAE J1100 packing standard.

Previous automation attempts often relied on discretization, overlaying a 3D grid on the trunk. However, because suitcase dimensions do not share simple integer ratios, grid cells must be extremely small to avoid significant volume loss, leading to a "curse of dimensionality." This research proposes a grid-free approach that allows for continuous placement and orientation of cargo items within six axis-aligned directions.

Methodology

The core of the proposed algorithm is the transition from discrete search spaces to continuous "free placements" guided by computational geometry.

Geometric Representation and Minkowski Sums

To determine where a box can be placed without intersecting the trunk walls, the algorithm calculates a "feasible area" for the center of each box type. This is achieved using Minkowski sums, a geometric operation that effectively "thickens" the trunk boundary by the dimensions of the suitcase.

Comparison between the original trunk mesh and the derived feasible area for a specific box type.

Because real-world trunk meshes are highly complex (often exceeding 40,000 triangles), the resulting feasible areas are represented using 3D Nef polyhedra. To maintain computational efficiency, a two-step simplification process reduces the number of linear inequalities defining these spaces, making the problem solvable for modern LP solvers.

Combinatorial Optimization

Rather than searching coordinates directly, the algorithm explores "packing patterns"—classes of arrangements defined by the relative positions of boxes (e.g., "Box A is to the left of Box B"). For each candidate pattern, the CPLEX Linear Programming (LP) solver determines if a valid set of coordinates exists that satisfies both the trunk boundary constraints and non-overlap requirements between boxes.

Experimental Evaluation

The algorithm was tested on three production vehicle trunk models: SMALL (99,352 triangles), MEDIUM (66,743 triangles), and LARGE (42,182 triangles).

In the SMALL trunk category, the algorithm demonstrated clear superiority, achieving a volume of 163.9 dm³. This outperformed both expert manual packing (151.1 dm³) and state-of-the-art physics-based simulations (159.9 dm³).

However, as the trunk size increases, the search space for packing patterns grows exponentially. In the LARGE trunk model, the algorithm struggled to explore the full search tree within a 24-hour time limit, making it less effective than physics-based methods in those specific scenarios. While computationally intensive, the task is highly parallelizable; utilizing six machines can reduce the time to reach a high-quality solution to approximately 13 hours.

Conclusion

This research demonstrates that a geometry-driven, grid-free approach to trunk packing can surpass human performance in constrained spaces. By moving away from discretization, the algorithm avoids the accuracy trade-offs inherent in grid-based methods. Future work will focus on improving search heuristics to handle larger volumes more efficiently and refining pre-processing to handle imperfect CAD meshes with surface gaps.

Summary updated

BibTeX
@misc{althaus2010fully,
  author = {Ernst Althaus and Peter Hachenberger},
  title = {{Fully Automatic Trunk Packing with Free Placements}},
  year = {2010},
  eprint = {1008.3773},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1008.3773},
}
Figure