Diese Dissertation untersucht die algorithmischen Grundlagen eines Sortierproblems aus dem Bereich der Eisenbahnoptimierung. Bei dem betrachteten Optimierungsproblem geht es um das Rangieren von Waggons im Bahngüterverkehr, was einen fundamentalen Arbeitsvorgang im Bahnbetrieb darstellt, bei dem die Wagen mehrerer Güterzüge umgruppiert werden, um neue Güterzüge zu bilden. Bei den heute verwendeten Rangiermethoden handelt es sich um äußerst vorsichtige Ansätze, was viele Möglichkeiten zur Verbesserung durch systematische Optimierungsverfahren birgt. Zu Beginn wird eine neuartige Kodierung von Rangierplänen eingeführt, was nicht nur eine effiziente Darstellung von Ran gierplänen sondern auch eine Beschreibung ihrer Gültigkeiter laubt. Mit Hilfe dieser Repräsentation wird dann ein Algorithmus zur Berechnung optimaler Rangierpläne für die Grundversion des Sortierproblems entwickelt. Verschiedene Gegebenheiten innerhalb des praktischen Problems fuhren zu zusätzlichen Anforderungen an einen gültigen Rangierplan. Es wird gezeigt, wie sich diese Anforderungen in zusätzliche formale Randbedin gungen in der oben genannten Darstellung übertragen lassen. Anschließend werden erfolgreiche Lösungswege für diverse Nebenbedingungen bezüglich der Infrastruktur und des Betriebs des Rangierbahnhofs entwickelt. Diese umfassen insbesondere verschiedene Beschränkungen des Gleisvolumens, eingeschränkte Abfahrtszeiten fertiggestellter Züge oder zeitabhängige Verfügbarkeiten von Gleisen. Bei den Lösungsmethoden handelt es sich um effiziente exakte und Approximationsalgorithmen sowie Modellierungen ganzzahliger Programme, in denen sich mehrere solcher Nebenbedingungen gleichzeitig integrieren lassen. Eine robuste Problemvariante beschäftigt sich mit Unsicherheiten in der Eingabe, was bei diesem Problem Störungen im Eisenbahn netz entspricht, welche wiederum verspätete Ankünfte von Güterzügen am Rangierbahnhof nach sich ziehen. Es wird ein Modell eingeführt, bei dem ein vorgefertigter Rangierplan - wenn er durch eine auftretende Verspätung ungültig geworden ist - korrigiert werden kann indem zusätzliche Rangierschritte in den Vorgang eingefügt werden. Für den Fall, dass keine Annahmen zum größtmöglichen Umfang auftretender Verspätungen gemacht werden, wird gezeigt, dass es sich bei der robusten ProblemVariante um ein A/"P-schweres Problem handelt. Gleich wohl wird eine generische Methode für diese allgemeine Situation aufgestellt, von der wiederum ein effizienter Algorithmus für ein realistisches Verspätungsmodell abgeleitet wird. Die entwickelten theoretischen Verfahren werden miteinander verglichen und experimentell unter Verwendung diverser synthetischer und echter Verkehrsdaten evaluiert. Die Experimente zeigen, dass die gewonnenen Einsichten und entwickelten Lösungsverfahren von hoher praktischer Relevanz sind.

    In this thesis the algorithmic foundations of a particular sorting problem from railway optimization are studied. The addressed problem is called tram classification, and it refers to the fundamental procedure of rearranging the cars of several trains into other compositions of different orders comprising new trains. The train classification methods applied today present rather conservative approaches, and there is a lot of room for systematic improvement by applying optimization methods. First of all, a novel encoding of classification schedules is presented. This does not only yield an efficient representation of train classification schedules, but it also allows characterizing feasible classification schedules and is applied to derive an algorithm for computing optimal classification schedules for the core version of the sorting problem. Several practical problem settings then yield further restrictions on a feasible schedule, which are shown to translate to formal constraints in the above mentioned representation. Successful solution approaches are then developed for various infrastructural as well as operational constraints. The former particularly cover different dimensions of limited track space, the latter include train departures and track space varying over time. The approaches comprise efficient exact and approximation algorithms and also integer programming models that allow integrating several such constraints simultaneously. Then, another problem variant deals with the robustness aspect of uncertain input, which here corresponds to disruptions in the railway network resulting in trains arriving delayed at the classification yard. A model is introduced in which a prepared schedule that became infeasible by an arising disruption is adjusted by inserting some additional steps into the sorting process. Without any assumptions on the amount of disruption, this robust problem variant is shown to be NP-hard. Still, a generic method is provided for the general setting, from which an efficient algorithm for a realistic model of disruption is derived. The developed theoretical approaches are compared to each other and evaluated experimentally using various synthetically derived and real-world traffic instances to show that the achieved insights and solutions are relevant in practice.


    Access

    Access via TIB

    Check availability in my library

    Order at Subito €


    Export, share and cite



    Title :

    On the problem of sorting railway freight cars: an algorithmic perspective


    Contributors:

    Publication date :

    2011


    Size :

    158 Seiten, Bilder, Tabellen, Quellen



    Type of media :

    Theses


    Type of material :

    Print


    Language :

    English





    Reinforced-concrete railway freight cars

    Gensbaur, Max | Engineering Index Backfile | 1923


    Mechanical refrigeration for railway freight cars

    Rowledge, E.R. | Engineering Index Backfile | 1931


    Railway motor cars for freight traffic

    Heintz, E. | Engineering Index Backfile | 1926