Optimization of Schedules with Heterogeneous Train Structure in Plan-ning of Railway Lines E-Book

Hyoung June Kim

• Herausgeber: Books on Demand
• Kategorie: Wissenschaft und neue Technologien
• Serie: Neues verkehrswissenschaftliches Journal
• Sprache: Englisch

Seitenzahl: 156

Veröffentlichungsjahr: 2020

Beschreibung

One of the most important things to consider before constructing a railway is the train operating program. However, the analysis of the operating program based train schedule in the railway planning stage is carried out mainly on the basis of the intuitive experiences of the planner, and the optimization of the train schedule under various conditions is not properly considered. This study analyzes the optimization of heterogeneous train scheduling structures with minimizing the weighted scheduled waiting time and with the decision of Subsidiary Main Track (SMT) for overtaking of high-speed trains on the railway line. As a way for analyzing the Optimal Train Schedule (OTS) under constraint conditions, the genetic algorithm is used. The genetic algorithm is widely applied to various optimization and decision-making problems in engineering, natural sciences, business administration, and social sciences. The proposed method can examine train schedules for more scenarios, apply quantitative evaluation criteria, and review concrete infrastructures in comparison to the existing empirical method used in South Korea.

Leseprobe

Preface

When designing railway infrastructure, it is frequently necessary to derive an initial, rough operating program based on traffic needs that acts as the basis for infrastructure dimensioning and takes into account defined, operational quality requirements. This process is described as capacity research and in recent decades, a variety of capacity research methods and procedures has been developed that are also successful in practical implementation. In particular, analytical methods used for investigating areas of homogeneous infrastructure, and simulation methods used for complex network structures have proved their worth.

In Germany and Europe, it is now rare to build new, longer railway lines to be used for mixed traffic with both slower and faster trains. However, in other parts of the world such as Asia, it is still an important component in both national and transnational transport system design. In such situations, the application of analytical methods is very limited because the results are extremely aggregated. When using simulation methods, numerous, detailed assumptions have to be made during the preliminary planning phase. A considerable amount of work is then needed to vary and optimize these assumptions within the framework of the capacity research.

In this dissertation, Mr. Kim develops a hands-on approach to determining optimized timetables based on a rough operating program for longer railway lines with mixed traffic. His approach, which requires a manageable amount of work, yields sufficiently detailed results that can also be used to draw conclusions about the proper arrangement of sidings.

The main research result of this work is a new, genetic procedure based on heuristic methods for the optimized design of an operating program on longer, mixed traffic railway lines. The results developed in this dissertation for optimizing timetables, especially for longer railway lines, based on a rough operating program and the derivable requirement-based arrangement of sidings are a considerable scientific contribution to the efficient planning of railway operations. The results not only close a gap between established analytical and simulation methods in railway operational science, but also have a direct relevance for the real design of railway systems.

Stuttgart, October 2019 Ullrich Martin

Dedication

I dedicate this thesis to my lovely wife HyeYeon Shin, who stood beside me with prayers and encouragement to achieve the vision that God showed to me, and to my three children, who sacrificed their needs to help their father complete this doctoral study, and to my parents who always pray for me to accomplish anything I set my mind to.

Acknowledgements

First of all, I give honor and glory to God, who steered me to accomplish this doctoral study.

I would like to express my sincere appreciation to Professor Ullrich Martin, head of the Institute of Railway and Transportation Engineering at the University of Stuttgart and Director of the Institute of Transportation Research at the University of Stuttgart. He gave me the opportunity to earn my Ph.D. degree in Germany and helped me from the beginning of the studies until I finished my thesis by providing me with advice and encouragement. I also thank PD Dr.-Ing. Yong Cui, my supervisor who advised me academically in my writing.

A tremendous thank you to my wife. This study would not have been completed without the prayers and loving support of my dear wife HyeYeon Shin. Finally, I thank my three children HaSeon, IHan and JiHan, who abandoned their needs to help me complete my Ph.D. degree.

Eidesstattliche Erklärung

