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

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