Mit dem Ziel einer flächendeckenden technischen Interoperabilität schreitet die Entwicklung und Verbreitung des European Train Control System (ETCS) sowohl fahrzeug- als auch infrastrukturseitig voran. Zukünftig werden vermehrt ETCS-only Fahrzeuge, d. h. Fahrzeuge mit allein ETCS und ohne weiterem Zugbeeinflussungssystem, unterwegs sein. Die Deutsche Bahn rüstet dementsprechend ihre Strecken nach und nach mit ETCS aus, wobei zwei Varianten - ETCS Level 2 und ETCS signalgeführt - umgesetzt werden. Die Regelwerke bezüglich der zwei Varianten werden von der Deutschen Bahn stets weiter entwickelt. Für Nichtbundeseigene Eisenbahnen (NE), deren Charakteristiken häufig einfache gehaltene Nebenbahnen und zur Deutschen Bahn abweichende Randbedingungen sind, ist noch kein Konzept einer ETCS-Ausrüstung erstellt worden. Um sicherzustellen, dass auch zukünftig die Infrastruktur von NE durch ETCS-only Fahrzeuge befahren werden kann, ist eine ETCS-Ausrüstung erforderlich. Im Rahmen dieser Arbeit wird nun aufbauend von den Anforderungen der NE ein allgemeines Ausrüstungskonzept erstellt, dass weitgehend die unterschiedlichen Gegebenheiten beinhaltet.

