Lagrangian relaxation is a successful solution approach for many combinatorial optimisation problems, one of them being the train timetabling problem (TTP). We model this problem using time expanded networks for the single train schedules and coupling constraints to enforce restrictions like station capacities and headway times. Lagrangian relaxation of these coupling constraints leads to shortest path subproblems in the time expanded networks and is solved using a proximal bundle method. However, large instances of our practical partner Deutsche Bahn lead to computationally intractable models. In this thesis we develop two new algorithmic techniques to improve the solution process for this kind of optimisation problems. The first new technique, Dynamic Graph Generation (DGG), aims at improving the computation of the shortest path subproblems in large time expanded networks. Without sacrificing any accuracy, DGG allows to store only small parts of the networks and to dynamically extend them whenever the stored part proves to be too small. This is possible by exploiting the properties of the objective function in many scheduling applications to prefer early paths or due times, respectively. We prove that DGG can be implemented very efficiently and its running time and the size of nodes that have to be stored additionally does not depend on the size of the time expanded network but only on the length of the train routes. The second technique is an asynchronous and parallel bundle method (APBM). Traditional bundle methods require one solution of each subproblem in each iteration. However, many practical applications, e.g. the TTP, consist of rather loosely coupled subproblems. The APBM chooses only small subspaces corresponding to the Lagrange multipliers of strongly violated coupling constraints and optimises only these variables while keeping all other variables fixed. Several subspaces of disjoint variables may be chosen simultaneously and are optimised in parallel. The solutions of the subspace problem are incorporated into the global data as soon as it is available without any synchronisation mechanism. However, in order to guarantee convergence, the algorithm detects automatically dependencies between different subspaces and respects these dependencies in future subspace selections. We prove the convergence of the APBM under reasonable assumptions for both, the dual and associated primal aggregate data. The APBM is then further extended to problems with unknown dependencies between subproblems and constraints in the Lagrangian relaxation problem. The algorithm automatically detects these dependencies and respects them in future iterations. Again we prove the convergence of this algorithm under reasonable assumptions. Finally we test our solution approach for the TTP on some real world instances of Deutsche Bahn. Using an iterative rounding heuristic based on the approximate fractional solutions obtained by the Lagrangian relaxation we are able to compute feasible schedules for all trains in a subnetwork of about 10% of the whole German network in about 12 hours. In these timetables 99% of all passenger trains could be scheduled with no significant delay and the travel time of the freight trains could be reduced by about one hour on average.

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

The work deals with two problems of mass rapid transit system operation: The development of flexible timetables and the realisation of flexible timetables. In both cases, genetic algorithms are used. In the process of (flexible) timetabling in suburban railways, a transport offer perfectly adapted to demand is searched for (temporal and spatial adaptation of demand as well as adaptation of capacity of the trains). After determination of the number of train runs per line and hour and their capacity, optimal departure times have to be found (with a precision of a minute down to 10 s), which fulfil criterias of the passengers (short waiting times) as well as of the operator (small number of vehicles needed). Two different codings for use with genetic algorithms have therefore been developed. They are tested on several case studies of the Dresden suburban railway network, assuming different degrees of flexibilisation. In the process of realising a flexible timetable, transitions between train headways as well as running time and dwell time reserves (margins in the order of a few seconds) are slightly modified in order to coordinate braking and accelerating trains and thereby reduce energy costs of a system of trains. Genetic algorithms can be applied for this problem as well, the proposed methods are tested on several case studies (S-Bahn Berlin, Metro Lille). / Die Arbeit behandelt zwei Probleme der Betriebsplanung von Stadtschnellbahnen: Die Erstellung flexibler Fahrpläne und die Umsetzung flexibler Fahrpläne. In beiden Fällen werden zur Lösung Genetische Algorithmen verwendet. Bei der Ermittlung flexibler Fahrpläne von S-Bahnen wird ein bestmöglich an die Verkehrsnachfrage angepasstes Verkehrsangebot gesucht (zeitlich, räumlich und bezüglich der Kapazität der einzelnen Züge angepasst). Nach stundenfeiner Festlegung der Fahrtenhäufigkeiten und Kapazitäten der einzelnen, sich überlagernden Linien werden deren Abfahrtszeiten gesucht (mit einer Genauigkeit von Minuten bis etwa 10 s), so dass sowohl die Wünsche der Fahrgäste nach gleichmäßigen Zugfolgezeiten als auch Betreiberwünsche (geringe Fahrzeuganzahl) erfüllt werden. Hierzu werden zwei verschiedene Kodierungen für die Verwendung mit Genetischen Algorithmen vorgestellt und das geschaffene Verfahren an verschiedenen Flexibilisierungsszenarien für die S-Bahn Dresden erprobt. Bei der Umsetzung flexibler Fahrpläne, die sich im Bereich weniger Sekunden abspielt, werden Übergänge zwischen Zugfolgezeiten, Fahr- und Haltezeitreserven geringfügig modifiziert, so dass durch bestmögliche Koordination von Anfahr- und Bremsvorgängen eines Systems von Zügen die Energiekosten minimal werden. Methodisch werden wiederum Genetische Algorithmen verwendet, die Erprobung des Verfahrens erfolgt anhand von Linien der S-Bahn Berlin und der Metro in Lille.

