Loading…
We show how to optimize rolling stock rotations that are required for the operation of a passenger timetable. The underlying mathematical ptimization problem is called rolling stock rotation problem (RSRP) and the leitmotiv of the thesis is RotOR, i.e., a highly integrated optimization algorithm for the RSRP. RotOR is used by DB Fernverkehr AG (DBF) in order to optimize intercity express (ICE) rotations for the European high-speed network. In this application, RSRPs have to be solved which (A) require many different aspects to be simultaneously considered, (B) are typically of large scale, and (C) include constraints that have a difficult combinatorial structure. This thesis suggests answers to these issues via the following concepts.
(A) The main model, which RotOR uses, relies on a hypergraph. The hypergraph provides an easy way to model manifold industrial railway requirements in great detail. This includes well known vehicle composition requirements as well as relatively unexplored regularity stipulations. At the same time, the hypergraph directly leads to a mixed-integer programming (MIP) model for the RSRP.
(B) The main algorithmic ingredient to solve industrial instances of the RSRP is a coarse-to-fine (C2F) column generation procedure. In this approach, the hypergraph is layered into coarse and fine layers that distinguish different levels of detail of the RSRP. The coarse layers are algorithmically utilized while pricing fine columns until proven optimality. Initially, the C2F approach is presented in terms of pure linear programming in order to provide an interface for other applications.
(C) Rolling stock rotations have to comply to resource constraints in order to ensure, e.g., enough maintenance inspections along the rotations. These constraints are computationally hard, but are well known in the literature on the vehicle routing problem (VRP). We define an interface problem in order to bridge between the RSRP and the VRP and derive a straightforward algorithmic concept, namely regional search (RS), from their common features and, moreover, differences. Our RS algorithms show promising results for classical VRPs and RSRPs.
In the first part of the thesis we present these concepts, which encompass its main mathematical contribution. The second part explains all modeling and solving components of RotOR that turn out to be essential in its industrial application. The thesis concludes with a solution to a complex re-optimization RSRP that RotOR has computed successfully for DBF. In this application all ICE vehicles of the ICE-W fleets of DBF had to be redirected past a construction site on a high-speed line in the heart of Germany.
Wir zeigen wie man Eisenbahnumläufe optimiert. Diese sind unerlässlich für die Produktion eines Fahrplans für den Personenverkehr. Das zugrundeliegende mathematische Optimierungsproblem ist das Rolling Stock Rotation Problem (RSRP) und RotOR - ein stark integrierter Optmierungsalgorithmus für das RSRP - bildet den roten Faden der Arbeit. RotOR wird bei der DB Fernverkehr AG (DBF) eingesetzt um Intercity-Express (ICE) Umläufe für das europäische Hochgeschwindigkeitsnetz zu optimieren. Diese Anwendung erfordert das Lösen von Szenarien in denen (A) viele verschiedene Anforderungen simultan, (B) typischer Weise große RSRP Instanzen und (C) Bedingungen mit einer schwierigen kombinatorischen Struktur zu betrachten sind. In dieser Arbeit schlagen wir die folgenden Konzepte für diese Gegebenheiten vor:
(A) Das Gesamtmodell von RotOR basiert auf einem Hypergraphen. Dieser Hypergraph ermöglicht einen einfachen aber dennoch sehr detailierten Umgang mit vielfältigen Anforderungen des Eisenbahnbetriebs. Derartige Anforderungen sind die Fahrzeugkomposition und die noch relativ unerforschte Gleichförmigkeit. Gleichzeitig führt der Hypergraph direkt zu einem gemischt-ganzzahligen Program für das RSRP.
(B) Unser algorithmischer Hauptansatz ist ein Coarse-to-fine (C2F) Spaltengenerierungsverfahren. Dazu wird der Hypergraph in feine und gröbere Schichten, sogenannte Layer, unterteilt. Die Layer entsprechen verschiedenen Detailierungsgraden. Gröbere Layer werden algorithmisch ausgenutzt um Spalten für den feinsten Layer zu erzeugen bis ein Optimalitätsbeweis gefunden ist. Die C2F Methode wird zunächst autonom für lineare Programme erklärt um eine Schnittstelle für andere Probleme bereit zu stellen.
(C) Eisenbahnumläufe müssen sogenannten Ressourcenbedingungen genügen, sodass z.B. ausreichend viele Wartungsmaßnahmen überdeckt sind. Derartige Bedingungen sind schwierig, allerdings vom Vehicle Routing Problem (VRP) in der Literatur bekannt. Wir definieren eine Schnittstelle zwischen RSRP und VRP und entwickeln aus deren
Gemeinsamkeiten und vorallem Unterschieden ein geradliniges algorithmisches Konzept das wir Regionale Suche (RS) nennen. Unsere RS Algorithmen zeigen vielversprechende Ergebnisse für klassische VRP und RSRP Instanzen.
Diese drei Konzepte bilden den mathematischen Hauptbeitrag und den ersten Teil der Arbeit. Der zweite Teil erklärt alle Modellierungs- und Lösungskomponenten welche für die Optimierung von ICE Umläufen bei der DBF notwendig sind. Die Arbeit schließt mit einem komplexen Anwendungsfall bei dem RotOR von der DBF benutzt wurde um ICE
Umläufe für eine Sperrung der Hochgeschwindigkeitstrecke zwischen Frankfurt (Main) und Köln zu berechnen. Aufgrund dieser Baustelle mussten nahezu alle Fahrzeuge der Kategorie ICE-W umgeleitet werden.
