Metro train rescheduling by adding backup trains under disrupted scenarios

Abstract

In large cities with heavily congested metro lines, unexpected disturbances often occur, which may cause severe delay of multiple trains, blockage of partial lines, and reduction of passenger service. Metro dispatchers have taken a practical strategy of rescheduling the timetable and adding several backup trains in storage tracks to alleviate waiting passengers from crowding the platforms and recover from such disruptions. In this study, we first develop a mixed integer programming model to determine the optimal train rescheduling plan with considerations of in-service and backup trains. The aim of train rescheduling is to frequently dispatch trains to evacuate delayed passengers after the disruption. Given the nonlinearity of the model, several linearization techniques are adapted to reformulate the model into an equivalent linear model that can be easily handled by the optimization software. Numerical experiments are implemented to verify the effectiveness of the proposed train rescheduling approach.

Graphical abstract

Keywords

train rescheduling / backup train / metro line / disruption / timetable

1 Introduction

Metro network is the main component of public transportation systems and is typically regarded as the “main arteries” of large cities because this network punctually delivers many passengers to their destinations, which is particularly convenient for tide commuters (Vuchic, 2005). Until now, the Beijing Metro system operates with 17 lines totaling for 570 km. In 2016, the Beijing Metro system has carried approximately 10 million passengers in average (Beijing Subway, 2016). In addition, the metro network can evidently release the road traffic congestion problems in large cities, such as Beijing, Tokyo, Singapore, and Los Angeles, because this network accounts for a large part of traveling demands (Yin et al., 2014).

Meanwhile, the dramatic expansion of residents in recent years has pressured the urban metro systems in China to address the increasing passenger demands. On the one hand, increasing passenger demands overload the trains, thus causing many issues in metro systems management. Many frequent perturbances, such as the breakdown of singling systems, vehicles, and platform screen doors (PSD), typically delay the daily operations of metro trains for several minutes or over 10 min (Yin et al., 2016a, 2016b). Consequently, these disturbances evidently reduce the reliability of equipment and infrastructure. For example, in the first quarter of 2017, Beijing Metro has reported at least 327 faults due to train breakdown and 81 faults from PSDs. Although most of these accidents only last for several minutes, these perturbances still delay many train services. On the other hand, as passenger demands increase, any small perturbance that delays the trains can still cause severe subsequent issues (Gao et al., 2016). For example, the numbers of waiting passengers double during peak hours when trains are three minutes delayed. Similarly, delay causes over-crowded platforms and even results in safety issues, such as panic-stricken stampede.

Therefore, taking an emergency response plan in case of disruptions, such as evacuating waiting passengers at platforms to immediately recover the normal operational state, is significantly practical. The train rescheduling approach is commonly regarded as the primary approach of the metro dispatchers in response to disruption scenarios. Currently, metro trains operate with high frequency and short following headway during peak hours in large cities. Maintaining appropriate train following headway in avoiding the potential collision between two trains is critical and difficult for metro dispatchers. In addition, most of the existing metro lines are constructed with several storage tracks that enable metro dispatchers to store a backup train for rescheduling purposes in case of disruptions. Thus, if we want to add a backup train under disrupted scenarios, then we must first consider the current information of all the existing service trains along the metro line. Then, we must carefully reschedule their departure and arrival times to realize a globally coordinated train dispatching plan between existing and new trains with guaranteed safety train following margin.

The contribution of this paper is the development of a new approach in rescheduling the timetable of trains for a metro line that explicitly involves backup trains. In particular, an optimization model is proposed to generate an optimal train schedule considering in-service and new backup trains in disrupted situations. The model reformulation proves that the nonlinear model can be linearized and efficiently solved by exact algorithms or optimization software.

2 Literature review

The train scheduling/rescheduling problem aims to generate/regenerate a timetable employed by trains in railway lines, which lays the foundation of railway management/operations and has attracted tremendous attention in recent years (Zhou and Zhong, 2007; Cacchiani and Toth, 2012; Cacchiani et al., 2014; Wang et al., 2015; Huang et al., 2016; Altazin et al., 2017; Yin et al., 2017).

In general, given that the generated train timetable is usually unchanged in a certain time period (e.g., days or months), the train scheduling problem is usually addressed in the planning stage. For example, Beijing Metro developed several kinds of timetables that correspond to weekday, weekend, and holiday train operation plans. In this sense, the objective of the train scheduling problem is commonly influenced by the number of trains, transport capacity, train energy consumption, and estimated passenger waiting time. For example, Niu and Zhou (2013) formulated a nonlinear optimization model by considering the train scheduling problem of a metro line with time-dependent and oversaturated demand. A genetic algorithm with binary coding was adopted to obtain the timetabling scheme. Wang et al. (2017) proposed a two-stage optimization approach to generate the optimal train schedule and circulation plan to minimize the number of required trains in daily metro line operation. Barrena et al. (2014) developed two nonlinear mathematical models to obtain an uneven train schedule that coordinates with the dynamic passenger demand to minimize the passenger waiting time in metro stations. Yin et al. (2017)formulated two mixed-integer linear programming (MILP) models that explicitly consider dynamic passenger demands and train operation curves on each segment to save energy consumption, utilize the regenerative braking energy of trains, and achieve a trade-off between passenger waiting time.

