Optimizing the train timetable with consideration of different kinds of headway time

Abstract

The train timetable is a crucial document for organization of railway traffic. A high-quality train timetable is not only implementable in operational environment, but also efficient in terms of capacity utilization of railway infrastructure. In this paper, we try to solve the train timetabling problem of a double track high-speed railway line with heavy traffic and trains with different operational speeds are operated. In order to obtain a feasible timetable with high efficiency, different kinds of headway time are distinguished in the process of train timetabling. With a time expanded graph describing train movements, an integer linear programming is formulated. A branch and price algorithm is proposed to solve the model. The case study shows that more trains will be scheduled when different kinds of headway time considered.

Keywords

Train timetabling headway time time expanded graph branch and price algorithm integer linear programming

Introduction

The train timetable is a crucial document for organization of railway traffic. It describes railway infrastructure occupation of train movements in time and space. In the railway planning process, the train timetabling is a connecting link between passenger demand and train operation. A high-quality train timetable is not only implementable in operational environment, but also efficient in terms of capacity utilization of railway infrastructure. Therefore, in the process of train timetabling, minimum process times (such as running time in track section, dwell time and headway time) must be satisfied to ensure feasibility and as many as possible trains are scheduled according to the expected passenger demand.

For high-speed railway lines (or corridors) with heavy traffic in China, the train timetabling problem is urgent to be solved. The difficulty of solving the problem is obvious. Firstly, the passenger demand of high-speed railway keeps increasing in recent years, especially during the Spring Festival. More and more trains need to be scheduled in the timetable consequently. Secondly, trains with different operational speeds are operated on most high-speed railway lines at present and meanwhile the complexity of train timetabling is increased. Thirdly, line planning is the basis of train timetabling, and determines the train lines and their frequencies. A train line defines the train type, a route from origin station to destination station (including several intermediate stations) and stations at which trains are scheduled to stop. Train timetabling should comply fully with line planning, and therefore more constraints need to be satisfied.

The train timetabling problem has been researched extensively for many years. Törnquist reviews researches published between 1973 and 2005 in the field of tactical scheduling, operational scheduling and re-scheduling and compares them with respect to problem type, solution mechanism and type of evaluation.¹ Lusby et al. provide an overview about track allocation problems, including train timetabling, train dispatching, train platforming and train routing from a strategic, tactical or operational level.² Harrod summarizes four timetable optimization formulations, according to whether a model explicitly describes the track structure and whether the timetable is periodic, and discusses the model structure, performance and applicability of different formulations.³

The train timetable is a time-space diagram with a time axis and a space axis. Naturally, a time-expanded graph can be used to describe train movements with discretized time units. Based on the time-expanded graph, a 0-1 integer linear programming can be formulated to solve the train timetabling problem. In the model, a binary variable represents whether a train occupies a certain track section (or block section) in a given discrete time unit. Brännlund et al. avoid conflicts between trains by the means of limiting the number of trains occupying a certain block section during a certain period.⁴ Harrod finds that the discrete time dynamic graph fails to capture the interaction effects of resource transitions and the resulting train schedule may not be operationally feasible. Therefore transition nodes (named “cells”) are introduced in order to model the transitions between blocks. For each train, the earliest departure time and the latest arrival time are known. With the goal of maximizing operational profits, a directed hypergraph formulation with block transition constraints is proposed.⁵

However, most researches divide railway line into track sections instead of block sections at macroscopic level and minimum headway time is used to separate different trains to ensure safety. Borndörfer et al. design bidding languages and an auction procedure to implement an auction of railway slots. A railway slot is defined as a particular path on a spatial network planned for a particular time. The winner determination problem of the auction is formulated as an integer programming to maximize earnings, in which binary variables decide whether a slot passes through a specific arc of the time-space network.⁶ Caprara et al. research on the train timetabling problem of a single, one-way track linking two major stations based on a given ideal timetable (which may violate track capacity constraints). To achieve maximum profits, a graph theoretic formulation based on arc variables is proposed and a heuristic algorithm with Lagrangian relaxation embedded is presented.⁷ Caprara et al. extend the formulation with the consideration of several additional constraints that arise in real-word applications.⁸ Cacchiani et al. provide an integer linear programming formulation based on train path variables for the train timetabling problem of a railway corridor. Similarly, an ideal timetable is given and the optimization objective is maximizing profits. The exact algorithm and heuristic algorithm with LP relaxation are devised respectively.⁹ Borndörfer and Schlechte put forward an integer programming formulation based on the concept of feasible arc configuration. The arc configuration is a set of arcs on a track without conflicts. LP relaxation of the formulation can be solved in polynominal time to obtain maximum sum of proceedings associated with each scheduled route.¹⁰ Harrod and Schlechte compare the arc configuration formulation with the directed hypergraph formulation.¹¹