Hiermit erkläre ich, dass ich diese Arbeit selbständig verfasst und keine anderen als die von mir angegebenen Quellen und Hilfsmittel verwendet habe.

Stuttgart, den 23.10.2019 Hyoung June Kim

Table of Contents

List of Figures

List of Tables

Kurzfassung

Abstract

Introduction

Basic Principles of Train Scheduling

2.1 Meaning of Train Scheduling

2.2 Basic Constraints for Train Scheduling

Optimization Methodology

3.1 Theoretical Background

3.2 Genetic Algorithm

Models for Scheduling and Delimitation

4.1 Mathematical Models for Train Scheduling

4.2 Differentiation from Existing Research

Construction of Mathematical Models for Optimization

5.1 Expression of Railway Line

5.2 Mathematical Model

5.2.1 Objective Function

5.2.2 Constraint Function

Optimization Algorithm Modeling

6.1 Methods and Procedures

6.2 Data Structure

6.2.1 Train Schedule Data

6.2.2 Detailed Operation Schedule

6.2.3 Scheduled waiting time

6.2.4 Station

6.3 Structure of Genetic Algorithm on Optimization of Train Schedule

6.3.1 Creation of Population

6.3.2 Fitness Evaluation

6.3.3 Generation of New Population

6.4 The Unified Modeling Language (UML)

6.4.1 Class Diagram

6.4.2 Class Diagram for Structuring the Genetic Algorithm

Case Study Using the Optimization Algorithm

7.1 Applied Railway Line

7.2 Evaluation in Accordance with Target Fitness

7.2.1 Target Fitness of 70

7.2.2 Target Fitness of 65

7.2.3 Target Fitness of 60

7.2.4 Target Fitness of 55

7.3 Analysis Results

Summary, Conclusion and Further Research

Glossary

Bibliography

List of Abbreviations

List of Variables

Appendix I: The Detailed Data of Each Target Fitness

Appendix II: Timetable for the Optimal Train Schedule and Traffic Diagram

List of Figures

Figure 1: Railway Planning Process (source: Zimmermann and Lindner 2003; Liebchen and Möhring 2007; Lusby et al. 2011)

Figure 2: Structure of Capacity Research (source: Cao 2017 and Martin et al. 2012)

Figure 3: The Waiting Time Diagram and Capacity (source: Pachl 2014; Kim et.al. 2017)

Figure 4: Example of a Stopping Station

Figure 5: Classification of Optimization Methods (source: Kim 2017a)

Figure 6 : The Flow Chart on Genetic Algorithm in This Study

Figure 7: The Guaranteed Headway between High-speed train and Low-speed train at a Station

Figure 8: The Case of Stopping Trains Simultaneously at a Station

Figure 9: Blocking time of a Block Section (source: Pachl 2014)

Figure 10: Class Diagram for the Structure of Genetic Algorithm

Figure 11: Layout of Stations for Applied Railway Line

Figure 12: Distribution Chart of Fitness Points for Target Fitness 70

Figure 13: Number of Overtaking on Each Station for Target Fitness of 70

Figure 14: Distribution Chart of Fitness Points for Target Fitness 65

Figure 15: Number of Overtaking on each Station for Target Fitness 65

Figure 16: Distribution Chart of Fitness Points for Target Fitness 60

Figure 17: Number of Overtaking on each Station for Target Fitness 60

Figure 18: Distribution Chart of Fitness Points for Target Fitness 55

Figure 19: Number of Overtaking on each Station for Target Fitness 55

Figure 20: Traffic Diagram of the Optimal Train Schedule (OTS) in this Study

List of Tables

Table 1: Classification of Metaheuristics (source: Kim 2017a)

Table 2: Comparison between Existing Research and This Study

Table 3: The elements of the Class Diagram in this Study (source: Choi 2018; Cao 2017)

Table 4: The abbreviations for the some elements

Table 5: Railway Line Standards and Type of Trains

Table 6: Parameters of Each Train and Train Operation Frequency

Table 7: Number of Train Schedules where the Same Overtaking Station in Target Fitness of 70

