Globale und lokale Optimierungsverfahren für dreidimensionale Anordnungsprobleme

Abstract

Thema dieser Arbeit sind <i>Optimierungsverfahren zur Anordnung dreidimensionaler, polyonaler Objekte</i>. Zielkriterium ist die möglichst dichte Packung der Objekte unter Berücksichtigung vorgegebener Randbedingungen. <br /> Es werden zwei Verfahrensklassen betrachtet: <i>Globale Optimierungsmethoden</i>, mit denen die relative Anordnung von Objekten festgelegt wird (z. B. Objekt A liegt rechts/links von Objekt B), und <i>lokale Verfahren</i>, mit denen die Kompaktierung einer gegebenen Ausgangsanordnung durchgeführt wird (die relative Lage der Objekte bleibt hier weitgehend erhalten).<br /> Gemeinsame Basis der Verfahren bildet die <i>Lineare Programmierung</i> zur Problemformulierung, so dass ausgereifte und numerisch stabile Lösungsalgorithmen zur Verfügung stehen. <br /> Für die globalen Optimierungsverfahren werden diskrete Drehwinkelmengen vorgegeben, wobei in der praktischen Anwendung nur kleine Winkelmengen betrachtet werden (z. B. Vielfache von 90°). In den lokalen Optimierungsverfahren werden hingegen <i>kontinuierliche Objektdrehungen</i> berücksichtigt. <br /> Aus geometrischer Sicht werden insbesondere Verfahren zur Objektseparation (<i>Distanzpolyeder</i> oder Hodographen und <i>GJK-Algorithmus</i>) und eine linearisierte Darstellung von Objektdrehungen (<i>infinitesimale Rotationen</i>) betrachtet.

<b>Optimization techniques for three-dimensional arrangement problems of polyhedral objects</b><br /> This thesis covers <i>optimization techniques for three-dimensional arrangement problems of polyhedral objects</i>. The objective is to minimize the occupied space while respecting problem specific side constraints.<br /> We discuss two types of optimization techniques:<i> Global Optimization</i> to determine the relative position of objects (e.g. object A is to the right of object B) and <i>Local Optimization</i> to do a compaction of a predefined initial arrangement (in this case the relative position of objects is typically not changed).<br /> Problem formulation and solution algorithms are based on <i>Linear Programming</i> in both cases. Therefore, robust and efficient optimization technologies can be used. <br /> We use a set of predefined, discrete object orientations for global optimization; for instance multiples of 90°. For local optimization or compaction we consider continuous object rotations. <br /> Object separation (<i>No-Fit-Polygons</i> or Hodographs and <i>GJK-Algorithm</i>) and a linearized version of object orientations (<i>Infinitesimal Rotations</i>) are covered from a geometrical point of view.