Combinatorial approaches for the trunk packing problem [Elektronische Ressource] / von Joachim Reichel

Sujets

• Mathematics

Informations

• Publié par: universitat_des_saarlandes
• Publié le: 01 janvier 2007
• Nombre de lectures: 7
• Langue: English
• Poids de l'ouvrage: 14 Mo

Extrait

Combinatorial Approaches
for the
Trunk Packing Problem
Dissertation
zur Erlangung des Grades des
Doktors der Ingenieurwissenschaften
der Naturwissenschaftlich-Technischen Fakultäten
der Universität des Saarlandes
von
Joachim Reichel
Saarbrücken
2006Tag des Kolloquiums: 10. Juli 2006
Dekan der Naturwissenschaftlich-Technischen Fakultät I:
Prof. Dr.-Ing. Thorsten Herfet
Vorsitzender des Prüfungsausschusses:
Prof. Dr.-Ing. Gerhard Weikum
Gutachter:
Prof. Dr. Elmar Schömer
Prof. Dr. Kurt Mehlhorn
Promovierter akademischer Mitarbeiter:
Dr. Stefan FunkeAbstract
In this thesis we consider a three-dimensional packing problem arising in
industry. The task is to pack a maximum number of rigid boxes with side
length ratios of 4 : 2 : 1 into an irregularly shaped container. Motivated by
the structure of manually constructed packings so far, we pursue a discrete
approach. We discretize the shape of the container as well as the set of
possible box placements. This discrete packing problem can be reduced to a
maximum stable set problem.
First we formulate the problem as an integer linear program, which ad-
mittedly can only be solved to optimality within reasonable runtime for very
small instances. Therefore, we present several heuristics based, for example,
on the linear programming relaxation or on local search. Other heuristics
generate tight packings for the core of the container, thereby reducing the
problem to a set of smaller subproblems.
We compare all presented algorithms on real data sets. We achieve very
good results for the majority of instances and for some instances we even
surpass the manually constructed solutions.
Zusammenfassung
In dieser Arbeit behandeln wir ein dreidimensionales Packungsproblem aus
der Industrie. Die Aufgabe besteht darin, möglichst viele starre Quader mit
einem Seitenverhältnis von 4 : 2 : 1 in einen unregelmäßig geformten Con-
tainer zu packen. Motiviert durch die Struktur der bisher manuell erstellten
Packungen verfolgen wir einen diskreten Lösungsansatz. Dazu diskretisieren
wir sowohl die Form des Containers als auch die Platzierungsmöglichkeiten
der Quader. Dieses diskrete Packungsproblem lässt sich auf die Berechnung
einer größtmöglichen unabhängigen Knotenmenge reduzieren.
Wir formulieren das Problem zunächst als ganzzahliges lineares Pro-
gramm, das allerdings nur für sehr kleine Instanzen mit angemessenem Re-
chenaufwand beweisbar optimal gelöst werden kann. Daher stellen wir ver-
schiedene Heuristiken vor, die zum Beispiel auf einer Relaxierung des ganz-
zahligen linearen Programms oder lokaler Suche basieren. Andere Heuristi-
ken generieren zunächst dichte Packungen für den Kern des Containers und
reduzieren so das Problem auf eine Reihe kleinerer Teilprobleme.
Wir vergleichen alle vorgestellten Algorithmen an Hand realer Datensät-
ze. In der Mehrzahl der Fälle erreichen wir sehr gute Resultate, bei einigen
Instanzen übertreffen wir sogar die manuell erstellten Packungen.Ausführliche Zusammenfassung
In der vorliegenden Arbeit behandeln wir ein dreidimensionales Packungs-
problem aus der Automobilindustrie. Auf dem europäischen Markt sind Au-
tomobilhersteller dazu verpflichtet, das Gepäckraumvolumen eines PKWs
entsprechend den Regelungen in der Norm DIN 70020 zu bestimmen und zu
veröffentlichen. Diese Norm schreibt vor, den Kofferraum mit starren Qua-
dern der Größe 200mm× 100mm× 50mm zu packen. Das Gepäckraum-
volumen des Kofferraums wird dann als das durch die Quader überdeckte
Volumen definiert. Das so ermittelte Gepäckraumvolumen ist ein wichtiges
Verkaufsargument;dementsprechendwirdvondenAutomobilherstellernviel
Aufwand betrieben, um einen möglichst hohen Wert zu erreichen.
DasZieldesdieserArbeitzuGrundeliegendenProjektesmiteineminter-
nationalen Automobilhersteller ist es, ein Softwarepaket zu entwickeln, um
das Gepäckraumvolumen eines PKWs in Übereinstimmung mit der Norm
DIN 70020 zu bestimmen. Die Anwendung soll abgesehen von einer Vorbe-
reitungphase keine Benutzerinteraktion erfordern und muss ohne Experten-
wissenzubedienensein.DieGütederberechnetenLösungensollvonmanuell
durchExpertenkonstruiertenPackungenumnichtmehralseinProzentbzw.
zehn Litern nach unten abweichen.
DieunregelmäßigeFormdesKofferraumsisteinwesentlicherUnterschied
zu der Mehrzahl der in der Literatur betrachteten Packungsprobleme. Mo-
tiviert durch die bisher manuell erstellten Packungen verfolgen wir in dieser
Arbeit einen diskreten Lösungsansatz. Wir zeigen, dass bereits eine diskre-
te Variante des eigentlichen Packungsproblems NP-vollständig ist. Für diese
diskreteVarianteexistierteinApproximationsschemamitpolynomiellerZeit-
komplexität,dasfürdieinderPraxisauftretendenProblemgrößenallerdings
nicht geeignet ist.
DieDiskretisierungerfolgtinzweiSchritten:Zunächstapproximierenwir
das Innere des Kofferraums durch ein dreidimensionales, kubisches Gitter.
Diese Approximation erfordert besondere Sorgfalt, da die geometrische Be-
schreibung des Kofferraums verschiedene Arten von Mängeln aufweist. Wei-
terhinschränkenwirinderdiskretenProblemstellungdiemöglichenPositio-
nen und Orientierungen der Quader ein, so dass alle Quader an den Zellen
des Gitters ausgerichtet sind. Wir verwenden effiziente Implementierungen
der notwendigen geometrischen Prädikate und beschreiben Algorithmen, um
die Informationen einer vorhandenen Approximation bei einer Veränderung
ihrerParameterzuaktualisieren.DiesebeidenKomponentenverwendenwir,
um eine möglichst gut geeignete Approximation des Kofferraums zu berech-
nen.
Das diskrete Packungsproblem lässt sich zurückführen auf die Berech-
nung einer möglichst großen unabhängigen Knotenmenge (stable set) in
dem zugehörigen Konfliktgraphen. Wir formulieren das Problem zunächst
als ganzzahliges lineares Programm und erhalten damit einen Algorithmus,derdasPackungsproblemoptimallösenkann.InderPraxisstelltsich jedoch
heraus,dassselbstmitmarktführendenSoftwarebibliothekenfürganzzahlige
lineare Programme nur kleine Probleminstanzenmit angemessenem Rechen-
aufwand beweisbar optimal gelöst werden können. Dennoch ist ein solcher
exakter Algorithmus nützlich für kleinere Teilprobleme.
Aus diesem Grund präsentieren wir verschiedene Heuristiken. Diese las-
sen sich in zwei Kategorien unterteilen: direkte Ansätze, die das Packungs-
problem in seiner Vollständigkeit lösen können, und indirekte Ansätze, die
das Packungsproblem auf eine Menge kleinerer Teilprobleme reduzieren.
WirstellenzunächsteineeinfacheGreedy-Heuristikvor,derenErgebnisse
allerdingshinterdenErwartungenzurückbleiben.Weiterhinpräsentierenwir
einenAlgorithmus,deriterativdieInformationendeswesentlicheinfacherzu
lösendenkontinuierlichenlinearenProgrammsnutztumdieProblemgrößezu
reduzieren. Sobald die Problemgröße hinreichend reduziert wurde, wird das
verbleibende Teilproblem durch ein ganzzahliges lineares Programm optimal
gelöst. Schließlich stellen wir einen auf lokaler Suche basierenden Algorith-
mus vor. Dieser Algorithmus beinhaltet einen Rückkopplungsmechanismus
zur Vermeidung von Zyklen. Regelmäßige Neustarts helfen dabei eine breite
Abdeckung des Suchraumszu erreichen.Die Liste der direkten Ansätze wird
durch eine einfache Heuristik ergänzt, die sich an der geometrischen Form
des Kofferraums orientiert.
Als indirekte Ansätze stellen wir zwei einfache Heuristiken vor, die zu-
nächst das Innere des Kofferraums mit dichten, regelmäßigen Packungen
füllen. Dadurch entstehen Teilprobleme unterschiedlicher Zahl und Größe,
die wir durch einen der zuvor vorgestellten direkten Ansätze lösen. Ein drit-
ter indirekter Ansatz unterteilt den Kofferraum in mehrere Regionen, die
sequentiell gepackt werden. Um den durch die Unterteilung entstehenden
Verschnitt zu reduzieren, ist es dabei notwendig, die Regionen nicht unab-
hängig voneinander zu behandeln und die Platzierung der Quader innerhalb
der Regionen gezielt zu beeinflussen.
Wir untersuchenanHand realerDatensätzeausder Praxiszunächstver-
schiedeneVariantenundImplementierungsdetailsdervorgestelltenAlgorith-
men. Die so gewonnenen Erkenntnisse verwenden wir, um die Algorithmen
auf die typischen Instanzen abzustimmen. Wir zeigen an einem praktischen
Beispiel, dass es oft vorteilhaft ist, bestimmte kleinere Bereiche des Koffer-
raums zunächst getrennt zu behandeln (inklusive eigener Approximation).
Schließlichvergleichenwir verschiedeneKombinationender vorgestelltenAl-
gorithmen hinsichtlich der Qualität und Struktur der Lösungen als auch der
dazu benötigten Rechenzeit. In der Mehrzahl der Fälle erreichen wir die ge-
forderte Lösungsgüte, in manchen Fällen übertreffen wir sogar die manuell
von Experten zur Verfügung gestellten Packungen.
Alle in dieser Arbeit beschriebenen Algorithmen wurden in einem ein-
fach zu bedienenden Softwarepaket integriert. Dieses