Die Dissertation beschäftigt sich mit dem optimalen Sortieren von Objekten, insbesondere von Güterwagen in Rangierbahnhöfen. Im Ludwigshafener Stammwerk der BASF wird ein Großteil der internen Logistik auf der Schiene abgewickelt. Ein Nadelöhr stellt dabei der werkseigene, kostenintensive Rangierbahnhof mit Ablaufberg dar, in dem eingehende Züge zerlegt und die Wagen zu Ausgangszügen umsortiert werden. Das Projektziel war es, ein Optimierungstool als Entscheidungsunterstützung für die Disponenten zu entwickeln, das vollautomatisch optimale Pläne zur Sortierung der Wagen erzeugt. In diesem Kontext des Sortierens von Objekten wird eine umfassende Klassifizierung zahlreicher Varianten eingeführt. Die grundsätzliche Anforderung aller Varianten ist, eine eingehende Sequenz von Objekten in einer Sortieranlage möglichst optimal d.h. in der Regel durch eine minimale Anzahl an zulässigen Operationen in eine Ausgangssequenz zu überführen, welche eine im Vorfeld gewünschte Struktur aufweist. In dieser Arbeit werden zahlreiche Varianten mathematisch formuliert. Für viele Varianten wird deren Äquivalenz zu bestimmten Graphenfärbungs-, Scheduling- sowie Bin-Packing-Problemen gezeigt. Die Dissertation beinhaltet eine komplexitätstheoretische Einordnung einiger Varianten. Für mehrere als theoretisch schwer bewiesene Fälle werden schnelle approximative Algorithmen vorgeschlagen, die Lösungen mit einer beweisbaren Güte liefern. Desweiteren werden neben heuristischen Methoden auch exakte Verfahren zur Bestimmung optimaler Lösungen vorgestellt. Unter anderem handelt es sich bei den eingesetzten exakten Ansätzen um LP- sowie Lagrangebasierte 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. Eine wesentliche Erkenntnis ist, dass sich für das reale Optimierungsproblem bei der BASF mit den vorgeschlagenen Ansätzen innerhalb weniger Minuten optimale Pläne bestimmen lassen. Den Abschluss bildet eine Kompetitivitätsanalyse diverser Online-Varianten, die dadurch gekennzeichnet sind, dass nicht alle relevanten Informationen zu Beginn der Planung vorliegen. Abschließend sei auf das Verwertungspotenzial der in dieser Arbeit vorgestellten Optimierungsverfahren innerhalb anderer Anwendungsbereiche, in denen Sortieren, Stapeln, Lagern oder Verstauen eine Rolle spielen, hingewiesen.
This thesis is concerned with the problem of optimally rearranging objects, in particular, railcars in a rail yard. 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.
Optimal sorting of rolling stock
Optimale Sortierung von Rollmaterial
2010
161 Seiten, Bilder, Tabellen, Quellen
Hochschulschrift
Englisch
Engineering Index Backfile | 1925