The work deals with two problems of mass rapid transit system operation: The development of flexible timetables and the realisation of flexible timetables. In both cases, genetic algorithms are used. In the process of (flexible) timetabling in suburban railways, a transport offer perfectly adapted to demand is searched for (temporal and spatial adaptation of demand as well as adaptation of capacity of the trains). After determination of the number of train runs per line and hour and their capacity, optimal departure times have to be found (with a precision of a minute down to 10 s), which fulfil criterias of the passengers (short waiting times) as well as of the operator (small number of vehicles needed). Two different codings for use with genetic algorithms have therefore been developed. They are tested on several case studies of the Dresden suburban railway network, assuming different degrees of flexibilisation. In the process of realising a flexible timetable, transitions between train headways as well as running time and dwell time reserves (margins in the order of a few seconds) are slightly modified in order to coordinate braking and accelerating trains and thereby reduce energy costs of a system of trains. Genetic algorithms can be applied for this problem as well, the proposed methods are tested on several case studies (S-Bahn Berlin, Metro Lille). / Die Arbeit behandelt zwei Probleme der Betriebsplanung von Stadtschnellbahnen: Die Erstellung flexibler Fahrpläne und die Umsetzung flexibler Fahrpläne. In beiden Fällen werden zur Lösung Genetische Algorithmen verwendet. Bei der Ermittlung flexibler Fahrpläne von S-Bahnen wird ein bestmöglich an die Verkehrsnachfrage angepasstes Verkehrsangebot gesucht (zeitlich, räumlich und bezüglich der Kapazität der einzelnen Züge angepasst). Nach stundenfeiner Festlegung der Fahrtenhäufigkeiten und Kapazitäten der einzelnen, sich überlagernden Linien werden deren Abfahrtszeiten gesucht (mit einer Genauigkeit von Minuten bis etwa 10 s), so dass sowohl die Wünsche der Fahrgäste nach gleichmäßigen Zugfolgezeiten als auch Betreiberwünsche (geringe Fahrzeuganzahl) erfüllt werden. Hierzu werden zwei verschiedene Kodierungen für die Verwendung mit Genetischen Algorithmen vorgestellt und das geschaffene Verfahren an verschiedenen Flexibilisierungsszenarien für die S-Bahn Dresden erprobt. Bei der Umsetzung flexibler Fahrpläne, die sich im Bereich weniger Sekunden abspielt, werden Übergänge zwischen Zugfolgezeiten, Fahr- und Haltezeitreserven geringfügig modifiziert, so dass durch bestmögliche Koordination von Anfahr- und Bremsvorgängen eines Systems von Zügen die Energiekosten minimal werden. Methodisch werden wiederum Genetische Algorithmen verwendet, die Erprobung des Verfahrens erfolgt anhand von Linien der S-Bahn Berlin und der Metro in Lille.

Lagrangian relaxation is a successful solution approach for many combinatorial optimisation problems, one of them being the train timetabling problem (TTP). We model this problem using time expanded networks for the single train schedules and coupling constraints to enforce restrictions like station capacities and headway times. Lagrangian relaxation of these coupling constraints leads to shortest path subproblems in the time expanded networks and is solved using a proximal bundle method. However, large instances of our practical partner Deutsche Bahn lead to computationally intractable models. In this thesis we develop two new algorithmic techniques to improve the solution process for this kind of optimisation problems. The first new technique, Dynamic Graph Generation (DGG), aims at improving the computation of the shortest path subproblems in large time expanded networks. Without sacrificing any accuracy, DGG allows to store only small parts of the networks and to dynamically extend them whenever the stored part proves to be too small. This is possible by exploiting the properties of the objective function in many scheduling applications to prefer early paths or due times, respectively. We prove that DGG can be implemented very efficiently and its running time and the size of nodes that have to be stored additionally does not depend on the size of the time expanded network but only on the length of the train routes. The second technique is an asynchronous and parallel bundle method (APBM). Traditional bundle methods require one solution of each subproblem in each iteration. However, many practical applications, e.g. the TTP, consist of rather loosely coupled subproblems. The APBM chooses only small subspaces corresponding to the Lagrange multipliers of strongly violated coupling constraints and optimises only these variables while keeping all other variables fixed. Several subspaces of disjoint variables may be chosen simultaneously and are optimised in parallel. The solutions of the subspace problem are incorporated into the global data as soon as it is available without any synchronisation mechanism. However, in order to guarantee convergence, the algorithm detects automatically dependencies between different subspaces and respects these dependencies in future subspace selections. We prove the convergence of the APBM under reasonable assumptions for both, the dual and associated primal aggregate data. The APBM is then further extended to problems with unknown dependencies between subproblems and constraints in the Lagrangian relaxation problem. The algorithm automatically detects these dependencies and respects them in future iterations. Again we prove the convergence of this algorithm under reasonable assumptions. Finally we test our solution approach for the TTP on some real world instances of Deutsche Bahn. Using an iterative rounding heuristic based on the approximate fractional solutions obtained by the Lagrangian relaxation we are able to compute feasible schedules for all trains in a subnetwork of about 10% of the whole German network in about 12 hours. In these timetables 99% of all passenger trains could be scheduled with no significant delay and the travel time of the freight trains could be reduced by about one hour on average.