Different from the train scheduling problem in the planning phase, the train rescheduling problem immediately requires regeneration of a new timetable to compensate the damage of perturbances strictly limited by the computational speed issue (Cacchiani et al., 2014). In mainline railway systems, many works have already been undertaken (e.g., Corman and Quaglietta, 2015; Yang et al., 2014; Meng and Zhou, 2014) to generate a rescheduled train timetable in case of unexpected incidents. However, a few studies have focused on rescheduling a metro line after a disruption. Gao et al. (2016) proposed to reschedule the metro train timetable by using the stop-skipping strategy after a disruption and developed a mathematical model with linearization and decomposition techniques in reducing computational complexity. Altazin et al. (2017) accomplished a similar research. Nevertheless, application of the stop-skipping strategy is usually not allowed in practical metro train rescheduling process because stop-skipping would even increase the travel time of some passengers. Yin et al. (2016a) proposed a train timetable rescheduling model based on time-variant and uncertain passenger demands. Minimizing the traveling time of passengers can be obtained by using an approximated dynamic programming method in the rescheduled timetable. However, the model cannot help overcome large delays nor evacuate over-crowded waiting passengers after a disruption. Li et al. (2017) developed an integrated approach for metro train regulation with a passenger flow control strategy. The problem was formulated into a quadratic programming model and efficiently solved by optimal control methods. Gao et al. (2017) proposed a real-time rescheduling strategy for urban rail lines considering the feedback information of faults (or disturbances) in the environment. In particular, they compared the metro train rescheduling performance with or without feedback information of faults. Despite insufficient quantitative analyses, Yamamura et al. (2014) investigated a few practical approaches to reduce delays in Tozai Line, Tokyo.

Typically, most existing metro lines are designed with several train storage sidings (or storage tracks) between two stations, which can be used for backup train storage for emergency usages. By contrast, the literature on utilizing backup trains has not studied recovery from disruptions. In this paper, we will explicitly address the train rescheduling problem by adding backup trains to recover from a disruption in a double-direction metro line.

3 Model formulation

In this section, we first present the general symbols and decision variables used in this paper. A mathematical model, which includes basic constraints and objective function, was then developed and reformulated into an MILP model using several linearization techniques.

3.1 Symbols and decision variables

K_E Set of existing trains in the metro line

K_F Set of future trains that depart from the origin station

K_A Set of newly added backup trains to the metro line from train storage sidings

k_e Number of considered existing trains

k_f Number of considered future trains

k_a Number of added backup trains

k, lIndex of trains, k,l\in K_E\cup K_F\cup K_A

S Set of physical stations in the considered metro line

S_k Set of stations that are involved in train service k

i,\hspace{0.17em}jIndex of stations, i\in S_k

S_T Index of the turn-around station

T_{turn}Turn-around time at station S_T

d_i^{\max } Maximum train dwelling time at each station

d_i^{\min }

Minimum train dwelling time at each station

h_{\min } Minimum train following headway between two consecutive trains

r_{i+\mathrm{1},i} Train running time between station i and i + 1

Decision variables:

x_{k,i} Arrival time at station i in service k (Integer variable)

y_{k,i} Departure time from station i in service k (Integer variable)

z_{k,l} Train order indicator (0–1 variable). For each l\in K_A and

k\in K_E\cup K_F

,

z_{k,l}=\mathrm{1}

if train l departs after train k; otherwise, z_{k,l}=\mathrm{0}.

p_{k,l} Train order indicator (0–1 variable). For each k,l\in K_A,p_{k,l}=\mathrm{1} if train l departs after train k; otherwise, p_{k,l}=\mathrm{0}.

We use Fig. 1 as an example to explain the definitions of the preceding symbols and decision variables presented in this study. In this example, we consider a metro line with eight physical stations, that is, \left|S\right|=\mathrm{8}. Two storage sidings dwelling two backup trains, which are between stations 1 and 2, as well as 6 and 7, exist. In this study, we assume that the power supply system has broken down at station 4 and blocked the following trains at stations or segments. At the current time t_{\mathrm{0}}, the disruption is over, that is, the power supply system is fixed, and many passengers are still left stranded in stations. We focus on rescheduling the timetable using backup trains in the storage lines during the disruption recovery period. In particular, this study explicitly considers three kinds of service trains during the recovery period starting from time t_{\mathrm{0}}. First, a few trains that have already traveled into the metro line are termed as existing trains, that is, set K_E (for example, existing trains 1 to 4 in Fig. 1). When disruption begins the recovery period, these existing trains dwell at different stations along the metro line. The second kind of train is the backup train, that is, backup trains 1 and 2 in storage sidings. The third kind of train refers to trains that have not yet departed from the origin station 1. In this study, we call these trains as future trains, that is, set K_F. As the existing and backup trains have traveled through a few stations and segments, we have S_k=\{\mathrm{2},\mathrm{3},\mathrm{4},\mathrm{5},\mathrm{6},\mathrm{7},\mathrm{8}\}for existing train service 1,S_k=\{\mathrm{3},\mathrm{4},\mathrm{5},\mathrm{6},\mathrm{7},\mathrm{8}\} for existing train service 2, and S_k=\{\mathrm{7},\mathrm{8}\} for backup train service 2. For simplicity, the train service is simplified as “train” in the following sections of this paper.