Many European railway infrastructure operators have to expand their networks to deal with rising demand. Extensions are planned using the process of timetable-based infrastructure development, where a strategic timetable is calculated first, and necessary infrastructure expansions are identified afterward. While numerous mathematical optimization models for railway network design and railway timetabling exist, there is a lack of network design models that explicitly focus on timetable-based demand data. This is addressed through the development of three variants of the timetable-based railway network design problem (TBRNDP): a nominal model (TBRNDP-N) that optimizes a network for a single timetable scenario, a robust model (TBRNDP-R) that extends the nominal model to incorporate uncertain demand data and a budget-constrained model (TBRNDP-B) that aims to maximize the satisfied demand while respecting a budget. The optimization models developed in this thesis use multigraphs as a mesoscopic representation of railway infrastructure. Nodes represent stations or junctions. The capacity of nodes is not limited due to complexity reasons. Edges represent individual tracks between two nodes, with multiple parallel edges denoting multi-track lines. The infrastructure model also considers node links, which denote which lines are directly connected in a node. The edge capacities are estimated using train type- and order-dependent headway times, which must be respected between two following or crossing trains. The models provide capacity by activating additional edges or reducing travel or headway times. Demand data is derived from a strategic timetable as a list of trains with attributes such as routing or timing restrictions and train types. Furthermore, timing relationships between two trains, such as frequencies or transfers, are considered. A preprocessing routine has been developed to identify and eliminate those variables and constraints that cannot be part of a feasible solution. It consists of three steps: path generation and evaluation, track-choice rules, and headway evaluation. Suitable paths that respect the routing and timing restrictions are generated before the optimization. The track-choice rules reduce symmetry within the optimization. Headway cases are evaluated using the time bounds and the shortest possible travel times to identify which headway times are implicitly respected and which have to be enforced by the optimization model. The nominal model TBRNDP-N optimizes a network for a single strategic timetable. The model computes a feasible macroscopic timetable and a cost-optimal railway network based on the demand data and a choice of possible network elements. The objective function minimizes infrastructure costs, including fixed costs for activating edges and node links and specific costs for each minute of travel or headway time reduction. The objective function is subject to constraints covering network- and timing-related aspects. The network design constraints enforce that one path is activated for each train, that each train is routed on specific tracks, and that all network elements required by trains are activated. The temporal aspect of timetabling is integrated through timing variables that denote the time at which departure and arrival events occur. A feasible temporal path has to be assigned to each train in a way that respects travel times, time bounds, and node timing constraints. Timing relationships between two trains cover frequencies and transfers enforce that two events associated with two trains happen within a defined time window. The headway times are differentiated between following trains that travel in the same direction and crossing trains that travel in opposite directions. Constraints are defined according to the evaluation of headway cases from the preprocessing. Computational experiments are conducted using real-world data from the Deutschlandtakt, a strategic timetable for Germany. They prove the model’s functionality but also show that performance improvements are necessary to calculate high-quality solutions for large test instances. This is addressed by introducing a heuristic decomposition approach based on the logic-based Benders decomposition concept. Using an integer (IP)-model for routing and network design, a satisfiability-module-theories (SMT)-model for timetabling, and an iterative solution procedure, the heuristic is capable of finding solutions in a much shorter time, but at the expense of solution quality. Finally, a brief sensitivity analysis is conducted, which demonstrates that shadow prices are unsuitable for capturing the model’s reactions to right-hand-side modifications and shows that relaxing the time bounds benefits network costs. Strategic timetables are based on demand prognoses and political requirements and, therefore, are subject to uncertainty. Using TBRNDP-N to optimize a network specifically for one strategic timetable could lead to issues when the strategic timetable changes and expensive additions to the infrastructure are necessary to accommodate the additional demands from the modified timetable. To avoid this, the model TBRNDP-N has been expanded to deal with uncertain input data modeled in two ways: discrete timetable scenarios cover different timetable concepts, and optional trains handle uncertain demand within a scenario. The robust model TBRNDP-R can optimize networks on which several different timetable scenarios can be operated. It is possible to control the robustness level through a coverage share parameter. Optional trains can be used to identify capacity reserves within the solution network, as they can be activated if sufficient capacity is available and they do not require additional infrastructure investments. A computational study has been conducted using two small test instances from the Deutschlandtakt, which have been extended to ten scenarios each. The results show that the robust model suffers from performance issues. Therefore, a decomposition heuristic for TBRNDP-R has been developed, which solves the scenarios individually and uses an SMT model to determine which timetable scenario can be activated on which infrastructure. Afterward, the network covering most scenarios is iteratively extended until a solution covering all scenarios has been found. The heuristic showed encouraging results, both in terms of computation times and solution quality. However, it heavily depends on the performance of TBRNDP-N, as it uses this for each scenario. The chapter closes by analyzing the robust model’s sensitivity towards changing train penalties, establishing a trade-off between additional infrastructure costs and penalties for inactive trains. The literature review conducted at the beginning of the thesis shows that many applications for railway network design have to deal with a limited budget for infrastructure investments. Therefore, the budget-constrained model TBRNDP-B has been developed, which features a change in the objective function: Instead of minimizing costs to satisfy a fixed demand, the budget-constrained model aims to maximize the fulfilled demand while respecting a limited budget for infrastructure investments. Six different measures to quantify the fulfilled demand are introduced and evaluated, with the preferred one using the shortest path’s length as the objective coefficient for each train. Computational experiments proved that the model works as intended and that usable solutions can be obtained within a reasonable time. The presented optimization models are valuable tools for an automatic and optimized network design process. Nevertheless, they also provide a foundation for further research. These include extensions of the modeling framework and the development of solution algorithms. Further research focusing on modeling could address the unlimited node capacities by incorporating different measures to quantify the node capacity or using a network-wide capacity measure. Also, more technical restrictions on edges could be considered and used as possible capacity extensions to further increase the practical applicability of the models. The presented models do not consider timetable quality, which could also be a promising topic of further research by incorporating a measure of timetable quality, such as average travel times or operational stability, into the objective function. The heuristic solution algorithms presented for TBRNDP-N and TBRNDP-R provided promising results regarding computation time reduction. However, the one for TBRNDP-N struggled to achieve a solution quality similar to the complete IP model. Refining the heuristics or developing an algorithm capable of providing optimal solutions would be a promising area of research and an essential step toward the productive use of the optimization models.:1. Introduction 1 1.1. Strategic Infrastructure Development 1.1.1. Strategic Timetables and Their Role in the Planning Process 1.1.2. Creating Strategic Timetables Using Mathematical Optimization Models 1.2. Network Design Problems 1.2.1. Combining Network Design and Scheduling 1.2.2. Applications of Network Design Problems to Railways 1.2.3. Robustness in Railway Network Design 1.3. Contributions of This Thesis 2. Modeling Railway Infrastructure, Timetables and Capacity 2.1. Infrastructure 2.1.1. The Mesoscopic Infrastructure Model With Parallel Edges and Node Links 2.2. Timetables 2.3. Capacity of Railway Lines 3. The Nominal Optimization Model TBRNDP-N 3.1. Preparing the Data for Optimization 3.1.1. Path Generation and Network-Related Sets 3.1.2. Track-Choice Rules 3.1.3. Time Window Evaluation and Headway-Related Sets 3.2. Basic Formulations for the Network Design Problem 3.2.1. The Multi-Commodity, Capacitated Fixed-Charge Network Design Problem with Arc-Flow Variables 3.2.2. The Multi-Commodity, Capacitated Fixed-Charge Network Design Problem with Path-Flow Variables and Unsplittable Flows 3.3. The Nominal Timetable-Based Railway Network Design Problem TBRNDP-N 3.4. Computational Experiments for the Nominal Model 3.4.1. Introduction to the Test Dataset 3.4.2. Evaluation of the Preprocessing Measures 3.4.3. Computational Results for Timetable-based railway network design problem - nominal (TBRNDP-N) 3.4.4. Discussion of the Experiments 3.5. A Decomposition Approach for TBRNDP-N Using Logic-Based Benders Decom- position 3.5.1. Benders Decomposition 3.5.2. Logic-Based Benders Decomposition 3.5.3. Satisfiability Modulo Theories 3.5.4. A Decomposition Heuristic for TBRNDP-N using satisfiability modulo theories (SMT) 3.5.5. Computational Results for the SMT-Based Decomposition Heuristic 3.5.6. Discussion of the Heuristic 3.6. Sensitivity Analysis 3.6.1. Sensitivity Analysis in General 3.6.2. Right-Hand-Side Variation for TBRNDP-N 3.6.3. Conclusion 3.7. Summary 4. The Robust Optimization Model TBRNDP-R 4.1. Uncertainty in Strategic Timetables 4.1.1. Timetable Scenarios 4.1.2. Optional Trains 4.2. The Robust Timetable-Based Railway Network Design Problem TBRNDP-R 4.3. Computational Results for the Robust Model 4.3.1. Discussion 4.4. A Decomposition Heuristic for the Robust Model TBRNDP-R 4.4.1. Computational Results for the Decomposition Algorithm 4.5. Sensitivity Analysis of the Robust Model Timetable-based railway network design problem - robust (TBRNDP-R) 4.6. Summary 5. The Budget-Constrained Model TBRNDP-B 5.1. Formulation of TBRNDP-B 5.1.1. Evaluating Different Objective Functions for Timetable-based railway network design problem - budget (TBRNDP-B) 5.2. Computational Results for the Budget-Constrained Model 5.3. Summary 6. Summary and Future Developments 6.1. Summary of Main Contributions 6.2. Further Research Directions / Viele europäische Eisenbahninfrastrukturunternehmen müssen ihre Kapazitäten erweitern, um mit der steigenden Nachfrage Schritt zu halten. Erweiterungen werden häufig nach dem Verfahren der fahrplanbasierten Infrastrukturentwicklung geplant, bei dem zunächst ein strategischer Fahrplan berechnet und anschließend die notwendigen Infrastrukturerweiterungen ermittelt werden. Es gibt zwar zahlreiche Optimierungsmodelle für die Berechnung optimaler Netzwerke und Fahrpläne, aber es fehlt an Modellen für die Infrastrukturentwicklung, die sich explizit auf fahrplanbasierte Nachfragedaten konzentrieren. Diesem Problem wird durch die Entwicklung von drei Varianten des fahrplanbasierten Netzwerkdesignproblems für Eisenbahnen (timetable-based railway network design problem, TBRNDP) begegnet: ein nominales Modell (TBRNDP-N), das ein Netz für ein bestimmtes Fahrplanszenario optimiert, ein robustes Modell (TBRNDP-R), das das nominale Modell erweitert, um unsichere Nachfragedaten einzubeziehen, und ein Modell mit limitiertem Budget (TBRNDP-B), das darauf abzielt, die befriedigte Nachfrage unter Berücksichtigung eines Budgets zu maximieren. Die in dieser Arbeit entwickelten Optimierungsmodelle verwenden Multigraphen und eine mesoskopische Darstellung der Eisenbahninfrastruktur. Die Knoten stellen Bahnhöfe oder Abzweigstellen dar, deren Kapazität aus Komplexitätsgründen nicht begrenzt ist. Kanten stellen einzelne Gleise zwischen zwei Knoten dar, wobei mehrgleisige Strecken durch mehrere, parallele Kanten abgebildet werden. Das Infrastrukturmodell beinhaltet auch Verbindungskurven, die angeben, welche Strecken in einem Knoten direkt miteinander verbunden sind. Die Streckenkapazitäten werden mit Hilfe von zugart- und zugfolgeabhängigen Mindestzugfolgezeiten abgeschätzt, die zwischen zwei aufeinander folgenden oder sich kreuzenden Zügen eingehalten werden müssen. Die Modelle stellen Kapazität durch die Aktivierung zusätzlicher Kanten oder die Verringerung von Fahr- oder Zugfolgezeiten bereit. Die Nachfragedaten werden aus einem strategischen Fahrplan als Liste von Zügen mit zeitlichen und räumlichen Vorgaben sowie Zugeigenschaften abgeleitet. Darüber hinaus werden zeitliche Beziehungen zwischen zwei Zügen, wie z. B. Takte oder Anschlüsse, berücksichtigt. Es wurde eine Preprocessing-Routine entwickelt, um diejenigen Variablen und Nebenbedingungen zu identifizieren und zu eliminieren, die nicht Teil einer gültigen Lösung sein können. Sie besteht aus drei Schritten: Pfaderzeugung und -Bewertung, Regeln für die Gleiszuordnung und Analyse von Zugfolgefällen. Das nominale Modell TBRNDP-N optimiert ein Netzwerk für einen strategischen Fahrplan. Basierend auf den Nachfragedaten und einem maximal möglichen Netzwerk wird durch das Modell ein zulässiger, makroskopischer Fahrplan und ein dafür optimiertes Netzwerk berechnet. Die Zielfunktion minimiert die Infrastrukturkosten, bestehend aus fixen Kosten für die Aktivierung von Kanten und Verbindungskurven und spezifischen Kosten für jede Minute Fahr- oder Zugfolgezeitverkürzung. Die Zielfunktion unterliegt Nebenbedingungen, die Aspekte des Netzwerkdesigns und der Fahrplanung abdecken. Die Nebenbedingungen für das Netzwerkdesign stellen sicher, dass für jeden Zug ein Pfad ausgewählt wird, dass jeder Zug auf bestimmte Gleise geleitet wird und dass alle von den Zügen benötigten Netzelemente aktiviert werden. Der zeitliche Aspekt der Fahrplangestaltung wird durch Zeitvariablen integriert, die Zeitpunkte für Ankunfts- und Abfahrtsereignisse angeben. Jedem Zug muss eine realisierbare zeitliche Trasse zugewiesen werden, die die Fahrzeiten, die Zeitvorgaben und die zeitliche Flusserhaltung in Knoten berücksichtigt. Zeitliche Verknüpfungen zwischen zwei Zügen umfassen Takte und Anschlüsse und stellen sicher, dass zwei Ereignisse zweier verschiedener Züge innerhalb eines bestimmten Zeitfensters statt finden. Bei den Zugfolgezeiten wird zwischen einander folgenden und kreuzenden Zügen unterschieden. Mit realen Daten aus dem Deutschlandtakt, einem deutschlandweitem strategischen Fahrplankonzept, wurde eine Reihe von Experimenten durchgeführt. Sie beweisen die Funktionalität des Modells, zeigen aber auch, dass Performanceverbesserungen notwendig sind, um qualitativ hochwertige Lösungen für große Testinstanzen zu berechnen. Dazu wird ein heuristischer Dekompositionsalgorithmus auf der Grundlage der logic-based Benders Decomposition entwickelt. Unter Verwendung eines Integer-Modells für Routing und Netzwerkdesign, eines Satisfiability-Modulo-Theories (SMT)-Modells für die Fahrplanung und eines iterativen Lösungsverfahrens ist die Heuristik in der Lage, Lösungen in wesentlich kürzerer Zeit zu finden. Allerdings ist die Lösungsqualität noch nicht zufriedenstellend. Strategische Fahrpläne beruhen auf Nachfrageprognosen und politischen Vorgaben und sind daher mit Unsicherheiten behaftet. Die Verwendung von TBRNDP-N zur Optimierung eines Netzes speziell für einen strategischen Fahrplan könnte zu Problemen führen, wenn sich der strategische Fahrplan ändert und teure Ergänzungen der Infrastruktur erforderlich sind. Um dies zu vermeiden, wurde das Modell TBRNDP-N erweitert, um mit unsicheren Eingangsdaten umgehen zu können, die auf zwei Arten modelliert werden: diskrete Fahrplanszenarien decken verschiedene Fahrplankonzepte ab, und optionale Züge behandeln unsichere Nachfrage innerhalb eines Szenarios. Das robuste Modell TBRNDP-R kann optimierte Netzwerke berechnen, auf denen mehrere unterschiedliche Fahrplanszenarien gefahren werden können. Es ist möglich, den Grad der Robustheit zu steuern. Optionale Züge können zur Identifizierung von Kapazitätsreserven innerhalb des Netzwerks verwendet werden. Auch für das robuste Modell wurde eine Studie mit zwei kleinen Testfällen aus dem Deutschlandtakt, die auf jeweils zehn Szenarien erweitert wurden, durchgeführt. Die Ergebnisse zeigen, dass die Performance des robusten Modells nicht zufriedenstellend ist. Daher wurde auch für TBRNDP-R ein heuristischer Dekompositionsalgorithmus entwickelt, der die Szenarien zunächst einzeln löst und ein SMT-Modell verwendet, um zu bestimmen, welches Fahrplanszenario auf welcher Infrastruktur aktiviert werden kann. Anschließend wird das Netzwerk, das die meisten Szenarien abdeckt, iterativ erweitert, bis eine Lösung gefunden ist, die alle Szenarien abdeckt. Die Heuristik zeigte vielversprechende Ergebnisse, sowohl in Bezug auf die Berechnungszeiten als auch auf die Lösungsqualität. Sie hängt jedoch stark von der Performance von TBRNDP-N ab, da eine Iteration von TBRNDP-N für jedes Szenario benötigt wird. Die zu Beginn der Arbeit durchgeführte Literaturrecherche hat gezeigt, dass das Budget für Infrastrukturinvestitionen häufig begrenzt ist. Um dies abzubilden, wurde das Modell TBRNDP-B entwickelt, das eine Änderung der Zielfunktion aufweist: Anstatt die Kosten zu minimieren, um eine feste Nachfrage zu befriedigen, zielt das budgetbeschränkte Modell darauf ab, die erfüllte Nachfrage zu maximieren und dabei ein begrenztes Budget für Infrastrukturinvestitionen nicht zu überschreiten. Es werden sechs verschiedene Möglichkeiten zur Quantifizierung der erfüllten Nachfrage vorgestellt und bewertet, wobei das bevorzugte Maß die Länge des kürzesten Pfads als Zielkoeffizient für jeden Zug verwendet. Auch für das budgetbeschränkte Modell konnte im Rahmen einer Studie die Funktionalität nachgewiesen werden. Die vorgestellten Optimierungsmodelle sind wertvolle Werkzeuge für eine automatisierte und optimierte Infrastrukturplanung. Dennoch bieten sie auch eine Grundlage für weitere Forschung. Dazu gehören Erweiterungen der Modellierung sowie die Weiterentwicklung der Lösungsalgorithmen. Die Modellierung könnte beispielsweise hinsichtlich der unbegrenzten Knotenkapazitäten erweitert werden, indem verschiedene Maße zur Quantifizierung der Knotenkapazität oder ein netzweite Kapazitätsabschätzung verwendet werden. Auch könnten weitere technische Beschränkungen für Kanten in Betracht gezogen und als mögliche Kapazitätserweiterungen verwendet werden, um die praktische Anwendbarkeit der Modelle weiter zu erhöhen. Die Qualität der errechneten Fahrpläne wird aktuell nicht betrachtet, was ebenfalls ein vielversprechendes Thema für weitere Forschungen sein könnte. Beispielsweise könnte ein Maß für die Fahrplanqualität, wie z. B. die durchschnittlichen Reisezeiten oder die Betriebsstabilität, in die Zielfunktion aufgenommen werden. Die für TBRNDP-N und TBRNDP-R vorgestellten heuristischen Lösungsalgorithmen lieferten vielversprechende Ergebnisse hinsichtlich der Reduzierung der Rechenzeit. Der Algorithmus für TBRNDP-N hatte jedoch Schwierigkeiten, eine Lösungsqualität zu erreichen, die der des vollständigen IP-Modells entspricht. Die Verfeinerung der Heuristiken oder die Entwicklung eines Algorithmus, der in der Lage ist, optimale Lösungen zu liefern, wäre ein weiteres vielversprechendes Forschungsgebiet und ein wesentlicher Schritt hin zu einer produktiven Nutzung der Optimierungsmodelle.:1. Introduction 1 1.1. Strategic Infrastructure Development 1.1.1. Strategic Timetables and Their Role in the Planning Process 1.1.2. Creating Strategic Timetables Using Mathematical Optimization Models 1.2. Network Design Problems 1.2.1. Combining Network Design and Scheduling 1.2.2. Applications of Network Design Problems to Railways 1.2.3. Robustness in Railway Network Design 1.3. Contributions of This Thesis 2. Modeling Railway Infrastructure, Timetables and Capacity 2.1. Infrastructure 2.1.1. The Mesoscopic Infrastructure Model With Parallel Edges and Node Links 2.2. Timetables 2.3. Capacity of Railway Lines 3. The Nominal Optimization Model TBRNDP-N 3.1. Preparing the Data for Optimization 3.1.1. Path Generation and Network-Related Sets 3.1.2. Track-Choice Rules 3.1.3. Time Window Evaluation and Headway-Related Sets 3.2. Basic Formulations for the Network Design Problem 3.2.1. The Multi-Commodity, Capacitated Fixed-Charge Network Design Problem with Arc-Flow Variables 3.2.2. The Multi-Commodity, Capacitated Fixed-Charge Network Design Problem with Path-Flow Variables and Unsplittable Flows 3.3. The Nominal Timetable-Based Railway Network Design Problem TBRNDP-N 3.4. Computational Experiments for the Nominal Model 3.4.1. Introduction to the Test Dataset 3.4.2. Evaluation of the Preprocessing Measures 3.4.3. Computational Results for Timetable-based railway network design problem - nominal (TBRNDP-N) 3.4.4. Discussion of the Experiments 3.5. A Decomposition Approach for TBRNDP-N Using Logic-Based Benders Decom- position 3.5.1. Benders Decomposition 3.5.2. Logic-Based Benders Decomposition 3.5.3. Satisfiability Modulo Theories 3.5.4. A Decomposition Heuristic for TBRNDP-N using satisfiability modulo theories (SMT) 3.5.5. Computational Results for the SMT-Based Decomposition Heuristic 3.5.6. Discussion of the Heuristic 3.6. Sensitivity Analysis 3.6.1. Sensitivity Analysis in General 3.6.2. Right-Hand-Side Variation for TBRNDP-N 3.6.3. Conclusion 3.7. Summary 4. The Robust Optimization Model TBRNDP-R 4.1. Uncertainty in Strategic Timetables 4.1.1. Timetable Scenarios 4.1.2. Optional Trains 4.2. The Robust Timetable-Based Railway Network Design Problem TBRNDP-R 4.3. Computational Results for the Robust Model 4.3.1. Discussion 4.4. A Decomposition Heuristic for the Robust Model TBRNDP-R 4.4.1. Computational Results for the Decomposition Algorithm 4.5. Sensitivity Analysis of the Robust Model Timetable-based railway network design problem - robust (TBRNDP-R) 4.6. Summary 5. The Budget-Constrained Model TBRNDP-B 5.1. Formulation of TBRNDP-B 5.1.1. Evaluating Different Objective Functions for Timetable-based railway network design problem - budget (TBRNDP-B) 5.2. Computational Results for the Budget-Constrained Model 5.3. Summary 6. Summary and Future Developments 6.1. Summary of Main Contributions 6.2. Further Research Directions