Hohenheim, Univ., Diss., 2007.

Diss. TU Berlin, 2007.

University, Diss., 1999--Saarbrücken.

Das d-dimensionale Vektorpackproblem (d-VPP), welches aus Planungsaufgaben resultieren kann, ist eine Verallgemeinerung des eindimensionalen Zuschnittproblems (1CSP) und deshalb NP-schwer. Die stetige Relaxation, die mittels Spaltengenerierung gelöst werden kann, ergebe den optimalen Zielfunktionswert zC, während der optimale Zielfunktionswert der ganzzahligen Aufgabe zD ist. In der Dissertation werden obere Schranken für das Gap Δ = zD-zC hergeleitet und systematisch Instanzen des 1CSPs mit großem Δ (bis zu 6/5) konstruiert. Die im Teilbarkeitsfall des 1CSPs bekannte Abschätzung Δ < 2 wird zu Δ < 7/5 verschärft. Im d-VPP mit d > 1 gilt die MIRUP-Hypothese Δ < 2 nicht. Dies und die Unbeschränktheit des Wertes einer Variante bei d gegen unendlich werden an speziellen Beispielen gezeigt. Außerdem wird eine Heuristik vorgeschlagen und erprobt.

Ein großer Anteil des Datenverkehrs in „Internet Service Provider“ (ISP)-Netzen wird heutzutage von „Content Delivery Networks“ (CDNs) verursacht. Betreiber von CDNs verwenden Lastverteilungsmechanismen um die Auslastung ihrer CDN-Infrastruktur zu vergleichmäßigen (Load Balancing). Dies geschieht ohne Abstimmung mit den ISP-Betreibern. Es können daher große Verkehrslastverschiebungen sowohl innerhalb eines ISP-Netzes, als auch auf den Verbindungsleitungen zwischen ISP-Netz und CDNs auftreten. In der vorliegenden Arbeit wird untersucht, welche nicht-kooperativen Möglichkeiten ein ISP hat, um Verkehrslastverschiebungen, welche durch Lastverteilungsmechanismen innerhalb eines CDNs verursacht werden, entgegenzuwirken bzw. abzumildern. Die Grundlage für diese Untersuchung bildet die Analyse des Serverauswahlverhaltens des YouTube-CDNs. Hierzu ist ein aktives Messverfahren entwickelt worden, um das räumliche und zeitliche Verhalten der YouTube-Serverauswahl bestimmen zu können. In zwei Messstudien wird die Serverauswahl in deutschen und europäischen ISP-Netzen untersucht. Auf Basis dieser Studien wird ein Verkehrsmodell entwickelt, welches die durch Änderungen der YouTube-Serverauswahl verursachten Verkehrslastverschiebungen abbildet. Das Verkehrsmodell wiederum bildet die Grundlage für die Bestimmung optimaler Routen im ISP-Netz, welche hohe Robustheit gegenüber CDN-bedingte Verkehrslastverschiebungen aufweisen (Alpha-robuste Routingoptimierung). Für die Lösung des robusten Routing-Optimierungsproblems wird ein iteratives Verfahren entwickelt sowie eine kompakte Reformulierung vorgestellt. Die Leistungsfähigkeit des Alpha-robusten Routings wird anhand von drei Beispielnetztopologien untersucht. Das neue Verfahren wird mit alternativen robusten Routingverfahren und einem nicht-robusten Verfahren verglichen. Neben der robusten Routingoptimierung werden in der Arbeit drei weitere Ideen für nicht-kooperative Methoden vorgestellt (BGP-, IP-Präix- und DNS-basierte Methode), um CDN-bedingten Verkehrslastverschiebungen entgegenzuwirken.

