Luca Keidel

Packen von Polygonen mit Hilfe von Metaheuristiken

Betreuer: Prof. Dr. Helmut Alt
Abschluss: Bachelor of Science (B.Sc.)
Abgabedatum: 21.07.2015

Kurzbeschreibung

Die Klasse der Packungs- und Zuschnittsprobleme umfasst eine Vielzahl diverser
praktischer und theoretischer Problemstellungen, aus der in dieser Arbeit das
zweidimensionale nesting problem betrachtet wird. Das nesting problem ist ein
Optimierungsproblem, bei dem die Problemstellung darin besteht, die Anordnung
mehrerer geometrischer Objekte so zu optimieren, dass der Platz optimal ausgenutzt
wird.

Bei den zu packenden Objekten handelt es sich in dieser Arbeit um einfache und
lochfreie Polygone, d.h. Polygone, deren Kanten sich jeweils untereinander nicht
schneiden dürfen. Die Anordnung der Polygone wird dahingehend optimiert, dass die
Ausnutzung der Fläche der achsenparallelen Bounding Box maximiert bzw. der Verschnitt
in Bezug auf ebendiese minimiert wird.

Da es sich bei dem nesting problem um ein NP-schweres Optimierungsproblem handelt,
ist bis dato kein effizienter Algorithmus bekannt, der in der Lage ist, eine optimale
Lösung für das Problem zu erzeugen. Daher wird eine Lösung mittels Metaheuristiken
approximiert, bei denen es sich um problemunabhängige abstrakte Verfahren zur Erzeugung
von heuristischen Optimierungsalgorithmen handelt.

In der Arbeit werden die Metaheuristiken Simulated Annealing und genetische Algorithmen
verwendet. Es werden verschiedene Ansätze zur Anwendung der beiden Metaheuristiken auf das
nesting problem vorgestellt und implementiert. Anhand eines Schnittmusters für T-Shirts aus
der Praxis und weiteren Probleminstanzen, wie Legepuzzles, werden die Ansätze getestet und
die Ergebnisse ausgewertet.

Die erzielten Ergebnisse der verschiedenen Ansätze unterscheiden sich teilweise deutlich in
ihrer Qualität. Insgesamt werden mit den Ansätzen gute, allerdings entsprechend der
heuristischen Natur der Verfahren, nicht optimale Ergebnisse erzielt.