Optimales Sortieren von Objekten

This thesis is concerned with the problem of optimally rearranging objects, in particular, railcars in a rail yard. The work is motivated by a research project of the Institute of Mathematical Optimization at Technische Universität Braunschweig, together with our project partner BASF, The Chemical Company, in Ludwigshafen. For many variants of such rearrangement problems - including the real-world application at BASF - we state the computational complexity by exploiting their equivalence to particular graph coloring, scheduling, and bin packing problems. We present mathematical optimization methods for determining schedules that are either optimal or close to optimal, and computational results are discussed from both a theoretical and practical point of view. In addition to the railway industry, there are other fields of application in which efficiently rearranging, sorting, or stacking is an important issue. For instance, the results obtained in this thesis could also be applied to solving certain piling problems in warehouses or container terminals.Die Dissertation beschäftigt sich mit dem optimalen Sortieren von Objekten, insbesondere von Güterwagen in Rangierbahnhöfen. Motiviert wurde diese Arbeit durch ein BMBF-gefördertes Projekt mit der BASF, The Chemical Company, in Ludwigshafen. Zahlreiche Varianten derartiger Sortierprobleme werden mathematisch formuliert und komplexitätstheoretisch eingeordnet. Für viele Varianten wird deren Äquivalenz zu bestimmten Graphenfärbungs-, Scheduling- sowie Bin-Packing-Problemen gezeigt. Für mehrere als theoretisch schwer bewiesene Fälle werden schnelle approximative Algorithmen vorgeschlagen, die Lösungen mit einer beweisbaren Güte liefern. Neben heuristischen Methoden werden auch exakte Verfahren zur Bestimmung optimaler Lösungen vorgestellt. Unter anderem handelt es sich bei den eingesetzten exakten Ansätzen um LP- sowie Lagrange-basierte Branch-and-Bound-Verfahren, die auf verschiedenen binären Modellen beruhen. Die Lösungsmethoden werden durch die Auswertung von Rechenergebnissen für reale Daten evaluiert. Den Abschluss der Dissertation bildet eine Kompetitivitätsanalyse diverser Online-Varianten, die dadurch gekennzeichnet sind, dass nicht alle relevanten Informationen zu Beginn der Planung vorliegen. Es sei auf das Verwertungspotenzial der in dieser Arbeit vorgestellten Optimierungsverfahren innerhalb anderer Anwendungsbereiche, in denen Sortieren, Stapeln, Lagern oder Verstauen eine Rolle spielen, hingewiesen