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.

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.