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.


    Zugriff

    Zugriff über TIB

    Verfügbarkeit in meiner Bibliothek prüfen

    Bestellung bei Subito €


    Exportieren, teilen und zitieren



    Titel :

    Optimal sorting of rolling stock


    Weitere Titelangaben:

    Optimale Sortierung von Rollmaterial


    Beteiligte:

    Erscheinungsdatum :

    2010


    Format / Umfang :

    161 Seiten, Bilder, Tabellen, Quellen



    Medientyp :

    Hochschulschrift


    Format :

    Print


    Sprache :

    Englisch




    Rolling stock

    OOHASHI KENGO | Europäisches Patentamt | 2016

    Freier Zugriff

    ROLLING STOCK

    SAWADA KENTO / FURUKAWA KAZUHIKO / KONISHI KENTA et al. | Europäisches Patentamt | 2016

    Freier Zugriff

    Rolling stock

    OOHASHI KENGO / HAYASHI KENTARO | Europäisches Patentamt | 2016

    Freier Zugriff

    Rolling stock

    NAKAO KOJI / OOHASHI KENGO | Europäisches Patentamt | 2016

    Freier Zugriff

    ROLLING STOCK

    KURODA MASARU / NAKAO KOJI | Europäisches Patentamt | 2015

    Freier Zugriff