Rail track operators have traditionally used manual methods to construct train timetables. Creating a timetable can take several weeks, and so the process usually stops once the first feasible timetable has been found. It is suspected that this timetable is often far from optimal. Existing methods schedule track maintenance once the best train timetable has been determined and allow little or no adjustments to the timetable. This approach almost certainly produces suboptimal integrated solutions since the track maintenance schedule is developed with the imposition of the previously constructed train timetable. The research in this thesis considers operationally feasible methods to produce integrated train timetables and track maintenance schedules so that, when evaluated according to key performance criteria, the overall schedule is the best possible. This research was carried out as part of the Cooperative Research Centre for Railway Engineering and Technologies. We developed a method that uses a local search meta-heuristic called 'problem space search'. A fast dispatch heuristic repeatedly selects and moves a track possessor (train or maintenance task) through the network; this results in a single integrated schedule. This technique generates a collection of alternative feasible schedules by applying the dispatch heuristic to different sets of randomly perturbed data. The quality of the schedules is then evaluated. Thousands of feasible solutions can be found within minutes. We also formulated an integer programming model that selects a path for each train and maintenance task from a set of alternatives. If all possible paths are considered, then the best schedule found is guaranteed to be optimal. To reduce the size of the model, we explored a reduction technique called 'branch and price'. The method works on small example problems where paths are selected from a predetermined set, but the computation time and memory requirements mean that the method is not suitable for realistic problems. The main advantages of the problem space search method are generality and speed. We are able to model the operations of a variety of rail networks due to the representation of the problem. The generated schedules can be ranked with a user-defined objective measure. The speed at which we produce a range of feasible integrated schedules allows the method to be used in an operational setting, both to create schedules and to test different scenarios. A comparison with simulated current practice on a range of test data sets reveals improvements in total delay of up to 22%.

Rail track operators have traditionally used manual methods to construct train timetables. Creating a timetable can take several weeks, and so the process usually stops once the first feasible timetable has been found. It is suspected that this timetable is often far from optimal. Existing methods schedule track maintenance once the best train timetable has been determined and allow little or no adjustments to the timetable. This approach almost certainly produces suboptimal integrated solutions since the track maintenance schedule is developed with the imposition of the previously constructed train timetable. The research in this thesis considers operationally feasible methods to produce integrated train timetables and track maintenance schedules so that, when evaluated according to key performance criteria, the overall schedule is the best possible. This research was carried out as part of the Cooperative Research Centre for Railway Engineering and Technologies. We developed a method that uses a local search meta-heuristic called 'problem space search'. A fast dispatch heuristic repeatedly selects and moves a track possessor (train or maintenance task) through the network; this results in a single integrated schedule. This technique generates a collection of alternative feasible schedules by applying the dispatch heuristic to different sets of randomly perturbed data. The quality of the schedules is then evaluated. Thousands of feasible solutions can be found within minutes. We also formulated an integer programming model that selects a path for each train and maintenance task from a set of alternatives. If all possible paths are considered, then the best schedule found is guaranteed to be optimal. To reduce the size of the model, we explored a reduction technique called 'branch and price'. The method works on small example problems where paths are selected from a predetermined set, but the computation time and memory requirements mean that the method is not suitable for realistic problems. The main advantages of the problem space search method are generality and speed. We are able to model the operations of a variety of rail networks due to the representation of the problem. The generated schedules can be ranked with a user-defined objective measure. The speed at which we produce a range of feasible integrated schedules allows the method to be used in an operational setting, both to create schedules and to test different scenarios. A comparison with simulated current practice on a range of test data sets reveals improvements in total delay of up to 22%.

La plupart des systèmes ferroviaires subissent une demande croissante de capacité. Pour y faire face, il faut construire de nouvelles infrastructures ou exploiter plus efficacement celles existantes, notamment en définissant des grilles horaires optimisées. Dans la littérature, la plupart des approches de construction des grilles sont basées sur des représentations macroscopiques de l'infrastructure, ce qui peut conduireà des solutions infaisables ou inefficaces. En revanche, les approches microscopiques reposent sur une modélisation réaliste du système ferroviaire, ce qui garantit la faisabilité et l'efficacité des résultats. Néanmoins, en raison de leur complexité, l'utilisation de ces approches est généralement limitée à une seule gare. Malgré l'optimisation de la grille horaire, les travaux de maintenance peuvent avoir un fort impact sur les circulations des trains. En présence de maintenances, il peut donc être nécessaire de redéfinir la grille horaire pour assurer une exploitation efficace de la capacité. Nous présentons deux contributions principales sous forme de deux approches microscopiques : une pour la conception de grilles horaires et l'autre pour leur redéfinition en cas de maintenance. La deuxième est la première approche microscopique qui apparaît dans la littérature pour aborder ce problème tout en considérant des aspects comme les limitations temporaires de vitesse. Nous démontrons la validité de nos approches et leur applicabilité dans des scénarios réels. De plus, nous montrons que les approches microscopiques peuvent être utilisées pour traiter des zones de l'infrastructure contenant plusieurs gares. / Most railway systems experience a growing demand of railway capacity. To face this demand, either new infrastructure must be built or a more efficient exploitation of the existing one must be attained. Timetables play a determinant role in the efficient capacity exploitation. Most timetabling approaches in the literature are based on macroscopic representations of the infrastructure. This may lead to inefficient and in some cases, impractical solutions. Instead, microscopic approaches are based on more realistic modelling of the elements of the railway system. This guarantees the feasibility of the timetables while promoting an efficient capacity exploitation. However, due to their complexity, the scope of microscopic approaches is typically restricted to main stations. Despite the optimization of timetables, the performance of infrastructure maintenance may severely impact the trains' circulations in the network. Therefore, the timetable may have to be rearranged to ensure an efficient capacity exploitation. We present two main contributions in this thesis: first, a microscopic approach for timetable design. Second, a microscopic approach for timetable rearrangement to cope with maintenance. This is the first microscopic approach in the literature to tackle this problem while also considering specific aspects as temporary speed limitations. After a thorough experimental analysis, we demonstrate the validity of our approaches and their practical applicability in real life scenarios. In particular, we show that microscopic approaches can be used to tackle large areas of the infrastructure, including several stations.