Ein großer Anteil des Datenverkehrs in „Internet Service Provider“ (ISP)-Netzen wird heutzutage von „Content Delivery Networks“ (CDNs) verursacht. Betreiber von CDNs verwenden Lastverteilungsmechanismen um die Auslastung ihrer CDN-Infrastruktur zu vergleichmäßigen (Load Balancing). Dies geschieht ohne Abstimmung mit den ISP-Betreibern. Es können daher große Verkehrslastverschiebungen sowohl innerhalb eines ISP-Netzes, als auch auf den Verbindungsleitungen zwischen ISP-Netz und CDNs auftreten. In der vorliegenden Arbeit wird untersucht, welche nicht-kooperativen Möglichkeiten ein ISP hat, um Verkehrslastverschiebungen, welche durch Lastverteilungsmechanismen innerhalb eines CDNs verursacht werden, entgegenzuwirken bzw. abzumildern. Die Grundlage für diese Untersuchung bildet die Analyse des Serverauswahlverhaltens des YouTube-CDNs. Hierzu ist ein aktives Messverfahren entwickelt worden, um das räumliche und zeitliche Verhalten der YouTube-Serverauswahl bestimmen zu können. In zwei Messstudien wird die Serverauswahl in deutschen und europäischen ISP-Netzen untersucht. Auf Basis dieser Studien wird ein Verkehrsmodell entwickelt, welches die durch Änderungen der YouTube-Serverauswahl verursachten Verkehrslastverschiebungen abbildet. Das Verkehrsmodell wiederum bildet die Grundlage für die Bestimmung optimaler Routen im ISP-Netz, welche hohe Robustheit gegenüber CDN-bedingte Verkehrslastverschiebungen aufweisen (Alpha-robuste Routingoptimierung). Für die Lösung des robusten Routing-Optimierungsproblems wird ein iteratives Verfahren entwickelt sowie eine kompakte Reformulierung vorgestellt. Die Leistungsfähigkeit des Alpha-robusten Routings wird anhand von drei Beispielnetztopologien untersucht. Das neue Verfahren wird mit alternativen robusten Routingverfahren und einem nicht-robusten Verfahren verglichen. Neben der robusten Routingoptimierung werden in der Arbeit drei weitere Ideen für nicht-kooperative Methoden vorgestellt (BGP-, IP-Präix- und DNS-basierte Methode), um CDN-bedingten Verkehrslastverschiebungen entgegenzuwirken.

Universiẗat, Diss.--Hohenheim, 1999.