Another typical mathematical formulation for the train timetabling problem is mixed integer linear programming, which is adopted from Job Shop Scheduling. In the formulation, a continuous variable presents the arrival or departure time of each train at each station and a binary variable presents the train order, namely whether a train is operated before another train. Zhou and Zhong put forward a job shop scheduling formulation to solve the single-track train timetabling problem, with the goal of minimizing the total travel time. Moreover, the planned departure time of each train is given and the actual departure time of a train at the starting station is not earlier than planned departure time. A branch-and-bound procedure is designed to obtain feasible schedules with guaranteed optimality.¹² Liu and Kozan propose a no-wait blocking parallel-machine job-shop scheduling model to solve train scheduling problem, with the objective of minimizing the maximum leaving time of all trains and train priority considered. A two-stage hybrid heuristic algorithm is developed to find a preferable train schedule.¹³

Headway time is a vital factor to detect train conflicts in the process of train timetabling. There are different types of headway time and each has a different value. For a busy high-speed railway line, in order to obtain a feasible timetable with high efficiency, different types of headway time should be considered and it is helpful to schedule more trains to accommodate increasing passenger demand.

However, different kinds of headway time are not distinguished in most previous approach. Most papers assume that arrival headway time and departure headway time are constant, namely the value of headway time does not change with specific pairs of train paths. If different kinds of headway time need to be considered, more variables should be added to their optimization models in order to reflect the relationship between headway time and train stopping patterns and train orders. This may destroy the model structure and therefore the corresponding algorithm should be adjusted.

In this paper, we try to take different kinds of headway time into consideration, and solve the train timetabling problem of a double track high-speed railway line with heavy traffic. Trains with different operational speeds are operated. This paper is organized as follows: The types of headway time and their influence factors are demonstrated in section “Headway time”. The description of the train timetabling problem is given particularly in section “Problem description”. The railway line is divided into track sections at macroscopic level and a time expanded graph is used to describe train movements. An integer linear programming is proposed in section “Train timetabling model”. Section “Branch and price algorithm” provides a branch and price algorithm to solve the model. Finally, in section “Case study”, the section between Xuzhou East Station and Nanjing South Station on Beijing–Shanghai high-speed railway is analyzed and it shows that more trains can be scheduled when different kinds of headway time considered.

Note that values of different kinds of headway time need to be calculated at microscopic level and are assumed to be given as input in our research. That is, we try to solve the train timetabling problem at macroscopic level. Several researchers solve the scheduling problem in more complicated situations. Bešinović et al. propose a hierarchical framework for timetable design which combines a microscopic and a macroscopic model of the network. The output of the framework is a feasible and stable timetable with a suboptimal trade-off between efficiency and robustness.¹⁴ Schlechte et al. provide a bottom-up approach to transform a microscopic railway network to an aggregated macroscopic network model and back. Although the track allocations are produced on a macroscopic scale, the results satisfy operational requirements of microscopic model.¹⁵ Corman et al. present a detailed microscopic representation of the railway network that is able to tackle the complexity of a station area with multiple conflicting routes and high service frequency.¹⁶ Kecman et al. develop new macroscopic models and investigate how different level of detail and number of operational constraints may affect the applicability of models for network-wide rescheduling.¹⁷

Headway time

Types of headway time

Headway time is the time interval between two successive trains to guarantee operational safety. There exists a train conflict if the headway time constraint is violated. For a double track railway line, trains are operated in one direction on each track. Headway time can be classified into nine kinds according to different combinations of train movements, namely headway in track section, “departure-departure” headway, “arrival-arrival” headway, “passing-passing” headway, “arrival-passing” headway, “passing-arrival” headway, “passing-departure” headway, “departure-passing” headway and “departure-arrival” headway as shown in Figure 1 in order. Headway in track section is the time interval between two trains which run on the same track section (as shown in Figure 1(a)). “Departure-departure” headway is the time interval between two trains which depart from the same station consecutively (as shown in Figure 1(b)). “Arrival-passing” headway is the time interval between the arrival time of a train and the passing through time of another train at the same station and the arrival time is earlier than the passing through time (as shown in Figure 1(e)). The remaining different kinds of headway time can be defined by analogy. Note that if trains are allowed to turn around immediately on the same track in a station (especially in a terminal), there exist other kinds of headway time for trains operated in the opposite directions. In this paper, it assumes that in trains can’t turn around immediately at any station along the railway line.

Figure 1.

The classification of headway time. (a) headway in track section, (b) “departure-departure” headway, (c) “arrival-arrival” headway, (d) “passing-passing” headway, (e) “arrival-passing” headway, (f)“passing-arrival” headway, (g)“passing-departure” headway, (h)“departure-passing” headway and (i) “departure- arrival” headway.

Blocking time theory

Accurate calculation of headway time is necessary to improve the quality of timetable. Generally, based on the blocking time theory, headway time is calculated for a pair of trains on the microcosmic level. When a train is running in a block section, the occupation time of the block section is more than the physical running time. Blocking time theory quantifies the specific occupation time of a train movement in a block section. Pachl analyzes blocking time theory in conventional main/distant signaling system.¹⁸ Furthermore, Wendler adopts the blocking time theory to modern signaling and automatic train control systems, especially for the ETCS levels.¹⁹ On the basis of characteristics of high-speed railway in China, the constitution of blocking time is shown in Figure 2. Specifically, blocking time in a block section consists of six parts.

