Please use this identifier to cite or link to this item: http://dx.doi.org/10.14279/depositonce-3124
Main Title: Railway Track Allocation: Models and Algorithms
Translated Title: Trassenallokation im Schienenverkehr: Modelle und Algorithmen
Author(s): Schlechte, Thomas
Advisor(s): Grötschel, Martin
Granting Institution: Technische Universität Berlin, Fakultät II - Mathematik und Naturwissenschaften
Type: Doctoral Thesis
Language: English
Language Code: en
Abstract: Diese Arbeit befasst sich mit der mathematischen Optimierung zur effizienten Nutzung der Eisenbahninfrastruktur. Wir behandeln die optimale Allokation der zur Verfügung stehenden Kapazität eines Eisenbahnschienennetzes - das Trassenallokationsproblem. Das Trassenallokationsproblem stellt eine wesentliche Herausforderung für jedes Bahnunternehmen dar, unabhängig, ob ein freier Markt, ein privates Monopol, oder ein öffentliches Monopol vorherrscht. Die Planung und der Betrieb eines Schienenverkehrssystems ist extrem schwierig aufgrund der kombinatorischen Komplexität der zugrundeliegenden diskreten Optimierungsprobleme, der technischen Besonderheiten, und der immensen Größen der Probleminstanzen. Mathematische Modelle und Optimierungstechniken können zu enormen Nutzen führen, sowohl für die Kunden der Bahn als auch für die Betreiber, z.B. in Bezug auf Kosteneinsparungen und Verbesserungen der Servicequalität.Wir lösen diese Herausforderung durch die Entwicklung neuartiger mathematischer Modelle und der dazughörigen innovativen algorithmischen Lösungsmethoden für sehr große Instanzen. Dadurch waren wir erstmals in der Lage zuverlässige ösungen für Instanzen der realen Welt, d.h. für den Simplon Korridor in der Schweiz, zu produzieren. Der erste Teil beschäftigt sich mit der Modellierung des Schienenbahnsystems unter Berücksichtigung von Kapazität und Ressourcen. Kapazität im Schienenverkehr hat grundsätzlich zwei Dimensionen, eine räumliche, welche der physischen Infrastruktur entspricht, und eine zeitliche, die sich auf die Zugbewegungen innerhalb dieser bezieht, d.h. die Belegung- und Blockierungszeiten. Sicherungssysteme im Schienenverkehr beruhen überall auf der Welt auf demselben Prinzip. Ein Zug muss Blöcke der Infrastruktur für die Durchfahrt reservieren. Das gleichzeitige Belegen eines Blockes durch zwei Züge wird Blockkonflikt genannt. Um eine konfliktfreie Belegung zu erreichen, beinhalten Modelle zur Kapazität im Schienenverkehr daher die Definition und Berechnung von angemessenen Fahrzeiten und dementsprechenden Reservierungs- oder Blockierungszeiten. Im zweiten und Hauptteil der Dissertation wird das Problem des Bestimmens optimaler Trassenallokationen für makroskopische Bahnmodelle betrachtet. Ein Literaturüberblick zu verwandten Problemen wird gegeben. Für das Trassenallokationsproblem wird ein graphentheoretisches Modell entwickelt, in dem optimale ösungen als maximal gewichtete konfliktfreie Menge von Pfaden in speziellen zeitexpandierten Graphen dargestellt werden können. Des Weiteren erreichen wir wesentliche Fortschritte beim Lösen von Trassenallokationsprobleme durch zwei Hauptbeiträge - die Entwickling einer neuartigen Modellformulierung des makroskopischen Trassenallokationsproblemes und algorithmische Verbesserungen basierend auf der Nutzung des Bündelverfahrens. Den Höhepunkt bilden Resultate für Praxisszenarios zum Simplon Korridor in der Schweiz. Nach bestem Wissen des Autors und bestätigt durch zahlreiche Eisenbahnpraktiker ist dies das erste Mal, dass auf einer makroskopischen Ebene automatisch erstellte Trassenallokationen die Bedingungen des ursprünglichen mikroskopischen Modells erfüllen und der Evaluierung innerhalb des mikroskopischen Simulationstools OpenTrack standhalten. Das dokumentiert den Erfolg unseres Ansatzes und den Nutzen and die Anwendbarkeit mathematischer Optimierung zur Allokation von Trassen im Schienenverkehr.
This thesis is about mathematical optimization for the efficient use of railway infrastructure. We address the optimal allocation of the available railway track capacity the track allocation problem. This track allocation problem is a major challenge for a railway company, independent of whether a free market, a private monopoly, or a public monopoly is given. Planning and operating railway transportation systems is extremely hard due to the combinatorial complexity of the underlying discrete optimization problems, the technical intricacies, and the immense sizes of the problem instances. Mathematical models and optimization techniques can result in huge gains for both railway customers and operators, e.g., in terms of cost reductions or service quality improvements. We tackle this challenge by developing novel mathematical models and associated innovative algorithmic solution methods for large scale instances. This allows us to produce for the first time reliable solutions for a real world instance, i.e., the Simplon corridor in Switzerland. The opening chapter gives a comprehensive overview on railway planning problems. This provides insights into the regulatory and technical framework, it discusses the interaction of several planning steps, and identifies optimization potentials in railway transportation. The remainder of the thesis is comprised of two major parts. The first part is concerned with modeling railway systems to allow for resource and capacity analysis. Railway capacity has basically two dimensions, a space dimension which are the physical infrastructure elements as well as a time dimension that refers to the train movements, i.e., occupation or blocking times, on the physical infrastructure. Railway safety systems operate on the same principle all over the world. A train has to reserve infrastructure blocks for some time to pass through. Two trains reserving the same block of the infrastructure within the same point in time is called block conflict. Therefore, models for railway capacity involve the definition and calculation of reasonable running and associated reservation and blocking times to allow for a conflict free allocation. In the second and main part of the thesis, the optimal track allocation problem for macroscopic models of the railway system is considered. The literature for related problems is surveyed. A graph-theoretic model for the track allocation problem is developed. In that model optimal track allocations correspond to conflict-free paths in special time-expanded graphs. Furthermore, we made considerable progress on solving track allocation problems by two main features - a novel modeling approach for the macroscopic track allocation problem and algorithmic improvements based on the utilization of the bundle method. Finally, we go back to practice and present in the last chapter several case studies using the tools netcast and tsopt. We provide a computational comparison of our new models and standard packing models used in the literature. Our computational experience indicates that our approach, i.e., configuration models'', outperforms other models. Moreover, the rapid branching heuristic and the bundle method enable us to produce high quality solutions for very large scale instances, which has not been possible before. In addition, we present results for a theoretical and rather visionary auction framework for track allocation. We discuss several auction design questions and analyze experiments of various auction simulations. The highlights are results for the Simplon corridor in Switzerland. We optimized the train traffic through this tunnel using our models and software tools. To the best knowledge of the author and confirmed by several railway practitioners this was the first time that fully automatically produced track allocations on a macroscopic scale fulfill the requirements of the originating microscopic model, withstand the evaluation in the microscopic simulation tool OpenTrack, and exploit the infrastructure capacity. This documents the success of our approach in practice and the usefulness and applicability of mathematical optimization to railway track allocation.
URI: urn:nbn:de:kobv:83-opus-34272
http://depositonce.tu-berlin.de/handle/11303/3421
http://dx.doi.org/10.14279/depositonce-3124
Exam Date: 23-Dec-2011
Issue Date: 15-Feb-2012
Date Available: 15-Feb-2012
DDC Class: 510 Mathematik
Subject(s): Linear ganzzahlige Optimierung
Netzwerkaggregation
Trassenallokation
Large-scale integer programming
Network aggregation
Railway track allocation
Usage rights: Terms of German Copyright Law
Appears in Collections:Institut für Mathematik » Publications

Files in This Item:
File Description SizeFormat 
Dokument_49.pdf4.37 MBAdobe PDFThumbnail
View/Open


Items in DepositOnce are protected by copyright, with all rights reserved, unless otherwise indicated.