Die Dissertationsschrift untersucht die Interaktion zwischen Strom- und Wärmemarkt mit einem besonderen Fokus auf Wärmepumpen und Wärmenetzen. Vor dem Hintergrund des steigenden Ausbaus erneuerbarer Energien und der langfristigen Klimaziele stellt sich dabei die Frage der Wirkung, welche die Kopplung von Strom- und Wärmemarkt auf die Reduktion der CO2-Emissionen, die Energiesystemkosten und die Integration der erneuerbaren Energien hat. Zur Beantwortung der Forschungsfrage wird das lineare Optimierungsmodell Enertile um zwei Wärmemodule zur Berücksichtigung von Wärmepumpen und Wärmenetzen erweitert. Im Unterschied zu anderen Modellen wird in der Implementierung für diese Arbeit der Ausbau und der Einsatz der erneuerbaren Energien, der KWK und der weiteren fossilen Kraftwerkskapazitäten gleichzeitig optimiert, wodurch eine Analyse der Wechselwirkungen zwischen dem Ausbau erneuerbarer Energien und der Kopplung von Strom- und Wärmemarkt möglich ist. Die in dieser Arbeit vorgenommene modellgestützte Analyse zeigt die große Bedeutung der Interaktion zwischen Strom- und Wärmemarkt. Im Rahmen einer langfristigen Dekarbonisierung der Energieversorgung durch einen verstärkten Ausbau von erneuerbaren Energien ergeben sich sowohl Chancen als auch Herausforderungen für die Interaktion zwischen Strom- und Wärmemarkt. Die Modellierung der Wärmepumpen zeigt für den gesamten Zeitraum ab 2020 deutlich geringere spezifische CO2-Emissionen gegenüber der Wärmeerzeugung in modernen Gasbrennwertkesseln. Die Ergebnisse zeigen auch, dass bivalente Systeme – die kombinierte Nutzung verschiedener Wärmeerzeugungstechnologien wie beispielsweise KWK, Gasheizkessel und Elektroheizkessel – vor dem Hintergrund der Umstrukturierung des Stromsektors eine wichtige Rolle spielen. Langfristig stellt die flexible Wärmebereistellung durch elektrische Heizungstechnologien insbesondere bei hohen Anteilen erneuerbarer Energien eine kostengünstige und CO2-arme Alternative zur fossilen Wärmeerzeugung dar.:1 Einleitung 1 1.1 Ausgangslage 1 1.2 Problemstellung 3 1.3 Zielsetzung und Vorgehen 4 2 Rahmenbedingungen auf dem Strom- und Wärmemarkt in Deutschland 7 2.1 Rahmenbedingungen auf dem Strommarkt 7 2.2 Rahmenbedingungen auf dem Wärmemarkt 12 2.3 Schlussfolgerungen für diese Arbeit 16 3 Modellierung der Interaktionen von Strom- und Wärmemarkt 17 3.1 Stand der Forschung und Anforderungen an das Modell 17 3.2 Modelle zur Untersuchung von Strom- und Wärmemarkt 18 3.3 Stromsystemoptimierung Enertile 21 3.3.1 Eingangsdaten und Ergebnisse 23 3.3.2 Problemformulierung 24 3.4 Modellerweiterung zur Integration des Wärmemarktes 26 3.4.1 Wärmepumpen 26 3.4.2 Wärmenetze 32 4 Unsicherheiten in Energiesystemmodellen 42 4.1 Unsicherheiten im Rahmen dieser Arbeit 42 4.2 Methoden zum Umgang mit Unsicherheiten in Energiesystemmodellen 43 4.3 Szenarienentwicklung und Sensitivitäten 47 5 Definition von Szenarien zur Analyse der Wechselwirkungen zwischen Strom- und Wärmemarkt 50 5.1 Szenarienübersicht 50 5.2 Zentrale Annahmen 51 5.3 Strommarkt 56 5.3.1 Erneuerbare Energien 56 5.3.2 Konventionelle Kraftwerke 57 5.3.3 Stromnachfrage 59 5.4 Wärmenetze 59 5.5 Wärmepumpen 63 5.6 Sensitivitäten 65 5.7 Kritische Reflexion der Annahmen 66 6 Modellgestützte Analyse der Wechselwirkungen zwischen Strom- und Wärmemarkt 68 6.1 Einfluss auf die CO2-Emissionen 69 6.1.1 Strommarkt 69 6.1.2 Wärmepumpen 72 6.1.3 Wärmenetze 77 6.2 Entwicklung des Kraftwerksparks und des Erzeugungsmixes 82 6.2.1 Strommarkt 82 6.2.2 Wärmepumpen 95 6.2.3 Wärmenetze 106 6.2.4 Integration erneuerbarer Energien auf dem Strommarkt 128 6.3 Änderung der Systemkosten durch die Kopplung von Strom- und Wärmemarkt 131 6.3.1 Kosten der Stromerzeugung 132 6.3.2 Kosten der Wärmeerzeugung in Wärmepumpen 134 6.3.3 Kosten der Wärmeerzeugung in Wärmenetze 136 6.4 Zusammenfassung der Szenarienanalyse 140 6.4.1 Einfluss der Kopplung von Strom- und Wärmemarkt bei ambitionierten Klimaschutz 140 6.4.2 Einfluss der Kopplung von Strom- und Wärmemarkt bei mäßigem Klimaschutz 141 7 Sensitivitäten 142 7.1 Stabile Brennstoffpreise 142 7.2 Potentiale von erneuerbaren Energien 145 7.3 Isolierte Effekte von Elektroheizkesseln und KWK 148 7.3.1 Keine KWK 148 7.3.2 Keine Elektroheizkessel 150 7.4 Hohe Flexibilität der Wärmepumpen 151 7.5 Zusammenfassung Sensitivitäten 152 8 Zusammenfassung 154 8.1 Motivation und Forschungsfrage 154 8.2 Methodisches Vorgehen 154 8.3 Ergebnisse 155 8.4 Schlussfolgerungen und kritische Reflektion 156 8.4.1 Szenarienanalyse 156 8.4.2 Methodik 157 8.4.3 Ausblick 159

No description available.

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