Train routing time is the time for setting up the train route, such as the switching time of turnouts and time for signal preparation, i.e. the part of “a” in Figure 2.

Reaction time mainly refers to reaction time of the driver and information transmission time between different devices, i.e. the part of “b” in Figure 2.

Approaching time is the time the train runs through the braking distance, i.e. the part of “c” in Figure 2.

Physical occupation time is the train running time in the block section and protective distance. The protective distance is reserved to avoid unpredictable situations happening, i.e. the part of “d” in Figure 2.

Clearing time is the time a train leaves the block section completely, namely the tail of the train leaves the block section, i.e. the part of “e” in Figure 2.

Release time is the time for releasing the train route and closing related signals, i.e. the part of “f” in Figure 2.

Figure 2.

The constitution of blocking time in a block section.

In track sections or stations, blocking times of a train in all block sections result in a blocking time stairway. As known for us, once a block section is occupied by one train, another train must not have access to the block section. That is, the overlaps of blocking time of different trains at the same block section are forbidden to eliminate train conflicts. For a pair of trains, different kinds of headway time are calculated under the condition that the two blocking time stairways touch each other without any tolerance in at least one block section and without any overlaps in all block sections. Besides theoretical calculation, the value of different kinds of headway time should be confirmed by traction calculation software.

Note that there exist many conflict-free train routes in stations, which can be used by different trains at the same time. Therefore, blocking time of block sections in stations should be analyzed with the consideration of release pattern of train route locking.

Influence factors of headway time

Based on the constitution of the blocking time constitution and operational rules, headway time is mainly influenced by horizontal and vertical alignments of railway line, speed limitation, signaling system, technical parameters of EMU and the operation schedule. Those influence factors are illustrated in detail.

Horizontal and vertical alignments of railway line. The physical occupation time is the main component of blocking time. It is restricted by the horizontal and vertical alignments of railway line in a large degree. In China, the length of block section in track section usually ranges from 1.9 km to 2 km and it is shorter if the block section is closed to a station.

Speed limitation. Due to operational conditions of infrastructure or severe weather, the speeds of trains need to slow down to guarantee safety. If the speeds of trains get lower, the physical occupation time and clearing time will be longer. This factor becomes more important in stations, where there exist many turnouts. Turnouts numbered 18 are applied widely in high-speed railway and the speeds of trains are limited to 80 km/h (according to the Railway Technical Management Rules) when trains go through the diverging route of the turnout.

Signaling system. Firstly, train routing time and release time depend on the signaling system. Secondly, the information transmission time between different devices of signaling system has an influence on the reaction time. Thirdly, the approaching time is mainly dominated by the braking distance, which is affected by train control system. CTCS2 and CTCS3 are widely used and quasi-moving blocking system is adopted in China. The braking distance is calculated under the assumption that, if a train does not obtain movement authority of next block section, the train needs to stop before the block section occupied by another train ahead. As shown in Figure 3, the train begins to brake at the indication point so as to stop before the beginning point of occupied block section. Note that, protective distance is reserved between the stopping place of the train and the beginning point of the block section to avoid errors of signaling system caused by the environmental factors, such as rain or snow. Moreover, it contributes to a more relaxed driving condition. Relevant technical regulations restrict the protective distance to 110 m in track sections and 60 m in stations according to the Provisional Technical Specification of CTCS2 and CTCS3.

Technical parameters of EMU. The speed profile is updated on time in CTCS2 and CTCS3 and the indication point^a (as shown in Figure 3) is related to braking performance of the train. That is, the position of indication point is not fixed. Therefore, approaching time is also affected by braking performance of EMU. Meanwhile, physical occupation time and clearing time are related to train speed and train formation, respectively.

Operation schedule. Operation schedule determines train routes, stopping patterns and train order for all trains. A train route determines the set of block sections that will be occupied. A stopping pattern determines the set of stations at which trains need to stop. Influence factors mentioned above affect the exact value of the blocking time for one train. Instead, operation schedule has an impact on the combination of the blocking time stairways for a pair of trains. Hence operation schedule is also a crucial factor and can’t be ignored.

Figure 3.

The pattern of speed control in CTCS2 and CTCS3.

Headway time is an important parameter for the train timetabling problem and plays a significant role to generate a conflict-free timetable. In terms of different kinds of headway time, blocking time for a train and combination of the blocking time stairways for a pair of trains are not identical. As a result, the exact values of different kinds of headway time are different and should not be set as the same value.

In this paper, different kinds of headway time are distinguished in the process of train timetabling. Meanwhile, the method of dynamic constraints generation is used to consider the influence of operation schedule on headway time. Note that, with given train lines, different kinds of headway time can be given for a pair of train lines in the phase of train timetabling, instead of a pair of trains.

Problem description

Railway line

The train timetabling problem of a double, one-way high-speed railway line with heavy traffic is discussed in this paper, as shown in Figure 4. On each track of the railway line, only one-way traffic is operated. Trains running in different directions don’t interact in general. At the macroscopic level, the railway line is divided into track sections and stations are modeled as nodes.