The set of decision variables includes the arrival and departure times of these trains. Particularly, given that this paper aims to optimize the rescheduled timetable for three kinds of trains involved, adding these backup trains notably influence the train orders. For example, if the original train order is K=\{e_{\mathrm{1}},e_{\mathrm{2}},\cdots f_{\mathrm{1}},f_{\mathrm{2}},\cdots \}with the addition of backup trains a_{\mathrm{1}} and a_{\mathrm{2}} into the operation, then many feasible choices are obtained for the rescheduled train order, that is, K=\{e_{\mathrm{1}},a_{\mathrm{1}},e_{\mathrm{2}},\cdots f_{\mathrm{1}},a_{\mathrm{2}},f_{\mathrm{2}},\cdots \}and K=\{e_{\mathrm{1}},e_{\mathrm{2}},a_{\mathrm{1}},\cdots f_{\mathrm{1}},f_{\mathrm{2}},a_{\mathrm{2}},\cdots \}. Therefore, we also define two sets of train order indicators, namely z_{k,l} and p_{k,l}, to represent the train orders in the rescheduled timetable.

3.2 Constraints

Next, we introduce the basic constraints for the train rescheduling problem with backup trains, such as train running time, dwelling time, headway, and turn-around constraints.

Running time constraints

(1)x_{k,i+\mathrm{1}}-y_{k,i}=r_{i+\mathrm{1},i}\hspace{0.17em}\mathit{f}\mathit{o}\mathit{r}\hspace{0.17em}k\in K_E\cup K_F\cup K_A\hspace{0.17em}\mathit{a}\mathit{n}\mathit{d}\hspace{0.17em}i,i+\mathrm{1}\in S_k

In this study, we assume that the running time on each segment (i,\hspace{0.17em}i+\mathrm{1}) between station i and station i + 1 is a constant value r_{i+\mathrm{1},i} (Yin et al., 2016c). Therefore, for each k\in K_E\cup K_F\cup K_A, arrival and departure times are restricted by this set of constraints as depicted in inequality (1).

Dwelling time constraints

(2)y_{k,i}-x_{k,i}\le d_i^{\max }\hspace{0.17em}\mathit{f}\mathit{o}\mathit{r}\hspace{0.17em}k\in K_E\cup K_F\cup K_A\hspace{0.17em}\mathit{a}\mathit{n}\mathit{d}\hspace{0.17em}i\in S_k

(3)y_{k,i}-x_{k,i}\ge d_i^{\min }\hspace{0.17em}\mathit{f}\mathit{o}\mathit{r}\hspace{0.17em}k\in K_E\cup K_F\cup K_A\hspace{0.17em}\mathit{a}\mathit{n}\mathit{d}\hspace{0.17em}i\in S_k

The two sets of constraints have established the upper and lower bounds for the dwelling times of trains at each station. Given that trains have already gone through a part of these stations, service stations for trains are actually different.

Train headway constraints

Guaranteeing the minimum train following headway is the most important constraint for normal circumstances and emergency cases to maintain the safety of trains and avoid potential collisions. For normal circumstances, guaranteeing the safety headway is relatively easy because the train running orders are always fixed with respect to the metro line, and trains will follow one another according to the pre-determined timetable. However, adding the backup trains into the metro line is different because the safety headway needs stability between the new and in-service trains. In particular, the insertion of these backup trains into the original timetable essentially changes the original train running orders, which require modifications on the traditional headway constraints in prior studies. Specifically, we propose three sets of constraints as follows.

(1) Train headway constraints for the in-service trains

(4)y_{k+\mathrm{1},i}-y_{k,i}\ge h_{\min }\hspace{0.17em}\mathit{f}\mathit{o}\mathit{r}\hspace{0.17em}k\in K_E\cup K_F\hspace{0.17em}\mathit{a}\mathit{n}\mathit{d}\hspace{0.17em}i\in S_k

(5)x_{k+\mathrm{1},i}-x_{k,i}\ge h_{\min }\hspace{0.17em}\mathit{f}\mathit{o}\mathit{r}\hspace{0.17em}k\in K_E\cup K_F\hspace{0.17em}\mathit{a}\mathit{n}\mathit{d}\hspace{0.17em}i\in S_k

With this set of constraints, we first guarantee that the existing and future trains determined by the original timetable will maintain the similar train running order under safety train following margin.

(2) Train headway constraints between in-service and backup trains

If the decision variable z_{k,l}=\mathrm{1}, then the following constraints are added into the model:

