Volumenpackungen nach SAE J1100 [Elektronische Ressource] / Tobias Baumann

Sujets

• Mathematics

Informations

• Publié par: johannes_gutenberg-universitat_mainz
• Publié le: 01 janvier 2008
• Nombre de lectures: 70
• Langue: Deutsch
• Poids de l'ouvrage: 6 Mo

Extrait

Volumenpackungen nach
SAE J1100
Dissertation
zur Erlangung des Grades
\Doktor
der Naturwissenschaften"
am Fachbereich 08 { Physik, Mathematik und Informatik
der Johannes Gutenberg-Universit at
in Mainz
Dipl.-Inf. Tobias Baumann
geb. am 25.10.1980 in Schlema
Mainz, im August 2008Tag der mundlic hen Prufung: 27. November 2008
2Zusammenfassung
In dieser Arbeit werden neue Packalgorithmen fur die US-Norm SAE J1100 vorgestellt.
Das diskrete Packproblem istNP-schwer und hat hier einen direkten Bezug zur Fahrzeug-
entwicklung. Die Algorithmen sind exakte Verfahren fur das Maximum Weighted Inde-
pendent 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 osung
des MWIS-Problems beeintr achtigt wird. Mit Hilfe dieses Verfahrens wird auch ein
kontinuierlicher Graph fur das Packproblem de niert.
Das MWIS-Problem selbst wird mit Hilfe eines Aufzahlungsalgorithmus exakt gel ost.
Dieser Algorithmus nutzt die Vorgaben der US-Norm SAE J1100 zur Berechnung guter
oberer Schranken. Wir vergleichen die erzielten Packungen mit denen manueller Pack-
prozesse. Weiterhin untersuchen wir die verwendeten Aufz ahlungsschemata hinsichtlich
ihrer Laufzeit und vergleichen sie mit weiteren Algorithmen aus der Literatur.
Da bei einer gitterbasierten Packung Luc ken auftreten k onnen oder Quader sich uber-
schneiden, beschreiben wir einen weiteren Algorithmus, der Quaderpackungen mit be-
liebigen Platzierungen erzeugen kann. Dieser Packalgorithmus verwendet approximierte
Minkowskisummen, die die Vereinigung vieler gleich orientierter und gleich gro er Qua-
der darstellen. Hierfur wird ebenfalls ein neuer e zienter Algorithmus vorgestellt, der
auch die Verwaltung der Minkowskisummen w ahrend des Packens ub ernimmt.
Diese Algorithmen werden erweitert, so dass beliebige Objekte gepackt werden k onnen.
Abstract
We present new algorithms to approximate the discrete volume of a polyhedral geometry
using boxes de ned 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 con ict graph for a discretisation of the geometry. We
present a framework to eliminate a large portion of the vertices of a graph without
a ecting the quality of the optimal solution. Using this framework we are also able to
de ne the con ict 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 e cient
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 place-
ments and xed 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 equalted boxes e ciently. This algorithm also
maintains the Minkowski Sums throughout the packing process.
We also extend these algorithms for packing arbitrary objects in xed orientations.
34Ausfuhrliche Zusammenfassung
Bei der Kaufentscheidung fur ein neues Auto spielt neben anderen Dingen die Ko er-
raumkapazit at eine gro e Rolle. Es ist zwar m oglich, das kontinuierliche Ko erraumvol-
umen mit Hilfe von CAD-Systemen einfach zu bestimmen. Allerdings m ochte der Kunde
normalerweise gr o ere Objekte, so zum Beispiel Ko er oder Getr ankekisten, in den Kof-
ferraum laden. Um diesen Sachverhalt abzubilden, gibt es zwei verschiedene Normen,
das Ko erraumvolumen zu bestimmen: In Europa ist die DIN 70020 [27] verbreitet, nach
der das Volumen mit Hilfe von uniformen Quadern der Gr o e 200 100 50 mm bestimmt
wird. In den USA hingegen gibt es die Norm SAE J1100 [45]. Diese Norm verlangt,
dass Quader verschiedener Gr o e in einer bestimmten Reihenfolge mit fest vorgegebe-
nen Maximalvorkommen in den Ko erraum geladen werden mussen. Im Gegensatz zum
kontinuierlichen Volumen ist das diskrete Packproblem ein NP-schweres Problem.
Bisher hatten Autohersteller nur die M oglichkeit, CAD-Systeme fur die Berechnung
von Ko erraumpackungen zu nutzen. Allerdings sind diese Methoden sehr zeitraubend
und ine zient, da die Packungen komplett manuell hergestellt werden mussten. Es
bestand auch kaum die M oglichkeit, noch in den Entwicklungsprozess des Fahrzeugs
einzugreifen, um etwa Regionen mit gro en Verschnitt zu modi zieren. Mit Hilfe von
e zienten Algorithmen fur dieses Packproblem ist es nun m oglich, das Ko erraumvolu-
men fruhzeitig in der Entwicklung eines Fahrzeugs zu bestimmen und mit entsprechenden
Modi kationen besser auf die Bedurfnisse der Kunden abzustimmen.
In Kooperation mit einem gro en deutschen Automobilhersteller haben wir ein Soft-
warepaket entwickelt, mit dem dreidimensionale Packprobleme, speziell fur Quader, ef-
zient gel ost werden k onnen. Die Software kann CAD-Daten verarbeiten und berechnet
Packungen nach den oben beschriebenen Normen. Zus atzlich gibt es die M oglichkeit,
beliebige Geometrien in einen Ko erraum zu packen, zum Beispiel Getr ankekisten oder
Ko er.
Diese Arbeit befasst sich mit neuen Packalgorithmen fur die US-Norm SAE J1100. Die
Algorithmen basieren auf Graphen und berechnen unabh angige Mengen mit maximalem
Gewicht (MWIS { Maximum Weight Independent Set). Der so genannte Kon iktgraph
kann aus einer Gitter-Diskretisierung des Ko erraums gewonnen werden [48]. Da die
Graphen fur das gewichtete Packungsproblem sehr gro werden k onnen, beschreiben wir
ein Verfahren, mit dem ein gro er Anteil der Knoten eines Graphen entfernt werden kann,
ohne das Ergebnis der optimalen L osung zu beein ussen. Mit Hilfe dieses Verfahrens
sind wir ebenfalls in der Lage, einen Kon iktgraphen ohne die Verwendung eines Gitters
zu erzeugen.
Zur L osung des MWIS-Problems verwenden wir einen Aufz ahlungsalgorithmus, der
die Vorgaben der US-Norm ausnutzt, um eine gute obere Schranke zu berechnen. Wir
vergleichen die erzielten Packungen mit denen manueller Packprozesse. Weiterhin un-
tersuchen wir die verwendeten Aufz ahlungsschemata hinsichtlich ihrer Laufzeit und ver-
gleichen sie mit anderen exakten Algorithmen aus der Literatur.
Weiterhin beschreiben wir einen Packalgorithmus mit beliebigen Platzierungen und
festen Orientierungen. Innerhalb der US-Norm ist dies ein enormer Fortschritt, da
gitterbasierte Packungen entweder Luc ken aufweisen oder sich Quader ub erschneiden
5
k onnen. Mit beliebigen Platzierungen der Quader wird dies umgangen, und bessere
Packungen sind m oglich. Dieser Algorithmus verwendet approximierte Minkowskisum-
men, die die Vereinigung vieler gleich orientierter und gleich gro er Quader darstellen.
Hierzu beschreiben wir ebenfalls einen neuen Algorithmus, der zus atzlich die e ziente
Verwaltung der Minkowskisummen w ahrend des Packens ub ernimmt.
Extended Abstract
The decision for a new car is based amongst others on the capacity of its luggage com-
partment. Using modern CAD systems, it is only possible to compute the continuous
volume. Usually the customer wants to pack some large objects, such as suitcases or bot-
tle crates, into the trunk compartment. For this issue there are two dierent standards
de ned to compute the volume of a trunk: First, the German standard DIN 70020 [27],
which is used throughout the European Union, uses small boxes of sizes 200 100 50 mm
and demands to pack as many boxes as possible into the trunk. The second standard,
SAE J1100 [45], which is used in the United States of America, requires several dierent
box types to be packed. In contrast to the continuous volume it is an NP-hard problem
to compute optimal packings with discrete objects.
Up to now, car manufacturers use CAD systems to compute trunk packings manually
with time-consuming and ine cient methods. As well, the trunk capacity is computed
very late during the car design process. If it is known earlier in the car design process,
one can use this knowledge to adapt the trunk in order to use wasted space for other
items such as electricity cables. In other places the trunk could be extended in order
to place some more items. This of course requires e cient algorithms to produce good
packings.
We developed a software package which can handle these three-dimensional packing
problems. This package can process CAD input data and computes packings according
to the standards mentioned above e ciently. As well, we integrated an algorithm to
pack arbitrary geometries into the trunk.
In this dissertation we present new algorithms to compute valid packings according to
the US standard SAE J1100. The are graph-based and produce maximum
weighted independent sets on a so-called con ict graph. This graph can be derived from
a grid discretisation [48] of the trunk space. We present a framework to eliminate a large
portion of the vertices of a graph without a ecting the quality of the optimal solution.
Using this framework we are also able to de ne the con ict graph without the use of a
d