Table 8: Fitness Point for 5 Overtaking Stations in Target Fitness 70

Table 9: Number of Train Schedules where the Same Overtaking Station in Target Fitness of 65

Table 10: Fitness Point for 5 Overtaking Stations in Target Fitness of 65

Table 11: Number of Train Schedules where the Same Overtaking Station in Target Fitness of 60

Table 12: Fitness Point for 5 Overtaking Stations in Target Fitness of 60

Table 13: [Number of Train Schedules where the Same Overtaking Station in Target Fitness of 55]

Table 14: Fitness Point for 5 Overtaking Stations in Target Fitness of 55

Table 15: Comparison of the Best fitness for each Target Fitness

Table 16: The Best fitness and Under Restriction of Five Stations that Require Subsidiary Main Tracks (SMTs)

Table 17: The Number of Overtaking and Ratio for Each Station among Analyzed 100 Train Schedules

Table 18: The detailed data of target fitness of 70

Table 19: The detailed data of target fitness of 65

Table 20: The detailed data of target fitness of 60

Table 21: The detailed data of target fitness of 55

Table 22: The detailed timetable of the nearly Optimal Train Schedule (OTS)

Kurzfassung

Aktuell wächst die Möglichkeit einer innerkoreanischen Eisenbahnverbindung, weil das Thema der Eisenbahnverbindung nach China über Sinuiju in Nordkorea bei den südkoreanisch-chinesischen Gipfelgesprächen diskutiert wird. Es wird erwartet, dass nicht nur Hochgeschwindigkeitszüge, sondern auch Güterzüge über Russland und China nach Europa gelangen können. Um diese Erwartung zu erfüllen, ist es notwendig, die alternden Bahnanlagen in Nordkorea zu verbessern. Bei der Planung vor dem Bau der Schienenwege muss jedoch, ausgehend von der verkehrspolitischen Aufgabenstellung, das Betriebsprogramm als Grundlage eines künftigen Fahrplans berücksichtigt werden. Wenn verschiedene Arten von Zügen auf einer Linie betrieben werden, ist eine Räumung der Durchgehenden Hauptgleise von Niedriggeschwindigkeitszügen für das Überholen durch Hochgeschwindigkeitszüge in Abhängigkeit von dem Zeitintervall, der Geschwindigkeit, der Zuglänge und der Entfernung zwischen den Stationen nicht vermeidbar. Die Analyse des auf dem Betriebsprogramm beruhenden Zugfahrplans in der Planungsphase vor dem Bau oder bei der Verbesserung einer Eisenbahninfrastruktur wird jedoch gegenwärtig oftmals noch auf der Grundlage der intuitiven Erfahrungen und Kenntnisse des Planers durchgeführt, und die Optimierung des Zugfahrplans unter verschiedenen Bedingungen wird nur ansatzweise berücksichtigt.

In dieser Studie wurde ein Modell zur Bestimmung eines optimalen Zugfahrplans in der Planungsphase, beim Einsatz dreier Arten von Zügen mit unterschiedlichen Geschwindigkeiten, Betriebsfrequenzen und Halten auf einer Eisenbahnlinie unter Berücksichtigung des Zugfahrplans entwickelt. Die Netzwerkmodelle können je nach Methode in Raum-Zeit-Netzwerk, Raum-Netzwerk und Standort-Zeit- kategorisiert werden. In dieser Arbeit wird ein auf dem Standort-Zeit-Netzwerkansatz beruhendes mathematisches Modell vorgeschlagen, das eine Reihe von Vorteilen hinsichtlich der Verwendbarkeit verschiedener Zielfunktionen und Nebenbedingungen, der Modellskalierbarkeit, einer einfachen Implementierung sowie der Interpretation der Ergebnisse bietet. Da Zugfahrpläne als NP-schweres Problem bekannt sind, dessen Lösung aufgrund einer großen Anzahl von Entscheidungsvariablen sehr oft nicht innerhalb eines angemessenen Zeitraums erreicht werden kann, werden in vielen Studien zur Entwicklung eines Zugfahrplans heuristische Methoden angewendet.