(6)\{\begin{array}{l}{y}_{k+\mathrm{1},i}-y_{l,i}\ge h_{\min }\\ y_{l,i}-y_{k,i}\ge h_{\min }\end{array}\hspace{0.17em}\mathit{f}\mathit{o}\mathit{r}\hspace{0.17em}i\in S_l,\hspace{0.17em}k,k+\mathrm{1}\in K_E\cup K_F,\hspace{0.17em}l\in K_A

When the decision variable z_{k,l}=\mathrm{1}, the added train l is right between service train k + 1 and train k. The preceding constraints then guarantee the safety train following headway between each added train l, in-service trains k, and k + 1 for k,k+\mathrm{1}\in K_E\cup K_F,\hspace{0.17em}l\in K_A.

(3) Train headway constraints between backup trains

If the decision variable p_{k,l}=\mathrm{1}, then the following constraints are added into the model:

(7)y_{l,i}-y_{k,i}\ge h_{\min }\hspace{0.17em}\mathit{f}\mathit{o}\mathit{r}\hspace{0.17em}\hspace{0.17em}i\in S_l\cup S_k,\hspace{0.17em}k,\hspace{0.17em}l\in K_A

Similarly, the preceding constraints guarantee the safety train following headway between the added trains l and k for k,l\in K_A.

Train order constraints

The following constraints guarantee departure of these backup trains. Specifically, each train should depart from the storage track to the metro line.

(8){\displaystyle \sum _{k\in K_E\cup K_F}{z}_{k,l}}=\mathrm{1}\hspace{0.17em}\mathit{f}\mathit{o}\mathit{r}\hspace{0.17em}l\in K_A

In addition, we also need to restrict the decision variable p_{k,l}, which actually determines the departure order of added backup trains.

(9){\displaystyle \sum _{l\in K_A}{p}_{k,l}}\le \mathrm{1}\hspace{0.17em}\mathit{f}\mathit{o}\mathit{r}\hspace{0.17em}k\in K_A

(10){\displaystyle \sum _{l\in K_A}{\displaystyle \sum _{k\in K_A}{p}_{l,k}}=k_a}-\mathrm{1}

(11)p_{k,l}=\mathrm{0}\hspace{0.17em}\mathit{f}\mathit{o}\mathit{r}\hspace{0.17em}k,\hspace{0.17em}l\in K_A,\hspace{0.17em}k=l

Remark 2.1 Notably, constraint (9) indicates that for each backup train k, one train l at most departs right after train k. Specifically, constraint (9) defines the running order of these backup trains. Constraint (10) assumes the departure of all these backup trains, and the last backup train to depart has a departure indicator of zero. Constraint (11) defines that for each train k, the departure indicator p_{k,l} is zero with respect to train k itself.

An illustration example is shown in Fig. 2, in which we consider three backup trains (numbered as 1, 2, and 3), three existing trains, and four future trains. Evidently, the three backup trains depart after existing train 1, existing train 2, and future train 3. Therefore, z_{k_{e\mathrm{1}},\mathrm{1}}=\mathrm{1}, z_{k_{e\mathrm{2}},\mathrm{2}}=\mathrm{1}, and z_{k_{f\mathrm{3}},\mathrm{3}}=\mathrm{1} define the backup train departure orders, in which k_{e\mathrm{1}}, k_{e\mathrm{2}}, k_{f\mathrm{3}} represent existing train 1, existing train 2, and future train 3, respectively. Moreover, given that backup train 2 follows backup train 1 and backup train 3 follows backup train 2, we can denote the train departure order among the three backup trains from this example, where p_{\mathrm{1},\mathrm{2}}=\mathrm{1} and p_{\mathrm{2},\mathrm{3}}=\mathrm{1}. In this sense, we have {\displaystyle \sum _{l\in K_A}{\displaystyle \sum _{k\in K_A}{p}_{l,k}}=k_a}-\mathrm{1}=\mathrm{2}. In addition, the preceding train order constraints guarantee the train departure orders for the three kinds of trains.

Train turn-around constraints

(11)y_{k,i+\mathrm{1}}-y_{k,i}=T_{turn}\hspace{0.17em}\mathit{f}\mathit{o}\mathit{r}\hspace{0.17em}k\in K_E\cup K_F\cup K_A\hspace{0.17em}\mathit{a}\mathit{n}\mathit{d}\hspace{0.17em}i=S_T

This constraint guarantees that each train uses time T_{turn} to turn their running direction at the turn-around station.

3.3 Objective function

After a disruption in metro lines, the primary objective for dispatchers is to enhance the transport capacity of the disrupted metro system, evacuate dwelling passengers at each station, and immediately recover normal operational states. Specifically, frequently dispatching trains is required to fill the gap between overflowing passenger demand and disrupted line carrying capacity. Therefore, this study particularly considers the arrival time of the last train as the objective function. Notably, two possibilities exist with respect to the last train. The last train may be regarded as one of the future trains in K_F or one of the backup trains K_A. Thus, we aim to minimize the objective function as follows:

(12)\min Z=\min \max \left\{y_{k_f,I},\hspace{0.17em}{\displaystyle \sum _{k\in K_A}\left(\mathrm{1}-{\displaystyle \sum _{l\in K_A}{p}_{k,l}}\right)y_{k,I}}\right\}

Remark 2.2 In the preceding equation, the left side of the max function, that is, y_{k_f,I}, represents the departure time of the last future train k_f at the destination station I. However, the order of backup trains is actually not pre-given but determined by decision variable p_{k,l}. In this study, the right side of the max function essentially denotes the departure time of the last backup train at the destination.

Based on the preceding formulations, constraints (1)–(11) and the objective function (12) can obtain the train rescheduling model with backup trains. Nevertheless, this model contains two sets of if-then constraints (6) and (7), and the objective function (12) has a max function with quadratic formulations. Thus, solving through commercial solvers, such as CPLEX or Gurobi, is difficult. Therefore, we reformulate this model through several linearization techniques to efficiently solve the following content.

3.4 Model Reformulation

In this section, we reformulate constraints (6) and (7) into equivalent linear constraints. Similarly, the max function is reformulated into objective function (12) by introducing a set of intermedia variables and constraints.

Lemma 1. For i\in S_l,\hspace{0.17em}k\in K_E\cup K_F,\hspace{0.17em}l\in K_A, constraint (6) can be equivalently replaced by the following linear constraints:

y_{k+\mathrm{1},i}-y_{l,i}+(\mathrm{1}-z_{k,l})\cdot M\ge h_{\min },

y_{l,i}-y_{k,i}+(\mathrm{1}-z_{k,l})\cdot M\ge h_{\min },

where M is a sufficiently large positive value.

Lemma 2. For \hspace{0.17em}i\in S_l\cup S_k,\hspace{0.17em}k,\hspace{0.17em}l\in K_A, constraint (7) can be equivalently replaced by the following linear constraints:

y_{l,i}-y_{k,i}+(\mathrm{1}-p_{k,l})\cdot M\ge h_{\min }.

Lemma 3. The objective function (12) can be replaced by formulation with additional variables and constraints.

\min \hspace{0.17em}w

With additional constraints:

(13)y_{k_f,I}\le w

(14)y_{k,I}-M\cdot {\displaystyle \sum _{l\in K_A}{p}_{k,l}}\le w\hspace{0.17em}for\hspace{0.17em}k\in K_A

(15)y_{k_f,I}\ge w-(\mathrm{1}-{\lambda }_{\mathrm{1}})\cdot M

(16)y_{k,I}+M\cdot {\displaystyle \sum _{l\in K_A}{p}_{k,l}}\ge w-(\mathrm{1}-{\lambda }_{\mathrm{2}})\cdot M\hspace{0.17em}for\hspace{0.17em}k\in K_A

(17){\lambda }_{\mathrm{1}}+{\lambda }_{\mathrm{2}}=\mathrm{1},

in which w is a continuous variable, and {\lambda }_{\mathrm{1}} and {\lambda }_{\mathrm{2}} are 0–1 integer variables. Clearly, the preceding objective function and constraints are all manageable linear expressions.

Proof:

Verifying Lemmas 1–2 is not difficult because we simply adopt a big-M method to represent the if-then rules. Therefore, we omit the proofs in this paper and only focus on the proof of Lemma 3, that is, the linearization of the objective function.

First, we reformulate the max function. For simplification, we use Z=\max \{Y_{\mathrm{1}},Y_{\mathrm{2}}\} to represent the original objective function, in which Y_{\mathrm{1}}=y_{k_f,I} and

Y_{\mathrm{2}}={\displaystyle \sum _{k\in K_A}\left(\mathrm{1}-{\displaystyle \sum _{l\in K_A}{p}_{k,l}}\right)y_{k,I}}

. For the max function in this formulation, we introduce a continuous variable w, and two 0–1 integer variables{\lambda }_{\mathrm{1}} and {\lambda }_{\mathrm{2}}. Thus, the objective function Z can be rewritten as follows:

(18)Z=w,

(19)Y_{\mathrm{1}}\le w,

(20)Y_{\mathrm{2}}\le w,

(21)Y_{\mathrm{1}}\ge w-(\mathrm{1}-{\lambda }_{\mathrm{1}})\cdot M,

(22)Y_{\mathrm{2}}\ge w-(\mathrm{1}-{\lambda }_{\mathrm{2}})\cdot M,

(23){\lambda }_{\mathrm{1}}+{\lambda }_{\mathrm{2}}=\mathrm{1.}

Thus, if Y_{\mathrm{1}}=Y_{\mathrm{2}}, then the preceding constraints can be guaranteed, and Z will be equal to the maximum between Y_{\mathrm{1}} and

Y_{\mathrm{2}}

. When Y_{\mathrm{1}}>Y_{\mathrm{2}}, we can combine inequalities (19) and (21)

w\ge Y_{\mathrm{1}}>Y_{\mathrm{2}}\ge w-(\mathrm{1}-{\lambda }_{\mathrm{2}})\cdot M,

which is rewritten as (\mathrm{1}-{\lambda }_{\mathrm{2}})\cdot M>\mathrm{0}. Thus, we have {\lambda }_{\mathrm{2}}=\mathrm{0}and {\lambda }_{\mathrm{1}}=\mathrm{1}. Taking back the two values to inequalities (21) and (22), the two following inequalities are obtained:Y_{\mathrm{1}}\ge w

Y_{\mathrm{2}}\ge w-M

Given that we have Y_{\mathrm{1}}\ge wand

Y_{\mathrm{1}}\ge w

, we have Y_{\mathrm{1}}=wand Z=Y_{\mathrm{1}}, which is actually the larger value between Y_{\mathrm{1}}and Y_{\mathrm{2}}. Similarly, we haveZ=Y_{\mathrm{2}}if Y_{\mathrm{2}}is larger than Y_{\mathrm{1}}. Therefore, we prove that the original objective function can be equivalently reformulated by (18)–(23).

Next, we focus on the linearization of

Y_{\mathrm{2}}={\displaystyle \sum _{k\in K_A}\left(\mathrm{1}-{\displaystyle \sum _{l\in K_A}{p}_{k,l}}\right)y_{k,I}}

, which has a quadratic function with respect to variables Z and Y. According to constraints (9)–(11), we note that

\begin{array}{l}{\displaystyle \sum _{k\in K_A}\left(\mathrm{1}-{\displaystyle \sum _{l\in K_A}{p}_{k,l}}\right)=k_a}-{\displaystyle \sum _{k\in K_A}{\displaystyle \sum _{l\in K_A}{p}_{k,l}}}\\ \hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}=k_a-(k_a-\mathrm{1})\\ \hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}=\mathrm{1.}\end{array}

