Volumenpackungen nach SAE J1100

Abstract

We present new algorithms to approximate the discrete volume of a polyhedral geometry using boxes defined by the US standard SAE J1100. This problem is NP-hard and has its main application in the car design process. The algorithms produce maximum weighted independent sets on a so-called conflict graph for a discretisation of the geometry. We present a framework to eliminate a large portion of the vertices of a graph without affecting the quality of the optimal solution. Using this framework we are also able to define the conflict graph without the use of a discretisation. For the solution of the maximum weighted independent set problem we designed an enumeration scheme which uses the restrictions of the SAE J1100 standard for an efficient upper bound computation. We evaluate the packing algorithms according to the solution quality compared to manually derived results. Finally, we compare our enumeration scheme to several other exact algorithms in terms of their runtime. Grid-based packings either tend to be not tight or have intersections between boxes. We therefore present an algorithm which can compute box packings with arbitrary placements and fixed orientations. In this algorithm we make use of approximate Minkowski Sums, computed by uniting many axis-oriented equal boxes. We developed an algorithm which computes the union of equal axis-oriented boxes efficiently. This algorithm also maintains the Minkowski Sums throughout the packing process. We also extend these algorithms for packing arbitrary objects in fixed orientations.

In dieser Arbeit werden neue Packalgorithmen für die US-Norm SAE J1100 vorgestellt. Das diskrete Packproblem ist NP-schwer und hat hier einen direkten Bezug zur Fahrzeugentwicklung. Die Algorithmen sind exakte Verfahren für das Maximum Weighted Independent Set Problem (MWIS). Wir beschreiben eine Methode, mit der ein großer Anteil der Knoten eines Graphen entfernt werden kann, ohne dass davon die optimale Lösung des MWIS-Problems beeinträchtigt wird. Mit Hilfe dieses Verfahrens wird auch ein kontinuierlicher Graph für das Packproblem definiert. Das MWIS-Problem selbst wird mit Hilfe eines Aufzählungsalgorithmus exakt gelöst. Dieser Algorithmus nutzt die Vorgaben der US-Norm SAE J1100 zur Berechnung guter oberer Schranken. Wir vergleichen die erzielten Packungen mit denen manueller Packprozesse. Weiterhin untersuchen wir die verwendeten Aufzählungsschemata hinsichtlich ihrer Laufzeit und vergleichen sie mit weiteren Algorithmen aus der Literatur. Da bei einer gitterbasierten Packung Lücken auftreten können oder Quader sich über-schneiden, beschreiben wir einen weiteren Algorithmus, der Quaderpackungen mit beliebigen Platzierungen erzeugen kann. Dieser Packalgorithmus verwendet approximierte Minkowskisummen, die die Vereinigung vieler gleich orientierter und gleich großer Quader darstellen. Hierfür wird ebenfalls ein neuer effizienter Algorithmus vorgestellt, der auch die Verwaltung der Minkowskisummen während des Packens übernimmt. Diese Algorithmen werden erweitert, so dass beliebige Objekte gepackt werden können.