Um die Zeitverzögerung bei der Räumung Durchgehender Hauptgleise von Niedergeschwindigkeitszügen für die Überholung durch Hochgeschwindigkeitszüge zu minimieren und um zu bestimmen, welche Bahnhöfe Überholgleise benötigen, wurden die sich daraus für den Zugfahrplan ergebenden Restriktionen als Nebenbedingungen angenommen, und Methoden, die möglichst viele dieser Nebenbedingungen abbilden können, wurden überprüft.

Im Ergebnis stellte sich heraus, dass ein heuristischer Algorithmus für die hier beabsichtigte Optimierung am besten geeignet ist. Folglich wurden verschiedene heuristische Algorithmen evaluiert und ein genetischer Ansatz wurde für diese Studie aufgrund vielfältiger Vorteile, z.B. der Skalierbarkeit des Modells, der einfachen Integration und Relaxation von Nebenbedingungen sowie der Möglichkeit, verschiedene Nebenbedingungen zu berücksichtigen, ausgewählt. Zur Verifizierung der auf dem entwickelten mathematischen Modell beruhenden Optimierung von Zugfahrplänen wurde der verwendete genetischer Algorithmus auf einer Linie in Südkorea, die sich in der Planungsphase befindet, angewendet.

Der in dieser Arbeit verwendete genetische Algorithmus analysiert zufällig generierte Zugfahrpläne (Chromosomen) über 300 Generationen, und der Zugfahrplan (Chromosom) mit der besten Eignung (kürzeste Verzögerungszeit) wird als optimaler Zugfahrplan (optimale Lösung) erkannt. Im Modell wird eine Analyse hinsichtlich der besten Eignung (beste Fitness) entsprechend eines gewählten Zielwertes, der Anzahl der Räumungen von Durchgehenden Hauptgleisen, die an den jeweiligen Bahnhöfen auftreten, und der Anzahl der Zugfahrpläne mit identischen Überholungsbahnhöfen durchgeführt.

Durch die Optimierung des Zugfahrplans auf einer geplanten Eisenbahnlinie und Festlegung der Überholungsbahnhöfe nach der in dieser Studie vorgeschlagenen Methode ist es möglich, eine objektive Grundlage für die Bahnplanung zu nutzen, statt sich allein auf die subjektive Erfahrung der Planer zu verlassen. Darüber hinaus kann ein so optimierter Zugfahrplan auf der Grundlage der in dieser Studie vorgeschlagenen Methode analysiert wird, kann dies dazu beitragen, die wirtschaftliche und politische Durchführbarkeit des Baus neuer Eisenbahnstrecken zu erreichen.

Abstract

Currently, the possibility of the inter-Korean railway connection is increasing as the topic of the railway connection leading to China through Sinuiju in North Korea is discussed at the Republic of Korea-China summit. It is expected that not only high-speed trains but also freight trains could reach beyond Russia and China, to Europe. In order to realize this expectation, it is essential to improve the aging railway facilities in North Korea. One of the most important things to consider when planning facilities before constructing a railway is the train operating program. Furthermore, when different types of trains operate in one line, the following high-speed train to overtake the preceding train take places depending on the train time interval, speed, length of trains, and distance between stations. However, the analysis of the operating program based train schedule in the railway planning stage for the construction or improvement of railway infrastructure is carried out mainly on the basis of the intuitive experiences of the planner, and the optimization of the train schedule under various conditions is not considered properly.

Considering the importance of the train schedule in the railway planning stage, this study developed a model for analyzing the Optimal Train Schedule (OTS) when three types of trains with different train speeds, operation frequencies, and stopping stations operate in one railway line. The existing railway models can be categorized into spacetime, space and location-time models depending on the expression method. In this thesis, a mathematical model based on the location-time model, is proposed, which has many advantages in terms of acceptability of various objective and constraint functions, model scalability and ease of implementation and ease of communication such as interpretation of results. Furthermore, because railway train schedules are known as an NP-hard problem whose solution cannot be derived within a reasonable period of time owing to a large number of decision-making variables, most studies on the development of a train schedule problem model use the heuristic methodology.

