# Mathematical optimization of rolling stock rotations

## Reuther, Markus

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.