Figure 4.

The presentation of railway line.

Train type and running time

Trains are classified into two types by their operational speeds. Trains with much higher operational speeds belong to high-ranking trains and the others belong to low-ranking trains. For different types of trains, pure running time is provided respectively in each track section. In the process of train timetabling, pure running time is assumed to be a constant and can’t be changed. Meanwhile, the additional time for acceleration and deceleration should not be ignored. If a train stops at a station, additional time for acceleration (or deceleration) is added to pure running time of the adjacent track section. The sum of pure running time and additional time for acceleration or deceleration is defined as running time in the track section.

Train line and their frequencies

Line planning obtains train lines and their frequencies in accordance with passenger demand and is the basis of train timetabling. For a railway line with heavy traffic, the requirement of service frequency for each train line may not always be satisfied due to the lack of capacity. However, as many as possible trains need to be scheduled in the train timetable in order to meet passenger demand and improve efficiency. Except for service frequency, train type, origin station, destination station and stations at which the train is scheduled to stop can’t be altered for each train line.

Dwell time

For the sake of high capacity utilization, overtaking between trains is allowed and dwell time at stations can be enlarged in a given range. Minimum dwell time is necessary for passengers to get on or off the train and maximum dwell time is limited to reduce the total travel time of whole journey.

Train set and time window

A train set is generated according to the requirement of train lines and their frequencies. If a train belongs to a certain train line, train type, origin station, destination station and stations at which the train is scheduled to stop are determined by the train line. And the number of trains, which belong to the same train line, equals the corresponding service frequency of the train line. For each train in the train set, the time distribution of passenger demand restricts a time window, which defines the earliest departure time (at the origin station) and the latest arrival time (at the destination station). For simplification, time windows of all trains are supposed to be given.

Headway time

For pairs of train lines, exact values of different kinds of headway time are provided in advance. It is meaningful to consider different kinds of headway time precisely. By this means, it is possible to arrange more trains into the train timetable. As a result, efficiency of the generating timetable is improved and feasibility of operation is ensured at the same time.

Problem definition

The train timetabling problem in this paper can be described as follows. Given a double, one-way high-speed railway line with heavy traffic, departure time and arrival time for all trains at each station are scheduled properly to eliminate train conflicts. Train lines with their frequencies and time windows for each train are known in advance. In the process of train timetabling, running time is fixed and dwell time can be optimized within a given range. The goal of optimization is to minimize the total dwell time and the deviation of departure time from the earliest departure time at the origin station. Because the values of different kinds of headway time are not identical, it is more accurate to consider different kinds of headway time for pairs of train lines separately.

Train timetabling model

Notions

The sets, parameters and variables involved in the train timetabling model are listed in Table 1 at first.

Table 1.

Sets, parameters and variables involved in the train timetabling model.

Sets
N:	Node set of the time expanded graph
N_d:	Set of departure nodes
N_a:	Set of arrival nodes
$N_{os}$ :	Set of artificial nodes
E:	Arc set of the time expanded graph
E_d:	Set of driving arcs in track sections
E_s:	Set of stopping arcs at stations
E_b:	Set of beginning arcs
E_e:	Set of ending arcs
L:	Train set
P_l:	Optional set of train paths for a train l, $l \in L$
P:	Optional set of train paths for all trains
C:	Conflict set of pairs of train paths and each pair of train paths violates headway time constraints
Parameters
$τ (n)$ :	Time instance of the node n, $n \in N$
w_p:	Weight of the train path p
$t_{dwe}$ :	Total dwell time for a train path $p \in P$
$t_{dev}$ :	Deviation time of departure time (at origin station) from the earliest departure time for a train path $p \in P$
$w_{dwe}$ :	Weight of total dwell time
$w_{dev}$ :	Weight of deviation time
$w_{rank}$ :	Weight of the rank of a train
Variables
x_p:	a binary variable with $x_{p} = 1$ if the train path p is scheduled in the final generating train timetable; otherwise, $x_{p} = 0$

Time expanded graph

With time discretized into 1 min, a time expanded graph $G = (N, E)$ can be used to describe train movements on a railway line. In the directed graph, the node set N can be expressed by ${N_{d}, N_{a}, N_{os}}$ . A departure node $n_{d} \in N_{d}$ represents a train departs from a station at $τ (n_{d})$ . An arrival node $n_{a} \in N_{a}$ represents a train arrives at a station at $τ (n_{a})$ . The artificial source node $n_{o} \in N_{os}$ and the artificial sink node $n_{s} \in N_{os}$ are established to normalize the problem. The arc set E can be expressed by ${E_{d}, E_{s}, E_{b}, E_{e}}$ . A driving arc $e_{d} \in E_{d}$ in a track section connects a departure node n_d with an arrival node n_a and running time in the track section equals to $τ (n_{a}) - τ (n_{d})$ . A stopping arc $e_{s} \in E_{s}$ in a station connects an arrival node n_a with a departure node n_d at the same station and the dwell time in the station equals to $τ (n_{d}) - τ (n_{a})$ . A beginning arc $e_{b} \in E_{b}$ connects the artificial source node n_o with a departure node n_d at the origin station. An ending arc $e_{e} \in E_{e}$ connects the artificial sink node n_s with an arrival node n_a at the destination station.