Given that {\displaystyle \sum _{l\in K_A}{p}_{k,l}}is also an integer variable between 0 and 1, only one of y_{k,I}when

\mathrm{1}-{\displaystyle \sum _{l\in K_A}{p}_{k,l}}=\mathrm{1}

will evidently be added. Specifically, constraints Y_{\mathrm{2}}\le w and Y_{\mathrm{2}}\ge w-(\mathrm{1}-{\lambda }_{\mathrm{2}})\cdot Mcan be reformulated as:

y_{k,I}-M\cdot {\displaystyle \sum _{l\in K_A}{p}_{k,l}}\le w\hspace{0.17em}for\hspace{0.17em}k\in K_A

y_{k,I}+M\cdot {\displaystyle \sum _{l\in K_A}{p}_{k,l}}\ge w-(\mathrm{1}-{\lambda }_{\mathrm{2}})\cdot M\hspace{0.17em}for\hspace{0.17em}k\in K_A

According to the preceding derivations, we can thus prove Lemma 3.

Through the model reformulation approach, we formulate the train rescheduling problem with backup trains as an MILP model given as follows:

\{\begin{array}{l}\min \hspace{0.17em}\hspace{0.17em}w\\ s.t.\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}{x}_{k,i+\mathrm{1}}-y_{k,i}=r_i\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\forall k\in K_E\cup K_F\cup K_A,\hspace{0.17em}\hspace{0.17em}i,i+\mathrm{1}\in S_k\\ \hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}{y}_{k,i}-x_{k,i}\le d_i^{\max }\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\forall k\in K_E\cup K_F\cup K_A,\hspace{0.17em}\hspace{0.17em}i\in S_k\\ \hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}{y}_{k,i}-x_{k,i}\ge d_i^{\min }\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\forall k\in K_E\cup K_F\cup K_A,\hspace{0.17em}\hspace{0.17em}i\in S_k\\ \hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}{y}_{k+\mathrm{1},i}-y_{k,i}\ge h_{\min }\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\forall k\in K_E\cup K_F,\hspace{0.17em}\hspace{0.17em}i\in S_k\\ \hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}{x}_{k+\mathrm{1},i}-x_{k,i}\ge h_{\min }\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\forall k\in K_E\cup K_F,\hspace{0.17em}\hspace{0.17em}i\in S_k\\ \hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}{y}_{k,i+\mathrm{1}}-y_{k,i}=T_{turn}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\forall k\in K_E\cup K_F\cup K_A,i=S_T\\ \hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}{y}_{k+\mathrm{1},i}-y_{l,i}+(\mathrm{1}-z_{k,l})\cdot M\ge h_{\min }\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\forall i\in S_l,\hspace{0.17em}k\in K_E\cup K_F,\hspace{0.17em}l\in K_A\\ \hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}{y}_{l,i}-y_{k,i}+(\mathrm{1}-z_{k,l})\cdot M\ge h_{\min }\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\forall i\in S_l,\hspace{0.17em}k\in K_E\cup K_F,\hspace{0.17em}l\in K_A\\ \hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}{y}_{l,i}-y_{k,i}+(\mathrm{1}-p_{k,l})\cdot M\ge h_{\min }\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\forall i\in S_l\cup S_k,\hspace{0.17em}k,\hspace{0.17em}l\in K_A\\ \hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}{\displaystyle \sum _{k\in K_E\cup K_F}{z}_{k,l}}=\mathrm{1}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\forall l\in K_A\\ \hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}{\displaystyle \sum _{l\in K_A}{p}_{k,l}}=\mathrm{1}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\forall k\in K_A\\ \hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}{\displaystyle \sum _{l\in K_A}{\displaystyle \sum _{k\in K_A}{p}_{l,k}}=k_a}-\mathrm{1}\\ \hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}{p}_{k,l}=\mathrm{0}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\forall k,\hspace{0.17em}l\in K_A,k=l\\ \hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\mathrm{Constraints}\hspace{0.17em}(\mathrm{13})-(\mathrm{17})\hspace{0.17em}\\ \hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}x,y\in N,\hspace{0.17em}z,p\in \{\mathrm{0},\mathrm{1}\}\end{array}