In order to minimize the scheduled waiting time for overtaking low-speed trains due to the following high-speed trains and determine the stations that require a Subsidiary Main Track (SMT), the conditions required for planning a train schedule were expressed as constraints, and the methods that can accommodate as many of these constraints as possible were reviewed. As a result, it was determined that the heuristic method is the most appropriate for the optimization research in this thesis. Consequently, various optimization algorithms were compared, and a genetic algorithm was selected for this study because of its various advantages such as scalability of the model, ease of addition and relaxation of constraints, and possibility of accommodating various constraints. To implement the optimization of the train schedule based on a mathematical model, a genetic algorithm was developed and applied to a line during the planning stage in Republic of Korea.

The genetic algorithm used in this study analyzed random train schedules (chromosomes) over 300 generations, and the train schedule (chromosome) with the best fitness (lowest scheduled waiting time) becomes the OTS (optimal solution). An analysis was performed on the best fitness according to target fitness, the number of overtaking occurred at each station, and the number of train schedules with the same overtaking stations.

If the OTS is established by applying the method proposed in this study to the planned railway line, and the stations where low-speed trains can be overtaken by high-speed trains when trains of different types operate in one railway line are determined in accordance with the established the OTS, then it will be possible to provide an objective basis for railway planning, rather than relying on the subjective experience of the planners. Furthermore, if the OTS is analyzed based on the method proposed in this study when a new railway line is constructed in a developing country, then it will help achieve economic and policy feasibility.

1 Introduction

Road traffic congestion in many towns and cities has increase owing to urbanization, population growth, existing narrow roads, limited investments in roads, and the increasing number of cars on the roads. This has resulted in an increase in research on sustainable public transport systems as it has become increasingly important. The efficiency of public transportation systems is continuously researched with a primary focus on the operation level and maintenance level.(Oh 2012).

Globally, there is a paradigm shift in transport systems as the investment in railway systems has increased in comparison to road transport systems. A Safe, efficient, economical, and comfortable railway transport realized through high-speed trains has increasingly become popular (Wang 2018).

Railway transportation systems have shown that they are potentially green mode of public transport (Cacchiani et al. 2014). The aforementioned benefits of the railway transport have led to the construction of new rail tracks and the repair of existing rail tracks in many countries, however, it requires a long-term planning. Railway planning proceeds decision-making process in a way step by step. It is characterized by a strategic, tactical, and operation level as shown in Figure 1. A detailed process for each level also corresponds with the classification system of railway planning (Zimmermann and Lindner 2003, Liebchen and Möhring 2007, Lusby et al. 2011).

Railway planning at the strategic level is characterized by a long-term focus on the infrastructure and can be subdivided into demand analysis, network planning, and line planning. The demand for passengers and cargos constitutes the basic data for railway network planning, line planning, and timetable generation.

Economic growth widens the range of human activities and increases trip frequency, therefore, traffic demand should be surveyed for railway planning (Do 2013). The demand for passenger and freight are made at a long-term strategic level and are analyzed using origin-destination surveys. The surveys are designed to gather data on the number and type of trips in an area, are the data is fundamental for railway network planning, line planning and timetable generation (Schroeder et al. 2010).

Railway planning at a long-term strategic level focuses on the construction of railway networks and the modification and supplementation of the existing railway networks. It primarily focuses on the potential of securing the capacity for a future railway network at the time of planning.

Figure 1: Railway Planning Process (source: Zimmermann and Lindner 2003; Liebchen and Möhring 2007; Lusby et al. 2011)

Railway line planning involves dividing railway services into different classes under the secured capacity and developing plans (including the start and end points, and frequency of services) for the lines to allow for provision of sufficient railway services for each class.

Railway planning at a tactical level focuses on the distribution of the resources of the constructed railway infrastructure and can be subdivided into timetable generation, track allocation and train routing, rolling stock scheduling, and crew scheduling. The timetable generation determines the stations where a train is to start from and make