For each train $l \in L$ , the optional set of train paths P_l is generated in the time expanded graph. A train path refers to a feasible schedule for one train, which determines the departure time and arrival time at all stations. Each possible train path $p \in P_{l}$ is constrained by the train line and time window of train l. Meanwhile, train movements on the railway line should satisfy the requirements of running time in each track section and dwell time at each station. Figure 5 represents the optional set of train paths for a train. For this train, running time in each section is 4 min and dwell time at station $s + 1$ can be 2 min or 3 min. There are 22 possible train paths generated in the optional set of train paths for the train.

Figure 5.

The optional set of train paths for a train.

Integer linear programming

In this section, an integer linear programming is formulated to solve the train timetabling for double, one-way high-speed railway line with heavy traffic. For each possible train path $p \in P$ , a corresponding binary variable x_p is introduced to indicate whether the train path p is scheduled in the final generating train timetable.

To achieve a reasonable objective function, several aspects are considered. Firstly, since the stopping patterns for all trains can’t be changed, the additional time for acceleration and deceleration are added to certain track sections. Meanwhile, pure running time for each track section is a constant. Therefore, instead of total travel time, total dwell time for all trains should be minimized. Secondly, it is appreciate for a train to depart from the origin station at the earliest departure time. For a train path, the deviation of departure time from the earliest departure time should also be minimized. As a result, the objective function is

min \sum_{l \in L} \sum_{p \in P_{l}} w_{p} x_{p}

(1)

where the weight w_p for a train path

p \in P

can be calculated as

w_{p} = w_{dwe} t_{dwe} + w_{dev} t_{dev}

(2)

Note that if the train priority is taken into account, the weight $w_{rank}$ needs to be added according to the rank of the corresponding train. And the expression of the weight w_p can be revised as

w_{p} = w_{rank} (w_{dwe} t_{dwe} + w_{dev} t_{dev})

(3)

In fact, if $w_{rank} = 1$ for all trains, the expression (3) turns into expression (2).

The model of train timetabling is demonstrated as following.

min \sum_{l \in L} \sum_{p \in P_{l}} w_{p} x_{p}

(4)

\sum_{p \in P_{l}} x_{p} \leq 1 \forall l \in L

(5)

\sum_{p \in c} x_{p} \leq 1 \forall c \in C

(6)

x_{p} \in {0, 1}

(7)

The objective function (4) minimizes the weighting sum of total dwell time and deviation of the earliest departure time. Constraint (5) enforces that there is at most one train path generated for each train. The cancellation of part of trains in the train set L is allowed. Constraint (6) eliminates train conflicts on the basis of different kinds of headway time. For a pair of train paths which belong to different trains, if the headway time constraint isn’t satisfied, the pair of train paths is added into the conflict set C. Different from traditional train timetabling models, the conflict set C is generated by considering different kinds of headway time carefully. For a specific pair of train paths, headway time changes with the train stopping patterns and train orders and therefore the conflict set is generated dynamically. Constraint (7) limits all decision variables to binary integer values.

Branch and price algorithm

For the train timetabling model (which is an integer linear programming) in section “Train timetabling model”, an exact branch and price algorithm is proposed. The branch and price algorithm combines the branch and bound scheme with column generation. Sets and parameters involved are shown in Table 2.

Table 2.

Set and parameters involved in branch and price algorithm.