4 Numerical experiments

In this section, we adopt several numerical experiments to test the effectiveness of the proposed approach. The proposed model is coded in Visual Studio C⁺⁺ 2012 on a Windows 8 personal computer. We use the commercial ILOG CPLEX 12.3 Academic Version to solve the formulated model.

4.1 Parameter settings

As shown in Fig. 3, a two-direction metro line with eight stations and three storage sidings is considered to be the traffic environment. The three backup trains, which depart from stations 3, 5, and 7, are located in each storage track. We assume that an error has occurred in this metro line and severely delayed trains. After the disruption, three existing trains are located in stations 2, 4, and 6. Moreover, five future trains that will depart from station 1 are considered in this numerical experiment. The running time for the trains on each segment is set as 120 s. The minimum and maximum dwelling times of trains are set as 30 and 50 s, respectively.

4.2 Results analyses

First, we test the model for the 11 trains with a minimum headway of 200 s. Notably, the proposed model is eventually formulated into an MILP model, which can be handled by a few commercial solvers, such as CPLEX or LINGO. In our study, the model is coded in a Visual Studio environment using C+ + language, and the model is then solved by CPLEX. Typically, CPLEX takes approximately 0.2 s to solve the model with this scale into an optimality of 0%, which is very time-efficient.

Figure 4 illustrates the optimal train rescheduling timetable with three backup trains plotted by red solid lines. The rescheduled timetable shows that all three kinds of trains, that is, existing trains (termed as E-Train), backup trains (termed as A-Train), and future trains (termed as F-Train), are completely separated from each other to guarantee the safety train following headway in a metro line. Interestingly, the backup trains are dispatched at different times and stations. For example, backup train 1 departs between existing trains 2 and 3, whereas the two other backup trains depart between future trains 1 and 2. Consequently, E-trains 1 and 2 have insufficient time due to headway constraints; hence, no backup train can be inserted between the two trains. In addition, E-train 3 evidently dwells at each station for a long time to allot sufficient margins for the insertion of backup train 1.

