Railway Track Allocation: Models and Algorithms

dc.contributor.advisorGrötschel, Martinen
dc.contributor.authorSchlechte, Thomasen
dc.contributor.grantorTechnische Universität Berlin, Fakultät II - Mathematik und Naturwissenschaftenen
dc.date.accepted2011-12-23
dc.date.accessioned2015-11-20T21:07:43Z
dc.date.available2012-02-15T12:00:00Z
dc.date.issued2012-02-15
dc.date.submitted2012-02-15
dc.description.abstractDiese 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.de
dc.description.abstractThis 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.en
dc.identifier.uriurn:nbn:de:kobv:83-opus-34272
dc.identifier.urihttps://depositonce.tu-berlin.de/handle/11303/3421
dc.identifier.urihttp://dx.doi.org/10.14279/depositonce-3124
dc.languageEnglishen
dc.language.isoenen
dc.rights.urihttp://rightsstatements.org/vocab/InC/1.0/en
dc.subject.ddc510 Mathematiken
dc.subject.otherLinear ganzzahlige Optimierungde
dc.subject.otherNetzwerkaggregationde
dc.subject.otherTrassenallokationde
dc.subject.otherLarge-scale integer programmingen
dc.subject.otherNetwork aggregationen
dc.subject.otherRailway track allocationen
dc.titleRailway Track Allocation: Models and Algorithmsen
dc.title.translatedTrassenallokation im Schienenverkehr: Modelle und Algorithmende
dc.typeDoctoral Thesisen
dc.type.versionpublishedVersionen
tub.accessrights.dnbfree*
tub.affiliationFak. 2 Mathematik und Naturwissenschaften::Inst. Mathematikde
tub.affiliation.facultyFak. 2 Mathematik und Naturwissenschaftende
tub.affiliation.instituteInst. Mathematikde
tub.identifier.opus33427
tub.identifier.opus43240
tub.publisher.universityorinstitutionTechnische Universität Berlinen

Files

Original bundle
Now showing 1 - 1 of 1
Loading…
Thumbnail Image
Name:
Dokument_49.pdf
Size:
4.27 MB
Format:
Adobe Portable Document Format

Collections