Search

With the increasing demand on train trips, shortages of train services are experienced, especially in the parts of the world where urban development is fierce. Operational measures to improve railway capacity are considered the most economically viable way to tackle the issue. Though of central importance in railway operations, the problem of capacity analysis was never perfectly solved. The famous UIC compression method suggested by the International Union of Railway was studied by its various related aspects, and several shortcomings have been laid bare by publications known to the community. The analytic method adopted in the SLS software family (which is officially used by Deutsche Bahn AG) produces results with and without a ready timetable. However, it is noteworthy that the result is imperfect, which can be told from the fact that two timetables the clearly differ result in the same value of capacity usage. This is due to over-simplification in its defined computational procedure. Stemming from these facts, this thesis intends to pool efforts into improving the method for railway capacity analysis. Firstly, the UIC compression and SLS methods are briefly analyzed from a methodological perspective, which gives the insight on their approximating nature. Secondly, the methods to compute the separation of train paths are studied, and the concrete computational details are given and analyzed, since this is unavoidable for any method to give a complete description of infrastructure utilization by train operations. Then, it becomes clear that the calculation process of UIC compression and SLS methods amounts to formulate a graph in the shorter sections resulting from their respective dividing procedures. In this regard, we see that such a graph for shorter section is a subgraph of the whole section of interest. Finally, heavily capitalizing “Zacken-Lücken-Problem”, an algorithm is given to compute all the required details to formulate such a graph of the whole infrastructure, which is called infrastructure capacity utilization description (ICUD). Based on the produced compressed timetable graph, the consumed capacity is formulated as the length of the critical path of this graph. This gives a graph-theoretic improvement to the existing methods for railway capacity analysis as it includes more details omitted by the existing methods. As previous study of ICUD gives rather full account on the timetable elements when describing the compressed timetable graph, a natural tendency is to study the impact of timetable elements on the ICUD graph or the consumed capacity. Since the optimization problem of train timetable relies as a matter of fact on studying the impact of combinatorial effect of the timetable elements—a similarity of decision and optimization version of computational problems in the theory of computation. Therefore, this thesis carries further to study the impact of timetable element on railway capacity. The general method is based on detecting difference in the critical path when changing the timetable element in it. Since stop pattern has an immerse impact of the outcome consumed capacity and has in fact taken the major portion of consumed capacity in intercity railway networks. This thesis takes stop plan as an example and studies its impact. The main reasoning is that altering a stop plan potentially changes the ICUD graph, which further changes the critical path and results in a different length. This reasoning is obeyed in the main texts. As the same reason per studying the impact of stop plan as example, this thesis further considers the problem of stop planning of intercity railway train scheduling, which is gaining more practical importance due to the increasing operational importance of intercity trains. For intercity lines, all trains operate in the same speed curve within one line section but heterogenous stop pattern. The study on infrastructure capacity utilization description (ICUD) offers the methodology for computing the impact of timetable element. With this knowledge, the case study in chapter 4 made use of so-called “transfer”—a natural idea—to alleviate the capacity consumption for railway infrastructure, and this chapter further evolves this idea for addressing practical scheduling problems, namely the problems of train stop planning for minimal consumed capacity (SPfMCC). We first formulate SPfMCC as a mixed integer linear programming (MILP) model and reformulate it by ICUD as a non-regular 0,1 integer program that is subject to train stop specifications and minimizes the consumed capacity. The consumed capacity, as the objective function, is represented by a signed sum of elements in the critical path of ICUD. Then, this model is decomposed into a 0,1-integer linear programming model of totally unimodular coefficient matrix and a problem of computing the impacts of stop plans. In this way, the method developed in chapter 4 can be directly applied to formalize a combinatorial algorithm based on the one-to-one stop transfer between different trains. Theoretical analysis and practical computations show that this algorithm returns an improved feasible solution in polynomial time. In addition, we consider two related problems of the similar kind—extensions one and two. Extension one predefines the number of stops at unspecified stations for specified trains, and extension two only defines the numbers of trains to stop at unspecified stations. Eventually, the main work of this thesis is summarized, and the leading research questions are answered, and some future research directions revealed by this study are discussed., Mit der steigenden Nachfrage nach Eisenbahnreisen kommt es vor allem in den Teilen der Welt, in denen die Stadtentwicklung stark voranschreitet, zu Engpässen im Eisenbahnverkehr. Betriebliche Maßnahmen zur Verbesserung der Eisenbahnkapazität gelten als die wirtschaftlich tragfähigste Art, das Problem anzugehen. Obwohl das Problem der Kapazitätsanalyse im Eisenbahnbetrieb von zentraler Bedeutung ist, wurde es nie vollständig gelöst. Das berühmte UIC-Komprimierungsverfahren, das vom Internationalen Eisenbahnverband vorgeschlagen wurde, wurde unter seinen verschiedenen verwandten Aspekten untersucht, und mehrere Mängel wurden durch Veröffentlichungen, die der Eisenbahnfachwelt bekannt sind, offengelegt. Die in der SLS-Software (die offiziell von der Deutschen Bahn AG verwendet wird) übernommene Analysemethode liefert Ergebnisse mit und ohne fertigen Fahrplan. Das Ergebnis ist jedoch unvollkommen ist, was daran zu erkennen ist, dass zwei deutlich unterschiedliche Fahrpläne den gleichen Wert der Kapazitätsauslastung ergeben. Dies ist auf eine zu starke Vereinfachung im definierten Berechnungsverfahren zurückzuführen. Ausgehend von diesen Fakten beabsichtigt diese Arbeit, die Bemühungen zur Verbesserung der Methode zur Eisenbahnkapazitätsanalyse zu bündeln. Zuerst werden die UIC-Komprimierungs- und SLS-Methoden kurz aus methodologischer Sicht analysiert, was einen Einblick in ihre Annäherungscharakteristik gibt. Zweitens werden die Methoden zur Berechnung der Trassentrennung untersucht und die konkreten Berechnungsdetails angegeben und analysiert, da dies für jede Methode zur vollständigen Beschreibung der Infrastrukturnutzung durch den Zugbetrieb unumgänglich ist. Dann wird deutlich, dass der Berechnungsprozess der UIC-Kompressions- und SLS-Methode darauf hinausläuft, in den kürzeren Abschnitten, die sich aus ihren jeweiligen Teilungsverfahren ergeben, eine Grafik zu formulieren. Hier wird klar, dass ein solcher Graph für einen kürzeren Abschnitt ein Teilgraph des gesamten analysierten Abschnitts ist. Schließlich, wird in Anlehnung an das „Zacken-Lücken-Problem“, ein Algorithmus angegeben, um alle erforderlichen Details zu berechnen, um einen solchen Graphen der gesamten Infrastruktur zu formulieren, der als Infrastructure Capacity Usage Description (ICUD) bezeichnet wird. Basierend auf dem erstellten komprimierten Fahrplangraphen wird die verbrauchte Kapazität als Länge des kritischen Pfads dieses Graphen formuliert. Dies stellt eine graphentheoretische Verbesserung der bestehenden Verfahren zur Eisenbahnkapazitätsanalyse, da dieses mehr Details enthält, die von den bestehenden Verfahren nicht erkannt werden. Da die bisherige ICUD-Studie die Fahrplanelemente die Fahrplanelemente bei der Beschreibung des komprimierten Fahrplangraphen ziemlich umfassend berücksichtigt, besteht eine natürliche Tendenz darin, die Auswirkungen von Fahrplanelementen auf das ICUD-Diagramm oder die verbrauchte Kapazität zu untersuchen. Da das Optimierungsproblem des Zugfahrplans tatsächlich auf der Untersuchung der Auswirkungen des kombinatorischen Effekts der Fahrplanelemente beruht eine Ähnlichkeit der Entscheidungs- und Optimierungsversion von Berechnungsproblemen in der Berechnungstheorie. Daher geht diese Arbeit weiter auf die Untersuchung der Auswirkungen von Fahrplanelementen auf die Eisenbahnkapazität ein. Das allgemeine Verfahren basiert auf dem Erfassen von Unterschieden im kritischen Pfad, wenn das Fahrplanelement darin geändert wird. Da das Haltemuster einen immersiven Einfluss auf das Ergebnis der verbrauchten Kapazität hat und tatsächlich den größten Teil der verbrauchten Kapazität in Intercity-Eisenbahnnetzen eingenommen hat. Diese Dissertation nimmt das Beispiel des Zughaltens und untersucht seine Auswirkungen. Die Hauptargumentation ist, dass die Änderung eines Stoppplans möglicherweise den ICUD-Graphen ändert, was den kritischen Pfad weiter ändert und zu einer anderen Länge führt. Dieser Argumentation wird in den Haupttexten gefolgt. Aus dem gleichen Grund, um beispielhaft die Auswirkungen von Haltestellenplänen zu untersuchen, befasst sich diese Arbeit weiter mit der Problematik an der Planung von Halten in Intercity-Bahnfahrplänen, die aufgrund der zunehmenden betrieblichen Bedeutung von Intercity-Zügen an praktischer Bedeutung gewinnen. Bei Intercity-Linien verkehren alle Züge innerhalb eines Streckenabschnitts in der gleichen Geschwindigkeitskurve, aber mit heterogenen Haltemustern. Die Studie zur Beschreibung der Kapazitätsauslastung der Infrastruktur (ICUD) bietet die Methodik zur Berechnung der Auswirkungen von Fahrplanelementen. Mit diesem Wissen nutzte die Fallstudie in Kapitel 4 den sogenannten „Transfer“ – eine natürliche Idee – um den Kapazitätsverbrauch für die Eisenbahninfrastruktur zu verringern, und dieses Kapitel entwickelt diese Idee weiter, um praktische Fahrplanprobleme anzugehen, nämlich die Probleme von Zughalteplanung für minimal verbrauchte Kapazität (SPfMCC). Zunächst wird SPfMCC als gemischtes ganzzahliges lineares Programmiermodell (MILP) formuliert und von ICUD zu einem nicht reguläres 0,1-ganzzahliges Programm umformuliert, das Zughaltespezifikationen unterliegt und die verbrauchte Kapazität minimiert. Die verbrauchte Kapazität als Zielfunktion wird durch eine vorzeichenbehaftete Summe von Elementen im kritischen Pfad von ICUD dargestellt. Dann wird dieses Modell in ein 0,1-ganzzahliges lineares Programmiermodell einer vollständig unimodularen Koeffizientenmatrix und ein Problem zur Berechnung der Auswirkungen von Halten zerlegt. Auf diese Weise kann die in Kapitel 4 entwickelte Methode direkt angewendet werden, um einen kombinatorischen Algorithmus zu formalisieren, der auf dem Eins-zu-eins-Haltestellentransfer zwischen verschiedenen Zügen basiert. Theoretische Analysen und praktische Berechnungen zeigen, dass dieser Algorithmus eine verbesserte zulässige Lösung in polynomieller Zeit liefert. Außerdem betrachten wir zwei verwandte Probleme ähnlicher Art – die Erweiterungen eins und zwei. Erweiterung eins definiert die Anzahl der Haltestellen an nicht spezifizierten Bahnhöfen für spezifizierte Züge, und Erweiterung zwei definiert nur die Anzahl der Züge, die an nicht spezifizierten Stationen halten sollen. Abschließend wird die Hauptarbeit dieser Dissertation zusammengefasst, und die führenden Forschungsfragen werden beantwortet, und einige zukünftige Forschungsrichtungen, die sich aus dieser Studie ergeben, werden diskutiert.