Table 1 demonstrates the optimal rescheduled timetable for these trains, with two values in each bracket representing arrival and departure times of each train at the stations. “-” represents that the train does not go through this station in the considered time horizon. The table also shows that the optimized departure time of the last train from station 8 is 2430 s, which is actually the earliest time that these trains can be dispatched into this metro line. Clearly, the short transmission time of these trains allows the evacuation of more passengers in a certain period, and the system recovers to normal states. In addition, the train headway constraints guarantee all these trains at each station. Specifically, for any of these trains, departure time from each station is larger than 200s compared with its former train.

Then, we also test the model for different minimum headway times of 11 trains, and the model is solved in the environment with the aid of CPLEX. We demonstrate their performances in Table 2, which involve the departure time of the last train from the last station, the average train departure time, and the computational time.

Table 2 shows that the computational time is within 1 s, which satisfies the real-time requirements in practical operations. In addition, the departure time of the last train and the average departure time are increased with long headway time between successive trains, which is consistent with our practical experiences. We also show rescheduled timetables under 120 and 150 s headway in Figs. 5 and 6, respectively, to demonstrate the effects of headway time. In Fig. 5 with short train following headway, all these backup trains are added between the existing trains, which shorten the time for dispatching future trains and evacuating delayed passengers at each station. For the case of long headway, that is, h_min = 150 s, Fig. 6 demonstrates that only two trains can be inserted between the existing trains, and one backup train has to depart between future trains. Therefore, we conclude that the train following headway (commonly determined by the train signaling system) essentially affects the rescheduling performance with backup trains. Therefore, a good train signaling system and short train following headway can considerably improve the feasibility of the rescheduling task with the aid of backup trains in storage tracks.

5 Conclusions

Given the increased demands of commuters in large cities, urban metro lines have been unified into an integrated system with high complexity that is extremely vulnerable to perturbances. Thus, managing this complex system in case of disruptions has become a practically significant yet theoretically challenging problem. In this paper, we have proposed a new approach for the rescheduling of metro trains after disruption using backup trains. In particular, this train rescheduling problem has been rigorously formulated into an MILP model considering train departure orders. Through model reformulation, the original model has been transformed into an equitant MILP model manageable for CPLEX. Numerical experiments have shown that the proposed approach can add backup trains into the rescheduled timetable under the train following headway constraints. Similarly, the results showed the relationship between train following headway and the feasibility of adding backup trains.

