Keywords

1 Introduction

High-speed lines are attracting more and more passenger flow because of the high train speed and frequency and better service. However, the risk exists at all times and passengers have to face the possibility of different degrees of trains delay. With the development of train control technology, it is more and more practical to consider the energy consumption while rescheduling the timetable.

Train operation adjustment is a large-scale combination of optimization, which needs to consider a lot of factors. A linear programming model has been designed to determine the optimal avoidance station and the cross station [1]. The minimum difference between the actual timetable and the original timetable has been taken as the optimization target [2]. In general, the factors that are considered for the train operation adjustment include the total late time, the number of late trains, the late rate, etc [3, 4].

In recent years, some scholars began to explore the design of energy-saving timetable. Energy-saving timetable can be achieved by optimizing the stopping time at the station and the coasting time in the interval [5]. A comprehensive timetable can be formed through the optimization of timetable and the speed curve between adjacent stations [6]. The current energy-saving timetable is mainly aimed at urban rail transit, while scholars also have proved the effectiveness of energy-saving timetable in high-speed railway applications [7,8,9].

Currently, the primary goal of the late train operation adjustment is to reduce the delayed time, so the energy consumed is almost neglected in this process. In this paper, a bi-level model based on high-speed railway timetable optimization is proposed under the delayed condition. In the rest of this paper, the problem of the timetable rescheduling of the upper layer model and the energy saving of the lower layer model will be described in the bi-level model. In the following section, the solving algorithm will be introduced. A case study of Wuhan to Guangzhou high-speed railway will be illustrated in the section of case study and the conclusion of the results are in the final section.

2 The Bi-level Model

2.1 Timetable Rescheduling Problem

The purpose of this part is to adjust the train movements to be consistent with the original timetable as much as possible within a certain range of constraints.

  1. (1)

    The Decision Variables

\( a_{i,j} \) is the new arrival time of train i at station j after adjustment. \( d_{i,j} \) is the new departure time. \( {\text{delay}}_{i,j} \) is the delay, that is, the difference in the arrival time between the adjusted and the original one. If the departure time of train i is earlier than train i′ in the original timetable, then \( T_{{i,i^{\prime },j}}^{\text{original}} = 1 \), otherwise \( T_{{i,i^{\prime },j}}^{\text{original}} = 0 \). If the departure time of train i is changed later, then \( T_{{i,i^{\prime },j}}^{\text{reschedule}} = 1 \), otherwise \( T_{{i,i^{\prime },j}}^{\text{reschedule}} = 0 \). If train i occupies track l, then \( \lambda_{i,j}^{l} = 1 \), otherwise \( \lambda_{i,j}^{l} = 0 \).

  1. (2)

    The optimization objective

Take a line with m trains and n stations as an example, and the goal of the model is to minimize the total delay time:

$$ \hbox{min} \, z_{d} = \sum\limits_{i = 1}^{m} {\left( {f_{i} \cdot \sum\limits_{j = 1}^{n} {{\text{delay}}_{i,j} } } \right)} . $$
(1)

\( z_{d} \) is the total delay time and \( f_{i} \) is the cost per unit time delay for train i.

  1. (3)

    The Constraints

\( \sec_{i,j} \) is the minimum running time of train i on section [j, j + 1]. \( {\text{sta}}_{i,j} \) is the minimum dwell time at station j. N is a large enough natural number. \( \tau_{j}^{\sec } \) is the headway of section [j, j + 1]. \( \tau_{j}^{\text{sta}} \) is the headway between two adjacent trains at station j. \( \omega_{j} \) is the track number of station j.

  1. (a)

    Section running time restrictions:

$$ a_{{i,j{ + }1}} - d_{i,j} \ge \sec_{i,j} $$
(2)
  1. (b)

    Station dwell time restrictions:

$$ d_{i,j} - a_{i,j} \ge {\text{sta}}_{i,j} $$
(3)
  1. (c)

    Section headway restrictions:

$$ (d_{{i^{\prime },j}} - d_{i,j} ) + N(1 - T_{{i,i^{\prime },j}}^{\text{original}} ) \ge \tau_{j}^{\sec } \cdot T_{{i,i^{\prime },j}}^{\text{original}} $$
(4)
$$ (d_{i,j} - d_{{i^{\prime },j}} ) + N(1 - T_{{i,i^{\prime },j}}^{\text{reschedule}} ) \ge \tau_{j}^{\sec } \cdot T_{{i,i^{\prime },j}}^{\text{reschedule}} $$
(5)
  1. (d)

    Station headway restrictions:

$$ \lambda_{i,j}^{l} + \lambda_{{i^{\prime },j}}^{l} - (T_{{i,i^{\prime },j}}^{\text{original}} + T_{{i,i^{\prime },j}}^{\text{reschedule}} ) < 1 $$
(6)
$$ (a_{i',j} - a_{i,j} ) + N(1 - T_{i,i',j}^{\text{original}} ) \ge \tau_{j}^{\text{sta}} \cdot T_{i,i',j}^{\text{original}} $$
(7)
$$ (a_{i,j} - a_{{i^{\prime },j}} ) + N(1 - T_{{i,i^{\prime },j}}^{\text{reschedule}} ) \ge \tau_{j}^{\text{sta}} \cdot T_{{i,i^{\prime },j}}^{\text{reschedule}} $$
(8)
  1. (e)

    Track restrictions:

$$ \sum\limits_{l = 1}^{{w_{j} }} {\lambda_{i,j}^{l} = 1} $$
(9)

2.2 Energy-Saving Problem

The purpose of this part is to optimize the energy efficiency of the train timetable. The energy consumption is taken as the optimization target.

  1. (1)

    The Decision Variables

\( t_{k} \) is the optimal operation time of train in section k. \( v_{y}^{k} \) is train constant speed. \( t_{d}^{k} \) is train coasting time. \( S_{f}^{k} \), \( S_{y}^{k} \), \( S_{d}^{k} \), and \( S_{b}^{k} \) are train acceleration, cruising, coasting and braking distance in section k respectively. \( E_{i} (t_{k} ) \) is the energy consumption.

  1. (2)

    The optimization objective

$$ \hbox{min} \, z_{e} = \hbox{min} \sum\limits_{i \in I} {\sum\limits_{k \in K} {E_{i} (t_{k} )} } , $$
(10)
$$ E_{i} (t_{k} ) = \int\limits_{0}^{{t_{k} }} {k_{f} (t) \cdot v(t) \cdot F(t){\text{d}}t} . $$
(11)

\( k \) is running section and \( K \) is running section set. \( i \) is train and \( I \) is train set. \( z_{\text{e}} \) is energy consumption. \( k_{f} (t) \) is traction coefficient, \( k_{f} \in [0,1] \). \( v(t) \) is speed.

  1. (3)

    The Constraints

\( k_{b} \) is braking force coefficient. \( k_{\text{b}} \in \{ 0,1\} \). \( M \) is train quality. \( W \) is running resistance, here we only consider the basic resistance. \( t_{f}^{k} \), \( t_{y}^{k} \), and \( t_{\text{b}}^{q} \) is train acceleration, cruising, and braking time respectively. \( S \) is the total distance. \( {\text{V}}_{0} \) is initial speed. \( V_{T} \) is final speed and \( V_{\hbox{max} } \) is maximum speed allowed. \( t_{k}^{\hbox{min} } \) and \( t_{k}^{\hbox{max} } \) are the minimum and maximum limits. T is the total running time after the upper model is adjusted.

  1. (a)

    Force restrictions:

$$ k_{f} F - k_{b} B - W = M \cdot {{({\text{d}}v(t)} \mathord{\left/ {\vphantom {{({\text{d}}v(t)} {{\text{d}}t)}}} \right. \kern-0pt} {{\text{d}}t)}} $$
(12)
  1. (b)

    Distance restrictions:

$$ \left\{ {\begin{array}{*{20}l} {S = \sum {S^{ * } } ,} \hfill \\ {S^{ * } = \int\limits_{0}^{{t^{ * } }} {v(t){\text{d}}t} .} \hfill \\ \end{array} } \right. $$
(13)

When \( S^{ * } = S_{\text{f}}^{k} \), then \( t^{ * } = t_{\text{f}}^{k} \); similarly, when \( S^{ * } = S_{d}^{k} \), \( t^{ * } = t_{\text{d}}^{k} \); when \( S^{ * } = S_{b}^{k} \), \( t^{ * } = t_{b}^{k} \); when \( S^{ * } = S_{y}^{k} \), \( t^{ * } = t_{y}^{k} \), and the formula is equivalent to \( S_{y}^{k} = v_{y}^{k} \cdot t_{y}^{k} \).

  1. (c)

    Speed restrictions:

$$ \left\{ {\begin{array}{*{20}l} {V_{0} = 0} \hfill \\ {V_{T} = 0} \hfill \\ {v \le V_{\hbox{max} } .} \hfill \\ \end{array} } \right. $$
(14)
  1. (d)

    Time restrictions:

$$ \left\{ {\begin{array}{*{20}l} {t_{k} = \sum {t_{ * }^{k} } ,\quad t_{ * }^{k} \in \left[ {t_{f}^{k} ,t_{y}^{k} ,t_{d}^{k} ,t_{b}^{k} } \right]} \hfill \\ {t_{k}^{\hbox{min} } \le t_{k} \le t_{k}^{\hbox{max} } } \hfill \\ {\sum\limits_{k \in K} {{\text{t}}_{k} } = T.} \hfill \\ \end{array} } \right. $$
(15)
  1. (e)

    Tracking interval restrictions:

The purpose of the restrictions is to ensure that the departure and arrival time of adjacent train i and train i′ satisfies the minimum tracking interval in the station, and the running time satisfies the minimum tracking interval in section. The specific expression of the tracking interval is the same as the upper layer.

3 Solving Algorithm

An iterative loops algorithm is designed to solve the model. First, the arrival and departure time is adjusted by the upper layer. Second, the time is optimized by lower layer. Third, the result is returned back to the upper layer to check the constraints. So it is iterated, and is expected to converge to an optimized solution.

  • Step 1: The adjustment of the arrival, departure, and stop time.

    • Step 1.1: Read the file, and get train, station, line, and late information.

    • Step 1.2: Select the Wuhan to Guangzhou railway data, and sort the train.

    • Step 1.3: Adjust the timetable according to the constraints using Ilog Cplex.

    • Step 1.4: Get the arrival and departure time after the train is adjusted.

  • Step 2: Energy-saving optimization

    • Step 2.1: Calculate the shortest running time of all trains.

    • Step 2.2: Calculate the spare time between the adjusted and shortest time.

    • Step 2.3: Distribute the spare time little by little using MATLAB.

      • Step 2.3.1: Divide the total spare time into small portions.

      • Step 2.3.2: Each section adds the same amount of spare time.

      • Step 2.3.3: Select the section with the most energy reduction to add the small amount of spare time, and time in other section is unchanged.

    • Step 2.4: Get optimized train arrival and departure time.

  • Step 3: Check whether the result meets the constraints of the upper layer.

    • Step 3.1: If all the constraints are met, go to step 4.

    • Step 3.2: Otherwise, go to step 1.3.

  • Step 4: Output the integrated timetable.

    • Step 4: Output the integrated timetable.

4 Case Study

The total length of the railway line is 1069 km, and includes 16 stations. Select the data from 9 to 11 o’clock, and there are 11 trains. Sorting them by start time is G77, G1109, G1111, G1143, G1007, G551, G93, G1113, G541, G1011, and G1115. Since the high-speed line is a double track, we only consider the direction from Wuhan to Guangzhou without loss of generality.

In this paper, a very short delay is studied. Because the timetable only contains 2 hours, so more serious delay is not considered.

4.1 The Delay Adjustment

In this section, the delay time is set to within 5 min. To simplify the analysis process, the delay of G1115 is not considered, because it is the last train.

Observe the train timetable: (a) The average departure time interval is 4 min, so the delay is easy to spread. (b) After three times overtaking, G93 became the fifth train to reach the terminal station, so a small delay in G93 will have a great impact on other trains. In the case study, the delay time of G77, G1143, and G93 is set 3, 5, and 2 min, respectively.

All the trains are in accordance with the original timetable to reach the terminal station, of which arrival and departure time of 5 intermediate stations has changed, as shown in Fig. 1, and the total time delayed on intermediate stations is 652 s. The search time of the algorithm is 0.17 s, which shows the feasibility of the algorithm (Table 1).

Fig. 1
figure 1

Change of the dwell time after a very short delay

Full size image
Table 1 Train delay after optimization
Full size table

The impact of the delay on G1143 is the largest, and G1143 stops in Guangzhou North for nearly 400 s. The increase in dwelling time is to make G93 to overtake. Then, the result is input to the lower layer to further optimize.

4.2 Energy-Saving Optimization

Table 2 shows the energy consumption value of each train under different time conditions. Here we take the train drive system energy conversion efficiency as \( \eta = 0.9 \). Experience has indicated that the eight groups of CRH series EMU trains running 1069 km will consume 8018 kw h electric energy. Based on this data, after energy-saving optimization, the whole line can save energy 2744.210 kw h, accounting for 3.1% of the total energy, and the energy-saving effect is obvious.

Table 2 Train energy consumption comparison table
Full size table

5 Conclusion

This paper presents a bi-level integrated programming approach on high-speed railway timetable rescheduling, which is designed to optimize the timetable under the delayed condition. The upper layer reschedules the timetable by considering the minimum delay time and the constraints, so that the train movement can be consistent with the original schedule as much as possible. In the lower layer, the energy efficiency is optimized under the constraints by the small-scale adjustment of the arrival and departure time at intermediate stations. Taking the actual operation data of Wuhan to Guangzhou high-speed railway as an example, the case study is carried out on a different degree of time delay, and the results verify the feasibility of the model and algorithm.