Sets
X:	Current optimal solution of all nodes
X_n:	Optimal solution of the node n, $X_{n} = {x_{p}}$
A:	Set of active node
$\bar{P_{l}}$ :	Set of promising train paths of train l, $\bar{P_{l}} = {x_{p}'}$ , $l \in L$ , $\bar{P_{l}} \in P_{l}$
Parameters
$ub$ :	Current upper bound
n:	Node in branch and price tree
n_r:	Root node in the branch and price tree
n_a:	Node which will be judged next, $n_{a} \in A$
P_n:	Linear programming of the node n
$obj (P_{n})$ :	Optimal objective value for the linear programming P_n
$One (X_{n})$ :	The number of decision variables which satisfy $x_{p}^{} = 1$ and $x_{p}^{} \in X_{n}$
$π$ :	Dual variable
$x_{p}'$ :	Promising train path with minimum objective value of pricing subproblem

Framework of algorithm

In the branch and price tree, each node n has a corresponding linear programming P_n. For the root node n_r of the tree, the linear programming $P_{n_{r}}$ is the LP relaxation of the train timetabling model. Column generation is used to solve the linear programming P_n. An optimal solution X_n and the objective value $obj (P_{n})$ are obtained consequently.

The set of active node A contains nodes which have not been judged and only the root node n_r originally. The node n_a which will be branched next is determined by breadth-first search strategy. That is, $obj (P_{n_{a}})$ is minimum among $obj (P_{n})$ for all nodes n in A. If the node with minimum optimal objective value is more than one, the node n with maximum $One (X_{n})$ is selected as n_a. It is useful to find a feasible solution of the train timetabling quickly.

It is pivotal to judge whether the node n_a is branched or trimmed. Note that the upper bound $ub$ is set to be infinite at first.

If all decision variables in the optimal solution $X_{n_{a}}$ are binary integers and $obj (P_{n_{a}})$ is smaller than the current upper bound $ub$ , the node n_a is trimmed. Meanwhile, the $ub$ is updated by $obj (P_{n_{a}})$ and the current optimal solution X is updated by $X_{n_{a}}$ .

If some decision variables in the optimal solution $X_{n_{a}}$ are not binary integers and $obj (P_{n_{a}})$ is greater than or equal to the current upper bound $ub$ , the node n_a is trimmed.

If some decision variables in the optimal solution $X_{n_{a}}$ are not binary integers and $obj (P_{n_{a}})$ is smaller than the current upper bound $ub$ , the node n_a needs to be branched further.

After the judgment of the node n_a, the node n_a is removed from the set A. The branching of the node n_a is implemented by forcing the most fractional decision variable to be 0 and 1. Then two new nodes are generated and added into the set A. Select the node n_a iteratively based on breadth-first search strategy until the set A is empty. The flowchart of branch and price algorithm is shown in Figure 6 in detail.

Figure 6.

The flowchart of branch and price algorithm.

Column generation

For each linear programming P_n of node n, the number of feasible train paths in optional set of train paths P is increase rapidly with the problem scale. For a train which is scheduled to stop at each station, the increase tendency of optional train paths with number of track section and time window is demonstrated in Figure 7.

Figure 7.

The increase tendency of optional train paths.

Instead of generating entire feasible train paths, promising train paths are generated dynamically to reduce the calculation complexity. That is, each P_n is solved by column generation.

In the beginning, artificial train paths are constructed for each train $l \in L$ respectively and constitute the initial $\bar{P_{l}}$ . To avoid the artificial train paths being scheduled into the final optimal solution, the weights w_p of artificial train paths are assigned to be infinite or a large number. The restricted master problem of P_n is as following. Note that some decision variables x_p is forced to be 0 or 1 in P_n.

min \sum_{l \in L} \sum_{p \in \bar{P_{l}}} w_{p} x_{p}

(8)

\sum_{p \in \bar{P_{l}}} x_{p} \leq 1 \forall l \in L

(9)

\sum_{p \in c} x_{p} \leq 1 \forall c \in C

(10)

x_{p} \in {0, 1} \forall p \in \bar{P_{l}}, \forall l \in L

(11)

Let $π_{l}$ and $π_{c}$ be the dual variables for constraint (9) and constraint (10), respectively. The following is the corresponding dual problem.

max - \sum_{l \in L} \sum_{p \in \bar{P_{l}}} π_{l} - \sum_{c \in C} \sum_{p \in c} π_{c}

(12)

- \sum_{l \in L} \sum_{p \in \bar{P_{l}}} π_{l} - \sum_{c \in C} \sum_{p \in c} π_{c} \leq w_{p} \forall p \in \bar{P_{l}}, \forall l \in L

(13)

π_{l} \geq 0 \forall l \in L

(14)

π_{c} \geq 0 \forall c \in C

(15)

Based on the dual problem, the pricing subproblem can be formulated as

min \sum_{l \in L} \sum_{p \in \bar{P_{l}}} w_{p} + \sum_{l \in L} \sum_{p \in \bar{P_{l}}} π_{l} + \sum_{c \in C} \sum_{p \in c} π_{c}

(16)

If the minimum objective value of pricing subproblem is greater than 0, the corresponding promising train path $x_{p}'$ is added into $\bar{P_{l}}$ and restricted master problem is solved again. Otherwise, the process of column generating is terminated. In order to reduce the number of solving restricted master problem, more than one promising train paths are added into $\bar{P_{l}}$ in each iteration. Besides the train path $x_{p}'$ with minimum objective value of pricing subproblem, other promising train paths are obtained by removing stopping arcs at stations of train path $x_{p}'$ stochastically. This method is based on the deletion algorithm proposed by Xu et al. to find K short paths.²⁰

From the description above, train paths are generated dynamically. If a new train path conflicts with other train path (which may exist already), it is necessary to add the pair of train paths to C. Therefore, considering different kinds of headway time, conflict constraints for pairs of train paths are generated dynamically. With the dynamic constraints generation, the influence of the operation schedule on headway time is measured precisely.

Case study

The Beijing–Shanghai high-speed railway line is a vital corridor in China. The section between Xuzhou East Station and Nanjing South Station is crucial for the capacity utilization of Beijing–Shanghai high-speed railway. Thus, the high-speed railway section between Xuzhou East Station and Nanjing South Station is studied to show the application and performance of the methodology. There are six stations in this section, namely Xuzhou East Station, Suzhou East Station, Bengbu South Station, Dingyuan Station, Chuzhou Station and Nanjing South Station in the downward direction. The train running time in each track section for different types of train is illustrated in Table 3. In addition, for high-ranking trains (named G trains), the additional time for acceleration and deceleration are 3 min and 2 min respectively; and for low-ranking trains (named D trains), the additional time for acceleration and deceleration are 2 min and 2 min, respectively. For each station, the minimum and maximum dwell time are set as 1 min and 9 min, respectively. The train lines and their frequencies are demonstrated in Figure 8. Consequently, a train set is formed and the number of trains is 107. The time window for each train is acquired based on the characteristics of current transportation organization and passenger demand. The weight of total dwell time

w_{dwe}

, weight of deviation time

w_{dev}

and weight of the rank of a train

w_{rank}

are equal to 1.

Table 3.

Train running time in each track section.

Train type	Track section	Pure running time (min)
High-ranking trains	Xuzhou East-Suzhou East	14
	Suzhou East-Bengbu South	18
	Bengbu South-Dingyuan	11
	Dingyuan-Chuzhou	13
	Chuzhou-Nanjing South	13
Low-ranking trains	Xuzhou East-Suzhou East	17
	Suzhou East-Bengbu South	22
	Bengbu South-Dingyuan	13
	Dingyuan-Chuzhou	15
	Chuzhou-Nanjing South	15

Figure 8.

Train lines and their frequencies.

The headway in track section can be 3 min on Beijing–Shanghai high-speed railway line. If the preceding train is a low-ranking train and the subsequent train is a high-ranking train, the “departure-departure” headway, “arrival-arrival” headway, “passing-passing” headway, “arrival-passing” headway, “passing-arrival” headway, “passing-departure” headway, “departure-passing” headway and “departure-arrival” headway are 5 min, 5 min, 4 min, 5 min, 5 min, 4 min, 5 min and 4 min, respectively. Otherwise, those headway time are 4 min, 5 min, 3 min, 4 min, 4 min, 3 min, 4 min and 3 min, as shown in Table 4. Note that although the headway time is given according to the train type for simplification, different kinds of headway time vary with different pairs of train lines actually.

Table 4.

Values of different kinds of headway time (min).

Train order		d-d	a-a	p-p	a-p	p-a	p-d	d-p	d-a
Preceding train	Low-ranking	5	5	4	5	5	4	5	4
Subsequent train	High-ranking	5	5	4	5	5	4	5	4
Preceding train	High-ranking	4	5	3	4	4	3	4	3
Subsequent train	Low-ranking	4	5	3	4	4	3	4	3

The branch and price algorithm is coded in Microsoft Visual Studio 2010 with the C# language, and CPLEX 12.3 solver is used to solve linear programming models generated in the branch and price algorithm. The computer used is equipped with 2.39 GHz CPU and 7.99 GB RAM.

With different kinds of headway time considered, the optimal train timetable is shown in Figure 9. There are 107 trains scheduled in the generating timetable. The weight of artificial train paths in objective function is assigned to be 500. In the optimization process, the number of promising train paths generated is 2639 for all trains and about 25 per train. It spends about 9684 s in solving the train timetabling model (which is an integer linear programming). The UB and LB of the branch and price tree are updated gradually, which are demonstrated in Figure 10. As shown in Figure 10(a), in the early stage, the UB is decreased dramatically, which means that feasible timetables are generated rapidly. However, in order to obtain the optimal result, more time is spent and the improvement of the UB is relatively small in the later stage. In the optimal result, total deviation time for departure time from the earliest departure time is 715 min and total dwell time is 77 min. Overall, the optimal value of the objective function is 792 min.

Figure 9.

Optimal train timetable with different kinds of headway time considered.

Figure 10.

The update of the (a) UB and (b) LB in the branch and price tree.

For an explicit explanation for the effectiveness of the methodology proposed in this paper, the optimal train timetable with identical headway time is also generated for comparison. When headway time is set to be 5 min, the optimal train timetable has only 101 trains as the cancellation of trains in the train set is allowed. The total deviation for departure time from the earliest departure time is 684 min and total dwell time is 61 min. The optimal value of the objective function is 3745 min. If 101 trains are scheduled considering different kinds of headway time, the total deviation for departure time from the earliest departure time is 578 min and total dwell time is 67 min. The comparison of the optimal results is shown in Table 5.

Table 5.

Comparison of the optimal results.

Case	Number of trains	Different kinds of headway time	Objective value	Deviation from the earliest departure time (min)	Dwell time (min)
1	107	Yes	792	715	77
2	101	No	3745	684	61
3	101	Yes	3639	578	67

Overtaking between different trains leads to increase of dwell time for the train which is overtaken by the other train. Therefore, the optimal train timetable would avoid overtaking as much as possible. It shows that more overtakings are included in the optimal result when accurate values of different kinds of headway time are considered. On the one hand, if more overtakings are scheduled, more train paths can be arranged into the final train timetable, namely a feasible train timetable with high efficiency is obtained. For example, in case 1, for those trains which have the earliest departure time ranging from 14:00 to 16:00, there is an overtaking between G131 and G325 in Suzhou East station, which gives a chance to arrange one more train G123 into the train timetable, as shown in Figure 11. As a result, more trains are scheduled in case 1 than in case 2. On the other hand, overtakings can lead to the decrease of objective function. That is, due to the overtakings, the deviation from the earliest departure time is decreased at the cost of the increase of dwell time. For example, in case 3, G325 is overtaken by G131 in Suzhou East station, as shown in Figure 12. For those two trains, the deviation from the earliest departure time is 26 min and dwell time is 7 min (as shown in Figure 12(a)). If there isn’t an overtaking, the deviation from the earliest departure time is 33 min and dwell time is 1 min (as shown in Figure 12(b)), which lead to the objective value increased by 1 min.

Figure 11.

Train paths scheduled in [14:00, 16:00] in case 1 and case 2.

Figure 12.

The overtaking between G131 and G325 in case 3. (a) overtaking and (b) no overtaking.

Conclusion

The train timetabling problem of a double, one-way high-speed railway line with heavy traffic is discussed in this paper. Train lines with their frequencies and time windows for each train are known in advance. In the process of train timetabling, running time is fixed and dwell time can be optimized within a given range. With a time expanded graph describing train movements, an integer linear programming is formulated to minimize total dwell time and the deviation of departure time from the earliest departure time at the origin station. A branch and price algorithm is proposed to solve the model. The case study on the high-speed railway section between Xuzhou East Station and Nanjing South Station shows that more trains will be scheduled and the deviation from the earliest departure time may be decreased when different kinds of headway time are considered. That is, a feasible train timetable with high efficiency can be obtained with the consideration of different kinds of headway time in detail.¹

Footnotes

Declaration of conflicting interests

The author(s) declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.

Funding

The author(s) disclosed receipt of the following financial support for the research, authorship, and/or publication of this article: This work was financially supported by National Natural Science Foundation of China (U1434207), Fundamental Research Funds for the Central Universities (2016JBM030), Beijing Municipal Science and Technology Comission (Z151100001315004), and Beijing Chaoyang District Science and Technology Comission (CYXC1607). The authors wish to thank these agencies.

Note

References

Törnquist

. Computer-based decision support for railway traffic scheduling and dispatching: A review of models and algorithms. In: Workshop on algorithmic methods & models for optimization of railways 2005.

Lusby

Larsen

Ehrgott

. Railway track allocation: Models and methods. OR Spectrum 2011; 33(4): 843–883.

Harrod

. A tutorial on fundamental model structures for railway timetable optimization. Surv Oper Res Manage Sci 2012; 17(2): 85–96.

Brännlund

Lindberg

Nõu

. Railway timetabling using Lagrangian relaxation. Transport Sci 1998; 32(4): 358–369.

Harrod

. Modeling network transition constraints with hypergraphs. Transport Sci 2011; 45(1): 81–97.

Borndörfer

Schlechte

Grötschel

. An auction approach to railway slot allocation. Comp Regul Netw Ind 2006; 7(2): 163–197.

Caprara

Fischetti

Toth

. Modeling and solving the train timetabling problem. Oper Res 2002; 50(5): 851–861.

Caprara

Monaci

Toth

. A Lagrangian heuristic algorithm for a real-world train timetabling problem. Discr Appl Math 2006; 154(5): 738–753.

Cacchiani

Caprara

Toth

. A column generation approach to train timetabling on a corridor. 4OR-A Quart J Oper Res 2008; 6(2): 125–142.

10.

Borndörfer

Schlechte

. Models for railway track allocation. In: Workshop on algorithmic methods & models for optimization of railways 2007.

11.

Harrod

Schlechte

. A direct comparison of physical block occupancy versus timed block occupancy in train timetabling formulations. Transport Res E: Log Transport Rev 2013; 54: 50–66.

12.

Zhou

Zhong

. Single-track train timetabling with guaranteed optimality: Branch-and-bound algorithms with enhanced lower bounds. Transport Res B: Methodol 2007; 41(3): 320–341.

13.

Liu

Kozan

. Scheduling trains with priorities: A no-wait blocking parallel-machine job-shop scheduling model. Transport Sci 2011; 45(2): 175–198.

14.

Bešinović

NBS

Goverde

RMP

Quaglietta

. An integrated micro–macro approach to robust railway timetabling. Transport Res B: Methodol 2016; 87: 14–32.

15.

Schlechte

Borndörfer

Erol

. Micro–macro transformation of railway networks. J Rail Transport Plan Manage 2011; 1(1): 38–48.

16.

Corman F, Goverde RM and D’Ariano A. Rescheduling dense train traffic over complex station interlocking areas, 2009.

17.

Kecman P, Corman F, D’Ariano A, et al. Rescheduling models for network-wide railway traffic management, 2012.

18.

Pachl J. Railway operation and control, 2002.

19.

Influence of ETCS on the capacity of lines. International Union of Railways (UIC). Paris, 2008[R]. ISBN 2-7461-1455-0.

20.

Luo

Gao

. Passenger flow distribution model and algorithm for urban rail transit network on multi-route choice. J China Railw Soc 2009; 31(2): 110–114.