Adding backup trains is a practical and effective strategy that can be easily implemented in real-world operations for the metro system to recover from disruptions because most existing metro lines are designed with several train storage sidings. Our future research will focus on the backup train rescheduling problem that explicitly considers the modeling of passenger volumes. On the contrary, introducing passenger modeling in our formulations leads to the nonlinearity of formulations. Therefore, future studies must focus on designing efficient algorithms

References

[1] Altazin E, Dauzere Peres S, Ramond F, Tréfond S (2017). Rescheduling through stop-skipping in dense railway systems. Transportation Research Part C: Emerging Technologies, 79: 73–84

[2] Barrena E, Canca D, Coelho L C, Laporte G (2014). Single-line rail transit timetabling under dynamic passenger demand. Transportation Research Part B: Methodological, 70: 134–150

[3] Beijing Subway (2016). Beijing Subway Webpage.

[4] Cacchiani V, Huisman D, Kidd M, Kroon L, Toth P, Veelenturf L, Wagenaar J (2014). An overview of recovery models and algorithms for real-time railway rescheduling. Transportation Research Part B: Methodological, 63: 15–37

[5] Cacchiani V, Toth P (2012). Nominal and robust train timetabling problems. European Journal of Operational Research, 219(3): 727–737

[6] Corman F, Quaglietta E (2015). Closing the loop in real-time railway control: Framework design and impacts on operations. Transportation Research Part E: Logistics and Transportation Review, 54: 15–39

[7] Gao Y, Kroon L, Schmidt M, Yang L (2016). Rescheduling a metro line in an over-crowded situation after disruptions. Transportation Research Part B: Methodological, 93: 425–449

[8] Gao Y, Yang L, Gao Z (2017). Real-time automatic rescheduling strategy for an urban rail line by integrating the information of fault handling. Transportation Research Part C: Emerging Technologies, 81: 246–267

[9] Huang Y, Yang L, Tang T, Cao F, Gao Z (2016). Saving energy and improving service quality: Bicriteria train scheduling in urban rail transit systems. IEEE Transactions on Intelligent Transportation Systems, 17(12): 3364–3379

[10] Li S, Dessouky M M, Yang L, Gao Z (2017). Joint optimal train regulation and passenger flow control strategy for high-frequency metro lines. Transportation Research Part B: Methodological, 99: 113–137

[11] Meng L, Zhou X (2014). Simultaneous train rerouting and rescheduling on an N-track network: A model reformulation with network-based cumulative flow variables. Transportation Research Part B: Methodological, 67: 208–234

[12] Niu H, Zhou X (2013). Optimizing urban rail timetable under time-dependent demand and oversaturated conditions. Transportation Research Part C: Emerging Technologies, 36: 212–230

[13] Vuchic V R (2005). Urban Transit: Operations, Planning and Economics. New Jersey: John Wiley & Sons

[14] Wang Y, Liao Z, Tang T, Ning B (2017). Train scheduling and circulation planning in urban rail transit lines. Control Engineering Practice, 61: 112–123

[15] Wang Y, Tang T, Ning B, van den Boom T J J, De Schutter B (2015). Passenger-demands-oriented train scheduling for an urban rail transit network. Transportation Research Part C: Emerging Technologies, 60: 1–23

[16] Yamamura A, Koresawa M, Adachi S, Tomii N, (2014). Taking effective delay reduction measures and using delay elements as indices for Tokyo’s metropolitan railways. Computers in Railways XIV: Railway Engineering Design and Optimization, 135(3): 3–15

[17] Yang L, Zhou X, Gao Z (2014). Credibility-based rescheduling model in a double-track railway network: A fuzzy reliable optimization approach. Omega, 48: 75–93

[18] Yin J, Chen D, Li L (2014). Intelligent train operation algorithms based on expert knowledge and reinforcement learning. IEEE Transactions on Intelligent Transportation Systems, 14(6): 1251–1261

[19] Yin J, Chen D, Li Y (2016c). Smart train operation algorithms based on expert knowledge and ensemble CART for the electric locomotive. Knowledge-Based Systems, 92: 78–91

[20] Yin J, Chen D, Yang L, Tang T, Ran B (2016b). Efficient real-time train operation algorithms with uncertain passenger demands. IEEE Transactions on Intelligent Transportation Systems, 17(9): 2610–2622

[21] Yin J, Tang T, Yang L, Gao Z, Ran B (2016a). Energy-efficient metro train rescheduling with uncertain time-variant passenger demands: an approximated dynamic programming approach. Transportation Research Part B: Methodological, 91: 178–210

[22] Yin J, Yang L, Tang T, Gao Z, Ran B (2017). Dynamic passenger demand oriented metro trian scheduling with energy-efficiency and waiting time minimization: Mixed-integer programming approaches. Transportation Research Part B: Methodological, 97: 182–213

[23] Zhou X, Zhong M (2007). Single-track train timetabling with guaranteed optimility: Branch-and-bound algorithm with enhanced lower bounds. Transportation Research Part B: Methodological, 41(3): 320–341

RIGHTS & PERMISSIONS

The Author(s) 2017. Published by Higher Education Press. This is an open access article under the CC BY license (http://creativecommons.org/licenses/by/4.0)