This paper was converted on www.awesomepapers.org from LaTeX by an anonymous user.
Want to know more? Visit the Converter page.

Integrated optimization of train timetables rescheduling and response vehicles on a disrupted metro line

Hui Wang [email protected] Jialin Liu [email protected] Feng Li [email protected] Hao Ji jihao˙[email protected] Bin Jia [email protected] Ziyou Gao [email protected] State key laboratory of Rail Traffic Control and Safety, Beijing Jiaotong university, Beijing 100044, China Key laboratory of transport industry of big data application technologies of comprehensive transport, Beijing Jiaotong university, Beijing 100044, China School of Economics and Management, Xi’an Technological University, Xi’an 710021, China
Abstract

When an unexpected metro disruption occurs, metro managers need to reschedule timetables to avoid trains going into the disruption area, and transport passengers stranded at disruption stations as quickly as possible. This paper proposes a two-stage optimization model to jointly make decisions for two tasks. In the first stage, the timetable rescheduling problem with cancellation and short-turning strategies is formulated as a mixed integer linear programming (MILP). In particular, the instantaneous parameters and variables are used to describe the accumulation of time-varying passenger flow. In the second one, a system-optimal dynamic traffic assignment (SODTA) model is employed to dynamically schedule response vehicles, which is able to capture the dynamic traffic and congestion. Numerical cases of Beijing Metro Line 9 verify the efficiency and effectiveness of our proposed model, and results show that: (1) when occurring a disruption event during peak hours, the impact on the normal timetable is greater, and passengers in the direction with fewer train services are more affected; (2) if passengers stranded at the terminal stations of disruption area are not transported in time, they will rapidly increase at a speed of more than 300 passengers per minute; (3) compared with the fixed shortest path, using the response vehicles reduces the total travel time about 7%7\%. However, it results in increased travel time for some passengers.

keywords:
Metro disruption; Train timetable rescheduling; Response vehicle scheduling; Dynamic traffic assignment

1 Introduction

1.1 Background

Urban metro system plays an essential role in daily trips so that the operators need to make efficient, safe and reliable plans to meet the huge traveling demand. However, some unexpected disruptions occur now and again. Metro managers often use two management strategies to respond to such emergencies: one is to reschedule normal train timetables, and the other is to arrange shuttle vehicles to evacuate stranded passengers. For example, the line tracks between Serangoon station & Sengkang station in the North East Line of Singapore was disrupted because of a power fault on March 27, 2021. This disruption lasted for hours, and tens of thousands of passengers were affected. To ensure the safety of trains, the Singapore Bus Service (SBS) quickly adjusted the train timetable in North East Line, and two free bus bridging routes were also opened (sin [2021]). However, as seen from the viewpoints of Twitter, passengers are still not satisfied with the current disruption response plan. There is still much room for improving the current timetable rescheduling and bus bridging service.

Except for the power failure, unexpected disruption might be triggered by many reasons, such as the breakdown of signals, the equipment failure of line tracks, mistakes of operators, etc (Golightly & Dadashi [2017], Pender et al. [2013]).

The metro disruption period is divided into three stages (Ghaemi et al. [2018a]). As shown in Figure 1, in the first stage, the traffic capacity of the metro system drops dramatically, and the normal timetable is converted into a disrupted timetable. The metro operators analyze the disruption reason and predict the duration time. According to the estimated disruption duration time, the metro managers determine whether the bus bridging service should be activated, and what kind of rescheduling strategies should be executed. In the second stage, the traffic capacity maintain a lower steady state after using recovery strategies. In the third stage, the disrupted timetable is swifted to the normal timetables after disruption, and the traffic capacity would return to its normal level. To provide a complete response scheme, we focus on the first stage and aim at providing efficient recovery strategies. (Cacchiani et al. [2014]).

Refer to caption
Figure 1: Traffic capacity during metro disruption period

Timetable rescheduling aims to avoid the trains running into the disruption area by adjusting the normal timetable. While, response vehicles aim to bridge the disrupted metro line by adding auxiliary vehicle services, which ensures that affected passengers can still reach their destinations. To the best of our knowledge, there are no studies majoring at optimizing both the metro timetable rescheduling and bus bridging service. To increase the efficiency of recover strategies, a complete plan including metro timetable rescheduling and bus bridging service are needed. Besides,the current bus bridging service can be seen as one type of response vehicles that has fixed route and departure frequency. However, it can not capture the time-varying road conditions. Thus, considering the time-varying road conditions, response vehilces are required to adjust their route choice according to the real-time road consitions.

To address the research gap, this work focuses on two questions as follows:
1. How to coordinate the train timetable rescheduling and response vehicle scheduling into an application? Because the transport capacity of trains is much greater than vehicles, it is a challenge task to bridge the capacity gap between both traffic modes.
2. How to schedule the real-time routes of response vehicles considering real-time traffic conditions?

This paper formulates a two-stage optimiztion model. In the first stage, we compute a feasible rescheduled timetable with the objective to minimize passenger waiting time, and the train safety and passenger assignment are considered. In particular, we introduce instaneous parameters and variables to calculate the passenger accumulation at each station. The result of passenger accumulation is then transferred into the demand of response vehicles. In the second stage, the real-time routes of response vehicles are guided by the SO-DTA model (Ziliaskopoulos [2000]). The road is discretized into a serious of successive cells, traffic signals and road capacity are both considered.

1.2 Literature review

1.2.1 Literature

Metro disruption management refers to the field of conventional railway disruption management. In the early ages, disruption management is urgent in daily railway operations, because the railway infrastructures are not complete. Potential influence factors (Jespersen-Groth et al. [2009]) and fault-to-incident propagation (Yan et al. [2019]) are essential for disruption prevention in the railway lines. According to the extent of disruption, railway disruption can be into two types: partial disruption and complete disruption (Cacchiani et al. [2014]). For the partially disrupted railway line, some tracks with the same direction are disrupted. Trains of different directions have to share the same track in the partially disrupted tracks. (Louwerse & Huisman [2014], Luo et al. [2018]). However, the railway line would be divided into two separate parts if it is completely disrupteded (Veelenturf et al. [2016],Nielsen et al. [2012]). This classification is also accepted by metro disruption management. To cope with unexpected disruptions, four strategies are adopted in the metro timetable rescheduling: short-turning, skip-stopping, canceling, and speed adjustment. The short-turning strategy is to make the train circle a partial area of the railway line (Ghaemi et al. [2017],Schettini et al. [2022]). The result of Ghaemi et al. [2018a] have revealed that the optimal short-turning strategy depends on both the start time and the length of the disruption. The skip-stopping strategy is to let the train not stop at some stations, as it can avoid trains loading too many passengers. As this strategy makes tiny changes to the metro timetable, it is usually used together with other strategies (Zhu & Goverde [2020]). Canceling is to cancel some train services in the normal timetable (Zhu & Goverde [2020]). Except for the above three strategies, the normal timetable can also be rescheduled by adjusting train speed. This strategy is from a microscopic aspect, and the train running time of railway tracks would be changed. Speed adjustment is usually adopted to reduce passenger delays (Narayanaswami & Rangaraj [2013]), or to achieve real-time running control of high-speed railway trains (Xu et al. [2017]).

Most literature focus on operator-oriented timetable rescheduling. The objectives of these literature usually includes cost of rescheduling strategies (Schettini et al. [2022]), train delay (Tessitore et al. [2022], Xu et al. [2016]), or energy consumption (Bueno-Cadena et al. [2020]). Few papers focus on integrating timetable rescheduling with other topics.i.g.,Wang et al. [2021] integrates rolling stock circulation and timetable rescheduling. Bešinović et al. [2021] incorporates train timetable rescheduling and passenger flow control. These literature do not conclude the interests of passengers, which is not enough for providing high-quality services. To compensate for this shortcoming, some recent literature focus on passenger-oriented timetable rescheduling. As the disruption information is unknown, passengers have to decide whether to wait until the disruption has ended (Wang et al. [2014], Zhang & Lo [2018]) or board other transport means (Schmidt et al. [2018], Ghaemi et al. [2018b], Xu et al. [2021]). The choice of passengers depends on their general cost, their available incomes (Pnevmatikou et al. [2015]), and so on. To better fit the demand of passengers, passenger-oriented timetable rescheduling is now accepted by scholars. The objective of passenger-oriented timetable rescheduling is to minimize the passenger total traveling time (Zhu & Goverde [2020], Zhu & Goverde [2019]), or the satisfaction of passengers (Binder et al. [2017],Huang et al. [2020]). Usually, these problems are solved by decomposition algorithms (Zhan et al. [2021], Gao et al. [2016]) or intelligent algorithms (Zilko et al. [2016]). However, these literature does not consider the substitute transport, and passengers have to wait during thr overall disruption.

Owing to the blockage of disrupted metro line, some passengers can not successfully reach their destination by metro. Thus, auxiliary transport is needed to serve these passengers. In practical operations, buses have been adopted as their advantage of large capacity (sin [2021]). For example, the first train timetabling (Guo et al. [2019]. Kang et al. [2021]), last train timetabling (Kang & Meng [2017], Yang et al. [2020]), and contract design (Zhang & Lo [2020]). During peak hours, the bus bridging service can also be applied to assist passenger control on a busy metro line (Yang et al. [2017]). While facing with a long-time disruption, the operator has to desgin the bus bridging routes and their frequencies (Kepaptsoglou et al. [2009], Jin et al. [2016]). For a disrupted single metro line, most literature focus on the design of bus bridging to minimize the cost of passengers (Wang et al. [2019], Evelien van der Hurk et al. [2016]). While, for a disrupted metro network, the attention are more paid to the resilience to potential disruptions (Jin et al. [2014]), or to build a integrated rail-bus transit network (Hua & Ong [2018], Tan et al. [2020], Dou et al. [2019]).

However, there are two shortcomings of the current bus bridging research. First, most literature assumes that the auxiliary bus has fixed routes and fixed frequencies. Some researchers have also considered breaking the mindset of bus bridging services, and they have designed a more flexible bus bridging plan in response to metro disruptions (Wang et al. [2016], Gu et al. [2018]). Second, current research on the bus bridging service assumes that the road condition is constant all the time, and the bus can reach each station on time. In daily operation, this assumption is a rather strong hypothesis, as it has not considered the variation of road traffic. For example, bus bunching is a common phenomenon in our daily life, which will lead to an unstable bus delay on the congested road (Daganzo [2009], Daganzo & Pilachowski [2011], Delgado et al. [2012], Petit et al. [2018]). Therefore, to better fit the practical operational demand, the real-time road traffic information should be concluded in our reponse schemes.

To capture the real traffic dynamics, the DTA technologies (Peeta & Ziliaskopoulos [2001], Szeto & Lo [2006]) are considered in our research. Usually, it can be classified into two types: simulation-based approaches (Sbayti et al. [2007],Levin et al. [2015], Shafiei et al. [2018]) and analytical approaches (Carey & Watling [2012], Ke et al. [2013]). The simulation-based models often suffer from a huge computational burden, and the analytical approach also has such a deficiency because the models are often written as path-based formulations. Moreover, the analytical approach has the problem of poor convergence in large-scale networks (Jiang et al. [2016]). Fortunately, a linear programming (LP) framework for system optimal DTA (SO-DTA) problem (Ziliaskopoulos [2000]) was proposed, in which the cell transmission model (CTM) (Daganzo [1994], Daganzo [1995]) is employed to load traffic flow. This framework is widely used in large-scale emergency traffic planning and organization due to its lower computational burden. (Chiu et al. [2007], Yao et al. [2009], Xie et al. [2010], Ben-Tal et al. [2011], Kimms & Maiwald [2018], He & Peeta [2014], Liu et al. [2021] ). These literature has provided the foundation for the design of response vehicles on the road.

1.2.2 Our focus

As mentioned above, most literature focuses on either train timetable rescheduling or bus bridging service. As far as the author knows, there is no literature integrating the metro timetable rescheduling and bus bridging service. Just like Zhu & Goverde [2020], the metro timetabling rescheduling does not take the substitute transport take into account, they assume that the passengers can wait until the disruption has ended. While in the design of the bus bridging service, the metro timetable is assumed to be fixed (see Jin et al. [2016], etc.). Thus, in this paper, we aim to integrate both the metro timetable rescheduling and response vehicle scheduling.

Besides, the modeling method of timetable rescheduling can be extended to deal with different problems. Zhu & Goverde [2020] has proposed an improved Dynamic Altenative Graph (DAG) formulation to reschedule the train timetable, and the passenger assignment procedure is to assign passengers to the alternative graph. Huang et al. [2020] use big-M and time-indexed formulations to reschedule the metro timetable, and the pasenger accumulation is measured by trains. However, these two important literature can not capture the time-varying accumulation of passengers, and this is required in design of response vehicles. To observe the real-time passenger accumulation in a station, we have introduced instaneous parameters and variables to record the passenger trajectory. Although there are four general reshceduling strategies, the short-turning and canceling strategy are efficient in response to unexpected disruption (Zhu & Goverde [2020]). To simplify the operation of metro operators, our paper only includes these two main strategies.

Refer to caption
Figure 2: Double-line metro under disruption scenario

In the field of metro disruption management, DTA is a new technique in response to the disruption. Compared with traditional optimization method (i.g., Kepaptsoglou et al. [2009], Jin et al. [2016]), the biggest advantage of DTA is that it can capture real-time information of vehicles on the road.

Therefore, this paper contributes to the literature through three aspects:

\bulletA new two-stage optimization model is built to coordinate the metro timetable rescheduling and response vehicle scheduling. In particular, the passenger accumulation is measured by our proposed model, which provides a new approach to passenger-oriented timetabling compared with current research.

\bulletMost literature take bus bridging service as a substitute for trains, we explore to provide more flexible service by scheduling response vehicles. This provides a new perspective to the response of metro disruption.

\bulletThe application of SO-DTA can capture the real-time road traffic, which is closer to reality compared with current metro disruption research.

The remainder of this paper is organized as follows. In section 2, the problem statements of our research are described. Section 3 presents a MILP model to reschedule the metro timetable. Furthermore, the real-time routes of response vehicles are optimized based on the SO-DTA model in section 4. Numerical cases of Beijing Metro Line 9 are conducted in section 5. Finally, the conclusions and possible topics for future research have been presented in section 6.

Refer to caption
Figure 3: Overview of two-stage optimization model

2 Problem description

We investigate the problem of metro timetable rescheduling and response vehicle scheduling on a disrupted double-line metro in this research. A double-line metro is made up of two separate lines that run in opposite directions. Figure 2 (a) shows that we use the set \mathbb{R} to denote all of the stations in the normal metro line, and the line track is described as a tuple (r, r+1) or (r, r-1). Note that the tuple (r, r+1) denotes the line track in the positive direction, while (r, r-1) denotes the line track in the negative direction. Trains circulate between the normal metro line’s terminal stations (Station 1 and Station |||\mathbb{R}|). However, due to an unexpected disruption, the metro line would be divided into two parts. These two parts are called as MS-1 and MS-2, and they are referred to as operational areas because trains can operate in them. As shown in Figure 2, an unexpected disruption occurred between stations r1 and r2. The operational area is denoted by O={1,,r1,r2,||}\mathbb{R}_{\rm{O}}=\{1,...,\rm{r1},\rm{r2}...,|\mathbb{R}|\}. MS-1 denotes the stations from Station 1 to r1, while MS-2 denotes the stations from Station 2 to |||\mathbb{R}|. Furthermore, we refer to the area between Stations r1 and r2 as the disruption area because trains cannot pass through it during a disruption scenario. As a result, trains will be rescheduled in the operational area while response vehicles will be scheduled in the disruption area in this paper.

In comparison to previous studies on metro disruption, we incorporate metro timetable rescheduling and response vehicle scheduling. The modeling methodologies for metro timetable rescheduling and response vehicle scheduling, however, differ. For the metro timetable rescheduling, train services in the normal timetable are rescheduled to avoid conflicts with spatio-temporal disruption area (definitions see as B). Passengers are assigned to available trains in the operational area; For the response vehicle scheduling, real-time routes of response vehicles are modeled using the method of dynamic traffic assignment, and vehicles are loaded into the road network in the disruption area. How can we bridge the gap between metro trains and response vehicles given the topological differences between metro lines and road networks?

To include both the metro timetable rescheduling and response vehicle scheduling in a unified optimization structure, we built a two-stage optimization model that first reschedules the normal metro timetable and then optimizes the real-time routes of response vehicles. An overview of the two-stage optimization model is shown in Figure 3.

Given the disruption information on a railway line and the passenger demand, we obtain a passenger-oriented rescheduled timetable in the first stage. In the first stage, the metro timetable rescheduling problem is described as a MILP, with the goal of minimizing total passenger waiting time. We consider three constraint modules in this stage: 1) timetable rescheduling. The timetable rescheduling aims to reschedule the normal timetable by using two strategies: cancellation and turnaround. Besides, the train’s safety in the new timetable is also ensured by the headway constraints. 2) passenger assignment. Passengers are restricted to be assigned to available train services. 3) measurement of passenger accumulation. The instantaneous parameters and variables are introduced to describe the time-varying passenger accumulation; In the second stage, the response vehicle scheduling problem is described as a LP, with the goal of minimizing the systematic total travel time of response vehicles. Before the scheduling of response vehicles, the real-time passenger demands are transferred into the demands of response vehicles by the procedure of passenger mapping. The constraints are referred to Ziliaskopoulos [2000]. We finally obtain an optimally rescheduled metro timetable, real-time routes of response vehicles, and passengers are transported to their destinations or transfer stations that can reach their destination through the two steps of optimizing models M1 and M2.

In order to ensure the rigorism of our focused problem, some necessary assumptions should be declared before the proposition of our model:

(1) The duration of disruption can be predicted. Much of the metro disruption literature accepts this assumption (Wang et al. [2021],Zhang & Lo [2018],Huang et al. [2020]). Once the disruption has occurred, the metro operators should analyze the cause of the disruption and estimate the duration of the disruption. Response strategies are based on the estimated disruption period for practical operations.

(2) The metro stations (except for the terminal stations in the disruption area) in the disruption area are closed during the disruption period. This assumption refers to the practical disruption case of Singapore on March 27, 2021. As the trains can not go through the disruption area, and the passengers can not board trains in this area. Thus, for the sake of recovery work on metro line tracks, these stations are closed.

(3) The terminal stations in the disruption area can provide trains with turnaround operations. To ensure the safe driving of trains, the train would turn around at the nearest turn-back station from disrupted terminal stations. Although some tracks are not broken down, they are also regarded as disrupted tracks because trains can not run across them.

(4) The response vehicles are sufficient. As the response vehicles can be deployed from nearby car or bus depots, we assume that sufficient vehicles can be deployed swiftly from these depots. This assumption has ensured that all the passenger demand in the disruption area can be boarded by the response vehicles.

(5) The response vehicles have the same holding capacity. This assumption was made to simplify the mathematical model, and the response vehicles are divided into several fleets.

(6) Special lanes are planned for the response vehicles. For each road, there are two special lanes with different directions planned for the response vehicles.

3 Stage 1: timetable rescheduling

In this section, we develop a MILP model for passenger-oriented timetabling with the objective of minimizing total passenger waiting time. The MILP model is made up of three constraint modules: 1) timetable rescheduling, 2) passenger assignment, and 3) passenger accumulation measurement. The following is our mathematical model:

3.1 Objective function

The objective is to minimize the total waiting time of passengers, as well as to penalize the unassigned passengers, which is

minZ1=pu𝕌𝕌~(w˘puxpu+Mxp)\min Z_{1}=\sum_{{\rm{p}\in\mathbb{P}}}\sum\limits_{{\rm{u}}\in\mathbb{U}\cup\mathbb{\tilde{U}}}\left(\begin{matrix}\breve{{\rm{w}}}_{{\rm{p}}}^{{\rm{u}}}x_{{\rm{p}}}^{{\rm{u}}}+{\rm{M}}x_{{\rm{p}}}\end{matrix}\right)\qquad\qquad (1)

where the parameter w˘pu\breve{{\rm{w}}}_{{\rm{p}}}^{{\rm{u}}} denotes the waiting time if passenger flow p takes the train service u.i,.e., w˘pu=t^u,o^pat^p\breve{{\rm{w}}}_{{\rm{p}}}^{{\rm{u}}}={\rm{\hat{t}}}_{{\rm{u,{\rm{\hat{o}_{p}}}}}}^{a}-{\rm{\hat{t}_{p}}}. The first term of objective function measures the total waiting time of passenger flows, which ensures the total waiting time of passengers can be minimized. While the last term penalizes the failure boarding of passengers, which ensures the passengers are assigned to trains as many as possible.
Remark 1. The big-M parameter in the objective function Z1Z_{1} should satisfy: M maxp,u𝕌𝕌~{w˘pu}\geq\max\limits_{{\rm{p}\in\mathbb{P}},{\rm{u}}\in\mathbb{U}\cup\mathbb{\tilde{U}}}\{\breve{{\rm{w}}}_{{\rm{p}}}^{{\rm{u}}}\}; otherwise, the passenger might not be assigned completely.
Proof. see as E.1.

3.2 Constraints

In the following, the constraints for train service activation, station identification, train headway, passenger assignment, train capacity, an passenger accumulation are introduced successively.

3.2.1 Activation of normal train services

The metro timetable includes the train route as well as station arrival and departure times. The normal timetable is generated using daily passenger demand data. However, if an unexpected disruption occurs on the metro line, the normal timetable should be adjusted to ensure train safety. That is, in the disruption scenario, the train should not pass through the spatio-temporal disruption area and should turn around at the disruption area’s terminal station. If the train service in the normal timetable conflicts with the spatio-temporal disruption area, the train trajectory should be revised. The following constraints depict the activation of normal train services:

s.t.(tu,ratu,rd)(tu,ratu,rd)M(1au+Θu),u𝕌𝕌~,r,s.t.\left(\begin{matrix}t_{{\rm{u,r}}}^{a}\\ t_{{\rm{u,r}}}^{d}\end{matrix}\right)\geq\left(\begin{matrix}{\rm{t}}_{{\rm{u,r}}}^{a}\\ {\rm{t}}_{{\rm{u,r}}}^{d}\end{matrix}\right)-{\rm{M}}(1-a_{{\rm{u}}}+\Theta_{{\rm{u}}}),\forall{\rm{u}\in\mathbb{U}}\cup\mathbb{\tilde{U}},{\rm{r}\in\mathbb{R}},\qquad\qquad (2a)
(tu,ratu,rd)(tu,ratu,rd)+M(1au+Θu),u𝕌𝕌~,r,\quad\ \left(\begin{matrix}t_{{\rm{u,r}}}^{a}\\ t_{{\rm{u,r}}}^{d}\end{matrix}\right)\leq\left(\begin{matrix}{\rm{t}}_{{\rm{u,r}}}^{a}\\ {\rm{t}}_{{\rm{u,r}}}^{d}\end{matrix}\right)+{\rm{M}}(1-a_{{\rm{u}}}+\Theta_{{\rm{u}}}),\forall{\rm{u}\in\mathbb{U}}\cup\mathbb{\tilde{U}},{\rm{r}\in\mathbb{R}},\qquad\qquad (2b)
(tu,ratu,rd)(tu,ratu,rd)+M(au+Θu+fu3),u𝕌,rO1T1,\quad\qquad\quad\left(\begin{matrix}t_{{\rm{u,r}}}^{a}\\ t_{{\rm{u,r}}}^{d}\end{matrix}\right)\geq\left(\begin{matrix}{\rm{t}}_{{\rm{u,r}}}^{a}\\ {\rm{t}}_{{\rm{u,r}}}^{d}\end{matrix}\right)+{\rm{M}}(a_{{\rm{u}}}+\Theta_{{\rm{u}}}+{\rm{f}}_{{\rm{u}}}-3),\forall{\rm{u}\in\mathbb{U}},{\rm{r}\in\mathbb{R}_{O}^{1}}\setminus\mathbb{R}_{\rm{T}}^{1},\qquad\qquad (3a)
(tu,ratu,rd)(tu,ratu,rd)+M(3au+Θufu),u𝕌,rO1T1,\qquad\qquad\ \left(\begin{matrix}t_{{\rm{u,r}}}^{a}\\ t_{{\rm{u,r}}}^{d}\end{matrix}\right)\leq\left(\begin{matrix}{\rm{t}}_{{\rm{u,r}}}^{a}\\ {\rm{t}}_{{\rm{u,r}}}^{d}\end{matrix}\right)+{\rm{M}}(3-a_{{\rm{u}}}+\Theta_{{\rm{u}}}-{\rm{f}}_{{\rm{u}}}),\forall{\rm{u}\in\mathbb{U}},{\rm{r}\in\mathbb{R}_{O}^{1}}\setminus\mathbb{R}_{\rm{T}}^{1},\qquad\qquad (3b)
(tu,ratu,rd)(tu,ra1)+M(Θu+fu+au3),u𝕌,rT1,\qquad\ \left(\begin{matrix}t_{{\rm{u,r}}}^{a}\\ t_{{\rm{u,r}}}^{d}\end{matrix}\right)\geq\left(\begin{matrix}{\rm{t}}_{{\rm{u,r}}}^{a}\\ -1\end{matrix}\right)+{\rm{M}}(\Theta_{{\rm{u}}}+{\rm{f}}_{{\rm{u}}}+a_{{\rm{u}}}-3),\forall{\rm{u}\in\mathbb{U}},{\rm{r}\in\mathbb{R}_{\rm{T}}^{1}},\qquad\qquad (4a)
(tu,ratu,rd)(tu,ra1)+M(3Θufuau),u𝕌,rT1,\qquad\ \left(\begin{matrix}t_{{\rm{u,r}}}^{a}\\ t_{{\rm{u,r}}}^{d}\end{matrix}\right)\leq\left(\begin{matrix}{\rm{t}}_{{\rm{u,r}}}^{a}\\ -1\end{matrix}\right)+{\rm{M}}(3-\Theta_{{\rm{u}}}-{\rm{f}}_{{\rm{u}}}-a_{{\rm{u}}}),\forall{\rm{u}\in\mathbb{U}},{\rm{r}\in\mathbb{R}_{\rm{T}}^{1}},\qquad\qquad (4b)
(tu,ratu,rd)1+M(au+Θu+fu3),u𝕌,rO1,\qquad\quad\left(\begin{matrix}t_{{\rm{u,r}}}^{a}\\ t_{{\rm{u,r}}}^{d}\end{matrix}\right)\geq-1+{\rm{M}}(a_{{\rm{u}}}+\Theta_{{\rm{u}}}+{\rm{f}}_{{\rm{u}}}-3),\forall{\rm{u}\in\mathbb{U}},{\rm{r}\in\mathbb{R}\setminus\mathbb{R}_{\rm{O}}^{1}},\qquad\qquad (5a)
(tu,ratu,rd)1+M(3auΘufu),u𝕌,rO1,\qquad\quad\left(\begin{matrix}t_{{\rm{u,r}}}^{a}\\ t_{{\rm{u,r}}}^{d}\end{matrix}\right)\leq-1+{\rm{M}}(3-a_{{\rm{u}}}-\Theta_{{\rm{u}}}-{\rm{f}}_{{\rm{u}}}),\forall{\rm{u}\in\mathbb{U}},{\rm{r}\in\mathbb{R}\setminus\mathbb{R}_{\rm{O}}^{1}},\qquad\qquad (5b)
(tu,ratu,rd)(tu,ratu,rd)M(2Θuau+fu),u𝕌,rO2T2,\qquad\qquad\left(\begin{matrix}t_{{\rm{u,r}}}^{a}\\ t_{{\rm{u,r}}}^{d}\end{matrix}\right)\geq\left(\begin{matrix}{\rm{t}}_{{\rm{u,r}}}^{a}\\ {\rm{t}}_{{\rm{u,r}}}^{d}\end{matrix}\right)-{\rm{M}}(2-\Theta_{{\rm{u}}}-a_{{\rm{u}}}+{\rm{f}}_{{\rm{u}}}),\forall{\rm{u}\in\mathbb{U}},{\rm{r}\in\mathbb{R}_{O}^{2}}\setminus\mathbb{R}_{\rm{T}}^{2},\qquad\qquad (6a)
(tu,ratu,rd)(tu,ratu,rd)+M(2Θuau+fu),u𝕌,rO2T2,\qquad\qquad\left(\begin{matrix}t_{{\rm{u,r}}}^{a}\\ t_{{\rm{u,r}}}^{d}\end{matrix}\right)\leq\left(\begin{matrix}{\rm{t}}_{{\rm{u,r}}}^{a}\\ {\rm{t}}_{{\rm{u,r}}}^{d}\end{matrix}\right)+{\rm{M}}(2-\Theta_{{\rm{u}}}-a_{{\rm{u}}}+{\rm{f}}_{{\rm{u}}}),\forall{\rm{u}\in\mathbb{U}},{\rm{r}\in\mathbb{R}_{O}^{2}}\setminus\mathbb{R}_{\rm{T}}^{2},\qquad\qquad (6b)
(tu,ratu,rd)(tu,ra1)M(2auΘu+fu),u𝕌,rT2,\quad\ \left(\begin{matrix}t_{{\rm{u,r}}}^{a}\\ t_{{\rm{u,r}}}^{d}\end{matrix}\right)\geq\left(\begin{matrix}{\rm{t}}_{{\rm{u,r}}}^{a}\\ -1\end{matrix}\right)-{\rm{M}}(2-a_{{\rm{u}}}-\Theta_{{\rm{u}}}+{\rm{f}}_{{\rm{u}}}),\forall{\rm{u}\in\mathbb{U}},{\rm{r}\in\mathbb{R}_{\rm{T}}^{2}},\qquad\quad (7a)
(tu,ratu,rd)(tu,ra1)+M(2auΘu+fu),u𝕌,rT2,\quad\ \left(\begin{matrix}t_{{\rm{u,r}}}^{a}\\ t_{{\rm{u,r}}}^{d}\end{matrix}\right)\leq\left(\begin{matrix}{\rm{t}}_{{\rm{u,r}}}^{a}\\ -1\end{matrix}\right)+{\rm{M}}(2-a_{{\rm{u}}}-\Theta_{{\rm{u}}}+{\rm{f}}_{{\rm{u}}}),\forall{\rm{u}\in\mathbb{U}},{\rm{r}\in\mathbb{R}_{\rm{T}}^{2}},\qquad\quad (7b)
(tu,ratu,rd)1M(2auΘu+fu),u𝕌,rO2,\quad\ \left(\begin{matrix}t_{{\rm{u,r}}}^{a}\\ t_{{\rm{u,r}}}^{d}\end{matrix}\right)\geq-1-{\rm{M}}(2-a_{{\rm{u}}}-\Theta_{{\rm{u}}}+{\rm{f}}_{{\rm{u}}}),\forall{\rm{u}\in\mathbb{U}},{\rm{r}\in\mathbb{R}\setminus\mathbb{R}_{\rm{O}}^{2}},\qquad (8a)
(tu,ratu,rd)1+M(2auΘu+fu),u𝕌,rO2,\quad\ \left(\begin{matrix}t_{{\rm{u,r}}}^{a}\\ t_{{\rm{u,r}}}^{d}\end{matrix}\right)\leq-1+{\rm{M}}(2-a_{{\rm{u}}}-\Theta_{{\rm{u}}}+{\rm{f}}_{{\rm{u}}}),\forall{\rm{u}\in\mathbb{U}},{\rm{r}\in\mathbb{R}\setminus\mathbb{R}_{\rm{O}}^{2}},\qquad (8b)
(tu,ratu,rd)1Mau,u𝕌,r,\left(\begin{matrix}t_{{\rm{u,r}}}^{a}\\ t_{{\rm{u,r}}}^{d}\end{matrix}\right)\geq-1-{\rm{M}}a_{{\rm{u}}},\forall{\rm{u}\in\mathbb{U}},{\rm{r}\in\mathbb{R}},\qquad\qquad\qquad\qquad\quad (9a)
(tu,ratu,rd)1+Mau,u𝕌,r,\left(\begin{matrix}t_{{\rm{u,r}}}^{a}\\ t_{{\rm{u,r}}}^{d}\end{matrix}\right)\leq-1+{\rm{M}}a_{{\rm{u}}},\forall{\rm{u}\in\mathbb{U}},{\rm{r}\in\mathbb{R}},\qquad\qquad\qquad\qquad\quad (9b)
au1Θu,u𝕌,a_{{\rm{u}}}\geq 1-\Theta_{{\rm{u}}},\forall{\rm{u}\in\mathbb{U}},\qquad\qquad\qquad\qquad\qquad\qquad\qquad (10)

where binary parameter Θu\Theta_{{\rm{u}}} with value 1 indicating that train service u 𝕌\in\mathbb{U} conflicts with the spatio-temporal disruption area, and 0 otherwise. Constraint (2a)-(2b) means that the rescheduled arrival/departure times of a train service remain unchanged if it is activated, and does not conflict with the spatio-temporal disruption area. Constraint (3a)-(3b) mean that the arrival/departure time of an activated positive train service u 𝕌\in\mathbb{U} at station rO1T1{\rm{r}\in\mathbb{R}_{O}^{1}}\setminus\mathbb{R}_{\rm{T}}^{1} remains unchangesd if it conflicts with spatio-temporal disruption area. Constraint (4a) means that the arrival times of an actived positive train service u 𝕌\in\mathbb{U} at terminal station rT1{\rm{r}\in\mathbb{R}_{\rm{T}}^{1}} remain unchanged if it conflicts with the spatio-temporal disruption area. Constraint (4b) means that the departure time of an activated positive train service u 𝕌\in\mathbb{U} at terminal station rT1{\rm{r}\in\mathbb{R}_{T}^{1}} equals -1 if it conflicts with the spatio-temporal disruption area. Constraint (5a)-(5b) mean that the arrival/departure time of an activated positive train service u 𝕌\in\mathbb{U} at station rO1{\rm{r}\in\mathbb{R}\setminus\mathbb{R}_{\rm{O}}^{1}} equals -1 if it conflicts with the spatio-temporal disruption area.

For an activated negative train service, constraints (6a)-(6b) mean that the arrival/departure time of an activated train service u 𝕌\in\mathbb{U} at station rO2T2{\rm{r}\in\mathbb{R}_{O}^{2}}\setminus\mathbb{R}_{\rm{T}}^{2} remains unchanged if it conflicts with the spatio-temporal disruption area. Constraint (7a) means that the arrival time of an actived positive train service u 𝕌\in\mathbb{U} at terminal station rT2{\rm{r}\in\mathbb{R}_{\rm{T}}^{2}} remains unchanged if it conflicts with the spatio-temporal disruption area. Constraint (7b) mean that the departure time of an activated positive train service u 𝕌\in\mathbb{U} at terminal station rT2{\rm{r}\in\mathbb{R}_{T}^{2}} equals -1 if it conflicts with the spatio-temporal disruption area. Constraints (8a)-(8b) mean that the arrival/departure time of an activated negative train service u 𝕌\in\mathbb{U} at station rO2{\rm{r}\in\mathbb{R}\setminus\mathbb{R}_{\rm{O}}^{2}} equals -1 if it conflicts with the spatio-temporal disruption area. Note that, the arrival/departure time of a train service equals -1 if it is not activated (constraints (9a)-(9b)). Constraint (10) means that train service u 𝕌\in\mathbb{U} should be activated if it does not conflict with the spatio-temporal disruption area.

3.2.2 Activation of turnaround train services

Recall that turnaround train services are saved in the set 𝕌~\mathbb{\tilde{U}} and are activated by an activated normal train service if they conflict with the spatio-temporal disruption area. The following constraints depict the activation of turnaround train services:

av1+(au+Θu+fu+δu,vr4),u𝕌,v𝕌~,rT1,\quad\ a_{{\rm{v}}}\geq 1+(a_{{\rm{u}}}+\Theta_{{\rm{u}}}+{\rm{f}}_{{\rm{u}}}+\delta_{{\rm{u,v}}}^{{\rm{r}}}-4),\forall{\rm{u}\in\mathbb{U}},{\rm{v}\in\mathbb{\tilde{U}}},{\rm{r}\in\mathbb{R}_{T}^{1}}, (11a)
av1+(au+Θufu+δu,vr3),u𝕌,v𝕌~,rT2,\quad\ a_{{\rm{v}}}\geq 1+(a_{{\rm{u}}}+\Theta_{{\rm{u}}}-{\rm{f}}_{{\rm{u}}}+\delta_{{\rm{u,v}}}^{{\rm{r}}}-3),\forall{\rm{u}\in\mathbb{U}},{\rm{v}\in\mathbb{\tilde{U}}},{\rm{r}\in\mathbb{R}_{T}^{2}}, (11b)
(tu,ratu,rd)(tu,ratu,rd)M(1au),u𝕌~,r,\quad\ \left(\begin{matrix}t_{{\rm{u,r}}}^{a}\\ t_{{\rm{u,r}}}^{d}\end{matrix}\right)\geq\left(\begin{matrix}{\rm{t}}_{{\rm{u,r}}}^{a}\\ {\rm{t}}_{{\rm{u,r}}}^{d}\end{matrix}\right)-{\rm{M}}(1-a_{{\rm{u}}}),\forall{\rm{u}\in\mathbb{\tilde{U}}},{\rm{r}\in\mathbb{R}},\qquad\qquad\qquad\quad (12a)
(tu,ratu,rd)(tu,ratu,rd)+M(1au),u𝕌~,r,\quad\ \left(\begin{matrix}t_{{\rm{u,r}}}^{a}\\ t_{{\rm{u,r}}}^{d}\end{matrix}\right)\leq\left(\begin{matrix}{\rm{t}}_{{\rm{u,r}}}^{a}\\ {\rm{t}}_{{\rm{u,r}}}^{d}\end{matrix}\right)+{\rm{M}}(1-a_{{\rm{u}}}),\forall{\rm{u}\in\mathbb{\tilde{U}}},{\rm{r}\in\mathbb{R}},\qquad\qquad\qquad\quad (12b)
(tu,ratu,rd)1Mau,u𝕌~,r,\quad\ \left(\begin{matrix}t_{{\rm{u,r}}}^{a}\\ t_{{\rm{u,r}}}^{d}\end{matrix}\right)\geq-1-{\rm{M}}a_{{\rm{u}}},\forall{\rm{u}\in\mathbb{\tilde{U}}},{\rm{r}\in\mathbb{R}},\qquad\qquad\qquad\qquad\qquad (13a)
(tu,ratu,rd)1+Mau,u𝕌~,r,\quad\ \left(\begin{matrix}t_{{\rm{u,r}}}^{a}\\ t_{{\rm{u,r}}}^{d}\end{matrix}\right)\leq-1+{\rm{M}}a_{{\rm{u}}},\forall{\rm{u}\in\mathbb{\tilde{U}}},{\rm{r}\in\mathbb{R}},\qquad\qquad\qquad\qquad\qquad (13b)
u1𝕌rδu1,vrav(auΘu),u𝕌,v𝕌~,r,\quad\ \sum_{{\rm{u1}\in\mathbb{U}}}\sum_{{\rm{r}\in\mathbb{R}}}\delta_{{\rm{u1,v}}}^{{\rm{r}}}a_{{\rm{v}}}\leq\left(\begin{matrix}a_{{\rm{u}}}\\ \Theta_{{\rm{u}}}\end{matrix}\right),\forall{\rm{u}\in\mathbb{U}},{\rm{v}\in\mathbb{\tilde{U}}},{\rm{r}\in\mathbb{R}},\qquad\qquad\quad (14)

where binary parameter δu,vr\delta_{{\rm{u,v}}}^{{\rm{r}}} with value 1 indicating that train service v𝕌~{\rm{v}\in\mathbb{\tilde{U}}} is activated by the turnaround operations of train service u𝕌{\rm{u}\in\mathbb{U}}, and 0 otherwise. Constraints (11a)-(11b) mean that an activated normal train service u𝕌{\rm{u}\in\mathbb{U}} turns around if it conflicts with the spatio-temporal disruption area, and then its turnaround train service v𝕌~{\rm{v}\in\mathbb{\tilde{U}}} is activated. Constraints (12a)-(12b) mean that the arrival/departure times of an activated train service v𝕌~{\rm{v}\in\mathbb{\tilde{U}}} at station r{\rm{r}\in\mathbb{R}} remain unchanged if it is activated. On the contrary, constraints (13a)-(13b)) mean that the arrival/departure times of an activated train service v𝕌~{\rm{v}\in\mathbb{\tilde{U}}} at station r{\rm{r}\in\mathbb{R}} euqal -1 if it is not activated. Remark that the station arrival/departure time of train service v𝕌~{\rm{v}\in\mathbb{\tilde{U}}} is calculated in advance, which is an input to our model. Constraint (14) means that a train service u𝕌{\rm{u}\in\mathbb{U}} does not turn around if it is not activated, and also a train service u𝕌{\rm{u}\in\mathbb{U}} does not turn around if it does not conflict with the spatio-temporal area. The turnaround train service v𝕌~{\rm{v}\in\mathbb{\tilde{U}}} of a train service u𝕌{\rm{u}\in\mathbb{U}} would not be activated in both two mentioned conditions.

3.3 Identification of visited stations

Station identification refers to the stations visited by a train service. We use binary variable su,rs_{{\rm{u,r}}} to denote whethere train service u visit station r. It is determined by

su,rauΘu,u𝕌,r,s_{{\rm{u,r}}}\geq a_{{\rm{u}}}-\Theta_{{\rm{u}}},\forall{\rm{u}\in\mathbb{U}},{\rm{r}\in\mathbb{R}},\qquad\qquad\qquad\qquad\qquad\ (15a)
su,rau,u𝕌𝕌~,r,s_{{\rm{u,r}}}\leq a_{{\rm{u}}},\forall{\rm{u}\in\mathbb{U}}\cup\mathbb{\tilde{U}},{\rm{r}\in\mathbb{R}},\qquad\qquad\qquad\qquad\qquad\ (15b)
su,r1+(au+Θu+fu3),u𝕌,rO1,s_{{\rm{u,r}}}\geq 1+(a_{{\rm{u}}}+\Theta_{{\rm{u}}}+{\rm{f}}_{{\rm{u}}}-3),\forall{\rm{u}\in\mathbb{U}},{\rm{r}\in\mathbb{R}_{\rm{O}}^{1}},\qquad\qquad (16a)
su,r(3auΘufu),u𝕌,rO1,s_{{\rm{u,r}}}\leq(3-a_{{\rm{u}}}-\Theta_{{\rm{u}}}-{\rm{f}}_{{\rm{u}}}),\forall{\rm{u}\in\mathbb{U}},{\rm{r}\in\mathbb{R}\setminus\mathbb{R}_{\rm{O}}^{1}},\qquad\qquad (16b)
su,r1+(au+Θufu2),u𝕌,rO2,\quad\ s_{{\rm{u,r}}}\geq 1+(a_{{\rm{u}}}+\Theta_{{\rm{u}}}-{\rm{f}}_{{\rm{u}}}-2),\forall{\rm{u}\in\mathbb{U}},{\rm{r}\in\mathbb{R}_{\rm{O}}^{2}},\qquad\qquad\quad (17a)
su,r(2auΘu+fu),u𝕌,rO2,\quad\ s_{{\rm{u,r}}}\leq(2-a_{{\rm{u}}}-\Theta_{{\rm{u}}}+{\rm{f}}_{{\rm{u}}}),\forall{\rm{u}\in\mathbb{U}},{\rm{r}\in\mathbb{R}\setminus\mathbb{R}_{\rm{O}}^{2}},\qquad\qquad\quad (17b)
sv,r+1+(av+u𝕌δu,vr+fv3),v𝕌~,r+{r,,||},r,\qquad\qquad s_{{\rm{v,r^{+}}}}\geq 1+(a_{{\rm{v}}}+\sum_{{\rm{u}\in\mathbb{U}}}\delta_{{\rm{u,v}}}^{{\rm{r}}}+{\rm{f}}_{{\rm{v}}}-3),\forall{\rm{v}\in\mathbb{\tilde{U}}},{\rm{r^{+}}\in\{r,...,|\mathbb{R}|\}},{\rm{r}\in\mathbb{R}}, (18a)
sv,r+(3avu𝕌δu,vrfv),v𝕌~,r+{1,,r1},r,\qquad\quad s_{{\rm{v,r^{+}}}}\leq(3-a_{{\rm{v}}}-\sum_{{\rm{u}\in\mathbb{U}}}\delta_{{\rm{u,v}}}^{{\rm{r}}}-{\rm{f}}_{{\rm{v}}}),\forall{\rm{v}\in\mathbb{\tilde{U}}},{\rm{r^{+}}\in\{1,...,r-1\}},{\rm{r}\in\mathbb{R}}, (18b)
sv,r1+(av+u𝕌δu,vrfv2),v𝕌~,r{1,,r},r,\quad\qquad\ s_{{\rm{v,r^{-}}}}\geq 1+(a_{{\rm{v}}}+\sum_{{\rm{u}\in\mathbb{U}}}\delta_{{\rm{u,v}}}^{{\rm{r}}}-{\rm{f}}_{{\rm{v}}}-2),\forall{\rm{v}\in\mathbb{\tilde{U}}},{\rm{r^{-}}\in\{1,...,r\}},{\rm{r}\in\mathbb{R}}, (19a)
sv,r(2avu𝕌δu,vr+fv),v𝕌~,r{r+1,,||},r.\quad\qquad\ s_{{\rm{v,r^{-}}}}\leq(2-a_{{\rm{v}}}-\sum_{{\rm{u}\in\mathbb{U}}}\delta_{{\rm{u,v}}}^{{\rm{r}}}+{\rm{f}}_{{\rm{v}}}),\forall{\rm{v}\in\mathbb{\tilde{U}}},{\rm{r^{-}}\in\{r+1,...,|\mathbb{R}|\}},{\rm{r}\in\mathbb{R}}. (19b)

Constraint (15a) means that all the stations are visited by an activated train service u𝕌{\rm{u}\in\mathbb{U}} if it does not conflict with the spatio-temporal disruption area, and constraint (15b) means that all the stations are not visited by a train service u𝕌{\rm{u}\in\mathbb{U}} if it is not activated. Constraint (16a) means that all the stations in MS-1 are visited by an activated positive train service u𝕌{\rm{u}\in\mathbb{U}} if it conflicts with the spatio-temporal disruption area, and constraint (16b) means that an activated positive train service u𝕌{\rm{u}\in\mathbb{U}} would not visit station rO1{\rm{r}\in\mathbb{R}\setminus\mathbb{R}_{\rm{O}}^{1}} if it conflicts with the spatio-temporal disruption area. Constraint (17a) means that that all the stations in MS-2 are visited by an activated negative train service u𝕌{\rm{u}\in\mathbb{U}} if train service u conflicts with the spatio-temporal disruption area, and constraint (17b) means that an activated positive train service u𝕌{\rm{u}\in\mathbb{U}} would not visit station rO2{\rm{r}\in\mathbb{R}\setminus\mathbb{R}_{\rm{O}}^{2}} if it conflicts with the spatio-temporal disruption area.

For an activated positive turnaround train service, constraint (18a) means that the train service v𝕌~{\rm{v}\in\mathbb{\tilde{U}}} visits station r+{r,,||}{\rm{r^{+}}\in\{r,...,|\mathbb{R}|\}} if it is activated at station r\in\mathbb{R}, and constraint (18b) means that the train service v𝕌~{\rm{v}\in\mathbb{\tilde{U}}} does not visit station r+{1,,r1}{\rm{r^{+}}\in\{1,...,r-1\}} if it is activated at station r\in\mathbb{R}. Similarly, for an activated negative train service, constraint (19a) means that the train service v𝕌~{\rm{v}\in\mathbb{\tilde{U}}} visits station r{1,,r}{\rm{r^{-}}\in\{1,...,r\}} if it is activated at station r\in\mathbb{R}, and constraint (19b) means that the train service v𝕌~{\rm{v}\in\mathbb{\tilde{U}}} does not visit station r{r+1,,||}{\rm{r^{-}}\in\{r+1,...,|\mathbb{R}|\}} if it is activated at station r\in\mathbb{R}.

3.4 Headway constraints

Headway constraints are considered in metro timetabling to ensure the safety distance between two successive trains. Train headway is typically classified into four types: arrival-arrival (AA), arrival-departure (AD), departure-arrival (DA), and departure-departure (DD). The headway constraints can be illustrated as follows:

su,r+sv,r2θu,vr,u𝕌,v𝕌~,r,\quad\ s_{{\rm{u,r}}}+s_{{\rm{v,r}}}\leq 2-\theta_{{\rm{u,v}}}^{{\rm{r}}},\forall{\rm{u}\in\mathbb{U},{\rm{v}}\in\mathbb{\tilde{U}}},{\rm{r}\in\mathbb{R}}, (20)

where binary parameter θu,vr\theta_{{\rm{u,v}}}^{{\rm{r}}} with value 1 indicating train service u𝕌{\rm{u}\in\mathbb{U}} and train service v𝕌~{\rm{v}}\in\mathbb{\tilde{U}} meet the headway constraints at station r{\rm{r}\in\mathbb{R}}. Constraint(20) means that train service u𝕌{\rm{u}\in\mathbb{U}} and train service 𝕌~\mathbb{\tilde{U}} can not visit station r{\rm{r}\in\mathbb{R}} if they do not satisfy the minimum headway. Remark that we only need to restrict the relation between train services in set 𝕌\mathbb{U} and train services in set 𝕌~\mathbb{\tilde{U}}, while other conditions follow the the minimum headway.

3.5 Passenger assignment

Recall that passengers are either assigned to train services or fail to board any train. Passenger assignment constraints can be shown as

u𝕌xpu+xp=n^p,p,\quad\ \sum_{{\rm{u}}\in\mathbb{U}}x_{{\rm{p}}}^{{\rm{u}}}+x_{{\rm{p}}}={\rm{\hat{n}_{p}}},\forall{\rm{p}\in\mathbb{P}},\qquad\qquad\qquad (21a)
xpun^p(tu,o^pd+1f~u,pw~u,pau),u𝕌𝕌~,p.\quad\ x_{{\rm{p}}}^{{\rm{u}}}\leq{\rm{\hat{n}_{p}}}\cdot\left(\begin{matrix}t_{{\rm{u,\hat{o}_{p}}}}^{d}+1\\ {\tilde{\rm{f}}_{\rm{u,p}}}\\ {\rm{\tilde{w}_{u,p}}}\\ a_{{\rm{u}}}\end{matrix}\right),\forall{\rm{u}}\in\mathbb{U}\cup\mathbb{\tilde{U}},{\rm{p}}\in\mathbb{P}. (21b)

Constraint (21a) denotes the flow conservation of passenger assignment. Constraint(21b) means that the passenger flow p can be assigned into train service u only if: (a) the train service u𝕌𝕌~{\rm{u}}\in\mathbb{U}\cup\mathbb{\tilde{U}} departures from the origin station of passenger flow p; (b) the direction of train service u𝕌𝕌~{\rm{u}}\in\mathbb{U}\cup\mathbb{\tilde{U}} is same as the direction of passenger group p{\rm{p}}\in\mathbb{P}; (c) the arrival time of train service u𝕌𝕌~{\rm{u}}\in\mathbb{U}\cup\mathbb{\tilde{U}} at the origin station of passenger flow p{\rm{p}}\in\mathbb{P} is not less than the production time of passenger group p{\rm{p}}\in\mathbb{P}; (d) the train service u𝕌𝕌~{\rm{u}}\in\mathbb{U}\cup\mathbb{\tilde{U}} is activated. The passenger flow p{\rm{p}}\in\mathbb{P} can not be assigned into train service u𝕌𝕌~{\rm{u}}\in\mathbb{U}\cup\mathbb{\tilde{U}} if either of the condition (a)-(d) can not be met.

3.6 Train capacity

Recall that the number of passengers on the train can not exceed the train capacity, which is denoted as

Cur=pxpuφpu,r,u𝕌𝕌~,r,\ \quad C_{{\rm{u}}}^{{\rm{r}}}=\sum_{{\rm{p}\in\mathbb{P}}}x_{{\rm{p}}}^{{\rm{u}}}\varphi_{{\rm{p}}}^{{\rm{u,r}}},\forall{\rm{u}\in\mathbb{U}}\cup\mathbb{\tilde{U}},\rm{r}\in\mathbb{R},\qquad (22a)
CurC¯u,u𝕌𝕌~,r,\ \quad C_{{\rm{u}}}^{{\rm{r}}}\leq{\rm{\bar{C}_{u}}},\forall{\rm{u}\in\mathbb{U}}\cup\mathbb{\tilde{U}},\rm{r}\in\mathbb{R},\qquad\qquad\quad (22b)

where the binary parameter φpu,r\varphi_{{\rm{p}}}^{{\rm{u,r}}} with value 1 indicating the passenger group p{\rm{p}}\in\mathbb{P} is onboard after it arrives at station r\rm{r}\in\mathbb{R} by taking train service u𝕌𝕌~{\rm{u}}\in\mathbb{U}\cup\mathbb{\tilde{U}}, and 0 otherwise. A tailored dynamic filling algorithm is proposed to determine the value of φpu,r\varphi_{{\rm{p}}}^{{\rm{u,r}}} (see as C.3). Constraint (22a) presents the formulation on the number of passengers on the train after it arrives at each station. Constraint (22b) denotes that the number of passengers in the train can not exceed train capacity. Note that this formulation can also deal with the condition while trains have different transport capacities.

Refer to caption
Figure 4: Identification of passenger holding
Refer to caption
Figure 5: Identification of departure passenger flow

Figure 5 depicts an illustration of the parameter φpu,r\varphi_{{\rm{p}}}^{{\rm{u,r}}}. The passenger flows are classified into two types: those that travel through the disruption area, denoted as p1, and those that do not travel through the disruption area, denoted as p2. For the passenger flow p1, if this passenger flow has boarded train service u1 (train service u1 conflicts with spatio-temporal area, i.e., Θu1=1\Theta_{{\rm{u1}}}=1), then the parameter φp1u1,r\varphi_{{\rm{p1}}}^{{\rm{u1,r}}} equals zero from station o^p1{\rm{\hat{o}_{p1}}} to the terminal station of disruption area; meanwhile, if this passenger flow has boarded train service u2 (train service u2 conflicts with spatio ; For the passenger flow p2, regardless of whatever train service is used, the parameter φp2u,r\varphi_{{\rm{p2}}}^{{\rm{u,r}}} equals zero from station o^p2{\rm{\hat{o}_{p2}}} to d^p21{\rm{\hat{d}_{p2}}}-1.

3.7 Measurement of passenger accumulation

Passenger accumulation is an indicator for assessing the quality of an operational timetable. Passenger accumulation is often assessed by stations, and passenger flow associated with a station is classified into three types: arrival flow, departure flow, and accumulation flow. The arrival flow refers to passengers arriving at a station, and the departure flow refers to people departing from this station. The accumulation flow represents passengers waiting at a station, and this sort of passenger flow indicates the station’s pressure. The metro managers can first acquire real-time passenger demand by observing real-time passenger accumulation in each station, and then response strategies are implemented. Second, we should pay closer attention to passenger accumulation at the disruption area’s terminal stations during the disruption time, as passenger accumulation in these stations grows quickly, posing safety threats to a station.

The idea of instantaneous accumulation flow is introduced to describe the instantaneous variation of passengers at a disruption area’s terminal station, and the formulation of instantaneous passenger flow is shown below:

𝒢pr,t=f^pn^pθ~pt,r+u𝕌θˇp,ut,rxpu,p,rT1,t𝕋,\ \quad\mathscr{G}_{{\rm{p}}}^{{\rm{r,t}}}=\hat{{\rm{f}}}_{{\rm{p}}}{\rm{\hat{n}_{p}}}\tilde{\theta}_{{\rm{p}}}^{{\rm{t,r}}}+\sum\limits_{{\rm{u}}\in\mathbb{U}}\check{\theta}_{{\rm{p,u}}}^{{\rm{t,r}}}x_{{\rm{p}}}^{{\rm{u}}},\forall{\rm{p}}\in\mathbb{P},{\rm{r}}\in\mathbb{R}_{\rm{T}}^{1},{\rm{t}}\in\mathbb{T}, (23a)
𝒢pr,t=(1f^p)n^pθ~pt,r+u𝕌θˇp,ut,rxpu,p,rT2,t𝕋,\qquad\qquad\mathscr{G}_{{\rm{p}}}^{{\rm{r,t}}}=(1-\hat{{\rm{f}}}_{{\rm{p}}}){\rm{\hat{n}_{p}}}\tilde{\theta}_{{\rm{p}}}^{{\rm{t,r}}}+\sum\limits_{{\rm{u}}\in\mathbb{U}}\check{\theta}_{{\rm{p,u}}}^{{\rm{t,r}}}x_{{\rm{p}}}^{{\rm{u}}},\forall{\rm{p}}\in\mathbb{P},{\rm{r}}\in\mathbb{R}_{\rm{T}}^{2},{\rm{t}}\in\mathbb{T}, (23b)

where binary parameter θ~pt,r\tilde{\theta}_{{\rm{p}}}^{{\rm{t,r}}} with value 1 indicating that passenger group p{\rm{p}}\in\mathbb{P} originates from station r{\rm{r}}\in\mathbb{R} at time t𝕋{\rm{t}}\in\mathbb{T}, and 0 otherwise. Binary parameter θˇp,ut,r\check{\theta}_{{\rm{p,u}}}^{{\rm{t,r}}} with value 1 indicating passenger group p{\rm{p}}\in\mathbb{P} who takes train service u𝕌𝕌~{\rm{u}}\in\mathbb{U}\cup\mathbb{\tilde{U}} demands transferring at station r{\rm{r}}\in\mathbb{R} at time t𝕋{\rm{t}}\in\mathbb{T}, and 0 otherwise. Constraints (23a)-(23b) present the formulation of instantaneous accumulation flow at station T1\mathbb{R}_{\rm{T}}^{1} and T2\mathbb{R}_{\rm{T}}^{2} separately. The instantaneous accumulation flow in time t𝕋{\rm{t}}\in\mathbb{T} at terminal station rT1T2{\rm{r}}\in\mathbb{R}_{\rm{T}}^{1}\cup\mathbb{R}_{\rm{T}}^{2} is compromised of two parts: the one is the passenger flow originating from station rT1T2{\rm{r}}\in\mathbb{R}_{\rm{T}}^{1}\cup\mathbb{R}_{\rm{T}}^{2} at time t𝕋{\rm{t}}\in\mathbb{T}; the other is the passenger flow transferring at station rT1T2{\rm{r}}\in\mathbb{R}_{\rm{T}}^{1}\cup\mathbb{R}_{\rm{T}}^{2} at time t𝕋{\rm{t}}\in\mathbb{T}, and transfer passenger flow exists only at the terminal station of the disruption area. Note that, the instantaneous accumulation flow at the terminal station of disruption area would be an input for the design of response vehicles, as the accumulated passengers have to transfer at this terminal station.
Property 1. (uniqueness of instantaneous arrival parameter) the instantaneous arrival parameters θ~pt,r\tilde{\theta}_{{\rm{p}}}^{{\rm{t,r}}} have following properties:

rOt𝕋θ~pt,r=1,p,\sum\limits_{{\rm{r}}\in\mathbb{R}_{{\rm{O}}}}\sum\limits_{{\rm{t}}\in\mathbb{T}}\tilde{\theta}_{{\rm{p}}}^{{\rm{t,r}}}=1,\forall{\rm{p}}\in\mathbb{P},\qquad\qquad\qquad\quad (24)

Property 2. (weak uniqueness of instantaneous transfer parameter) the instantaneous arrival parameters θˇp,ut,r\check{\theta}_{{\rm{p,u}}}^{{\rm{t,r}}} have following properties:

rOt𝕋u𝕌θˇp,ut,r1,p.\sum\limits_{{\rm{r}}\in\mathbb{R}_{{\rm{O}}}}\sum\limits_{{\rm{t}}\in\mathbb{T}}\sum\limits_{{\rm{u}}\in\mathbb{U}}\check{\theta}_{{\rm{p,u}}}^{{\rm{t,r}}}\leq 1,\forall{\rm{p}}\in\mathbb{P}.\qquad\qquad\quad (25)

The property 1-2 can be proved by their definitions. The weak uniqueness denotes that rOt𝕋u𝕌θˇp,ut,r=1\sum\limits_{{\rm{r}}\in\mathbb{R}_{{\rm{O}}}}\sum\limits_{{\rm{t}}\in\mathbb{T}}\sum\limits_{{\rm{u}}\in\mathbb{U}}\check{\theta}_{{\rm{p,u}}}^{{\rm{t,r}}}=1 only if rTφpr=1\sum\limits_{{\rm{r}}\in\mathbb{R}_{{\rm{T}}}}\varphi_{{\rm{p}}}^{{\rm{r}}}=1; and rOt𝕋u𝕌θˇp,ut,r=0\sum\limits_{{\rm{r}}\in\mathbb{R}_{{\rm{O}}}}\sum\limits_{{\rm{t}}\in\mathbb{T}}\sum\limits_{{\rm{u}}\in\mathbb{U}}\check{\theta}_{{\rm{p,u}}}^{{\rm{t,r}}}=0 otherwise.

The formulation of instantaneous passenger flow can be converted into its accumulated form by replacing the instantaneous parameters. Passenger accumulation can be measured as follows:

Apr,t={n^pϑ~pt,r+u𝕌𝕌~ϑˇp,ut,rxpu,p,rO,t𝕋;0,p,rO,t𝕋,\qquad\quad\qquad A_{{\rm{p}}}^{{\rm{r,t}}}=\begin{cases}{\rm{\hat{n}_{p}}}\tilde{\vartheta}_{{\rm{p}}}^{{\rm{t,r}}}+\sum\limits_{{\rm{u}}\in\mathbb{U}\cup\mathbb{\tilde{U}}}\check{\vartheta}_{{\rm{p,u}}}^{{\rm{t,r}}}x_{{\rm{p}}}^{{\rm{u}}},\forall{\rm{p}}\in\mathbb{P},{\rm{r}}\in\mathbb{R}_{\rm{O}},{\rm{t}}\in\mathbb{T};\\ 0,\forall{\rm{p}}\in\mathbb{P},{\rm{r}}\in\mathbb{R}\setminus\mathbb{R}_{\rm{O}},{\rm{t}}\in\mathbb{T},\end{cases} (26a)
Dpr,t={u𝕌𝕌~xpuϑ^u,pr,t,p,rO,t𝕋;0,p,rO,t𝕋,\ \qquad D_{{\rm{p}}}^{{\rm{r,t}}}=\begin{cases}\sum\limits_{{\rm{u}}\in\mathbb{U}\cup\mathbb{\tilde{U}}}x_{{\rm{p}}}^{{\rm{u}}}\hat{\vartheta}_{{\rm{u,p}}}^{{\rm{r,t}}},\forall{\rm{p}}\in\mathbb{P},{\rm{r}}\in\mathbb{R}_{\rm{O}},{\rm{t}}\in\mathbb{T};\\ 0,\forall{\rm{p}}\in\mathbb{P},{\rm{r}}\in\mathbb{R}\setminus\mathbb{R}_{\rm{O}},{\rm{t}}\in\mathbb{T},\end{cases} (26b)
Gpr,t=Apr,tDpr,t,p,r,t𝕋,G_{{\rm{p}}}^{{\rm{r,t}}}=A_{{\rm{p}}}^{{\rm{r,t}}}-D_{{\rm{p}}}^{{\rm{r,t}}},\forall{\rm{p}}\in\mathbb{P},{\rm{r}}\in\mathbb{R},{\rm{t}}\in\mathbb{T},\quad (26c)

where binary parameter ϑ~pt,r\tilde{\vartheta}_{{\rm{p}}}^{{\rm{t,r}}} with value 1 indicating that passenger group p{\rm{p}}\in\mathbb{P} has arrived at station r{\rm{r}}\in\mathbb{R} at time t𝕋{\rm{t}}\in\mathbb{T}, and 0 otherwise. Binary parameter ϑ^u,pr,t\hat{\vartheta}_{{\rm{u,p}}}^{{\rm{r,t}}} with value 1 indicating that passenger group p{\rm{p}}\in\mathbb{P} who takes train service u𝕌𝕌~{\rm{u}}\in\mathbb{U}\cup\mathbb{\tilde{U}} has departed from station r{\rm{r}}\in\mathbb{R} at time t𝕋{\rm{t}}\in\mathbb{T}, and 0 otherwise. Constraint (26a) denotes the formulation of the accumulated arrival passenger flow at a station. Constraint (26b) denotes the formulation of the accumulated departure passenger flow at a station. Constraint(26c) denotes the formulation of the accumulated stranded passenger flow at a station.

Refer to caption
Figure 6: Identification of arrival passenger flow

In Figure 6 (a)-(b), for passenger flow p1{\rm{p1}\in\mathbb{P}}, there are two parameters describing the arrival of passenger flow p1: instantaneous arrival parameter θ~p1t,r\tilde{\theta}_{{\rm{p1}}}^{{\rm{t,r}}} and accumulated arrival parameter ϑ~p1t,r\tilde{\vartheta}_{{\rm{p1}}}^{{\rm{t,r}}}. For the instantaneous parameter, θ~p1t,r\tilde{\theta}_{{\rm{p1}}}^{{\rm{t,r}}} equals one only if the station r and time t matches with the information of passenger flow p1.i.e., ϑ~p1t,r=1\tilde{\vartheta}_{{\rm{p1}}}^{{\rm{t,r}}}=1 if r=o^p1,t=t^p1{\rm{r=\hat{o}_{p1}},t=\hat{t}_{p1}}, and 0 otherwise; while for the accumulated parameter, ϑ~p1t,r=1\tilde{\vartheta}_{{\rm{p1}}}^{{\rm{t,r}}}=1 if r=o^p1,tt^p1{\rm{r=\hat{o}_{p1}},t\geq\hat{t}_{p1}}, and 0 otherwise.

In Figure 7 (a)-(b), for the instantaneous transfer flow p1, the parameter θˇp,ut,r\check{\theta}_{{\rm{p,u}}}^{{\rm{t,r}}} equals one only if the passenger flow p1 arrives at his transfer station at time t.i.e., θˇp,ut,r\check{\theta}_{{\rm{p,u}}}^{{\rm{t,r}}}=1 if t=tu,ra,φpu,r=1,rT{\rm{t}}_{{\rm{u,r}}}^{a},\varphi_{{\rm{p}}}^{{\rm{u,r}}}=1,{\rm{r}}\in\mathbb{R}_{\rm{T}}, and 0 otherwise; while for the accumulated transfer flow p1, the parameter φpu,r\varphi_{{\rm{p}}}^{{\rm{u,r}}} equals one if the passenger flow p1 has arrived at his transfer station T\mathbb{R}_{\rm{T}} at time t.i.e.,θˇp,ut,r\check{\theta}_{{\rm{p,u}}}^{{\rm{t,r}}}=1 if t tu,ra,φpu,r=1,rT\geq{\rm{t}}_{{\rm{u,r}}}^{a},\varphi_{{\rm{p}}}^{{\rm{u,r}}}=1,{\rm{r}}\in\mathbb{R}_{\rm{T}}, and 0 otherwise.

As shown in Figure 5, for the accumulated transfer flow p1 (p1{\rm{p1}\in\mathbb{P}}), the parameter ϑ^u,p1r,t\hat{\vartheta}_{{\rm{u,p1}}}^{{\rm{r,t}}} equals one if the passenger flow p1 has departed from station r at time t.i.e., ϑ^u,pr,t=1\hat{\vartheta}_{{\rm{u,p}}}^{{\rm{r,t}}}=1 if t tu,rd,φpu,r=1\geq{\rm{t}}_{{\rm{u,r}}}^{d},\varphi_{{\rm{p}}}^{{\rm{u,r}}}=1, and 0 otherwise.
Remark 2. The instantaneous parameters and their accumulation parameters satisfy:

(1)θ~pt,rϑ~pt,r,p,rO\tilde{\theta}_{{\rm{p}}}^{{\rm{t,r}}}\leq\tilde{\vartheta}_{{\rm{p}}}^{{\rm{t,r}}},\forall{\rm{p}}\in\mathbb{P},{\rm{r}}\in\mathbb{R}_{\rm{O}};

(2)θˇp,ut,rϑˇp,ut,r,p,u𝕌,rO\check{\theta}_{{\rm{p,u}}}^{{\rm{t,r}}}\leq\check{\vartheta}_{{\rm{p,u}}}^{{\rm{t,r}}},\forall{\rm{p}}\in\mathbb{P},{\rm{u}\in\mathbb{U}},{\rm{r}}\in\mathbb{R}_{\rm{O}}.
Proof. Remark 2 can be proved by their definitions.

Refer to caption
Figure 7: Identification of transfer passenger flow

4 Stage 2: response vehicle scheduling

In this section, we first map the passenger demand into the demand of response vehicles in the disruption area. This mathematical mapping is compromised of two parts: task mapping and demand mapping. Task mapping means to map the origin/destination of passengers into the origin/destination of response vehicles, while demand mapping means to map the real-time passenger demand into the real-time demand of response vehicles. Second, considering the real-time demand of response vehicles, we introduce the SO-DTA model ((Ziliaskopoulos [2000])) to guide the real-time routes of response vehicles.

4.1 Passenger mapping


Remark 3. (task mapping) Let a mapping FT:(+||,+||)(+||,+||)F_{T}:(\mathbb{Z}_{+}^{|\mathbb{P}|},\mathbb{Z}_{+}^{|\mathbb{P}|})\to(\mathbb{Z}_{+}^{|\mathbb{P}|},\mathbb{Z}_{+}^{|\mathbb{P}|}) be given by (o~,d~)=FT(o^,d^)({\rm{\tilde{o}}},{\rm{\tilde{d}}})=F_{T}({\rm{\hat{o}}},{\rm{\hat{d}}}). Then,

(1) o~p=ξp1[f^pr1+(1f^p)r2]+(1ξp1)o^p{\rm{\tilde{o}_{p}}}=\xi_{\rm{p}}^{1}[{\rm{\hat{f}_{p}}}{\rm{r}_{1}^{*}}+(1-{\rm{\hat{f}_{p}}}){\rm{r}_{2}^{*}}]+(1-\xi_{\rm{p}}^{1}){\rm{\hat{o}_{p}}},

(2) d~p=ξp2[(1f^p)r1+f^pr2]+(1ξp2)d^p{\rm{\tilde{d}_{p}}}=\xi_{\rm{p}}^{2}[(1-{\rm{\hat{f}_{p}}}){\rm{r}_{1}^{*}}+{\rm{\hat{f}_{p}}}{\rm{r}_{2}^{*}}]+(1-\xi_{\rm{p}}^{2}){\rm{\hat{d}_{p}}}.

Binary parameter ξp1/ξp2\xi_{\rm{p}}^{1}/\xi_{\rm{p}}^{2} with value 1 indicating that the initial origin/destination of passenger flow p{\rm{p}}\in\mathbb{P} should be transferred, and 0 otherwise. r1{\rm{r}_{1}^{*}} and r2{\rm{r}_{2}^{*}} are the terminal stations of disruption area in the positive direction,i.e., r1=argminrD{r},r2=argmaxrD{r}{\rm{r}_{1}^{*}}=\mathop{\arg\min}_{{\rm{r}}\in\mathbb{R}_{{\rm{D}}}}\{{\rm{r}}\},{\rm{r}_{2}^{*}}=\mathop{\arg\max}_{{\rm{r}}\in\mathbb{R}_{{\rm{D}}}}\{{\rm{r}}\}. Note that, task mapping aims to determine the transportation task of a passenger group in the disruption area. For example, for a passenger group with OD pair (1,7), and the disruption area is from station 3 to 5, then the transferred OD pair would be (3,5). The task of response vehicles is to transport this passenger flow from station 3 to station 5.
Remark 4. (demand mapping) Let a mapping FD:R+|O|×|𝕋D|×||R+||×|𝕄|×{𝕋R|F_{D}:{\rm{R}}_{+}^{|{\rm{\mathbb{R}_{{\rm{O}}}}}|\times|{\rm{\mathbb{T}_{{\rm{D}}}}}|\times|{\rm{\mathbb{P}}}|}\to{\rm{R}}_{+}^{|{\rm{\mathbb{C}}}|\times|{\rm{\mathbb{M}}}|\times\{\rm{\mathbb{T}_{{\rm{R}}}}|} be given by d=FD(𝒢){\rm{d}}=F_{D}(\mathscr{G}). Then the demand of response vehicles is denoted as:

di,mt={rOpτ𝕋~R(t)𝒢pr,τδ~i,rm,p/CR,i,t𝕋R,m𝕄;0,else;\qquad\qquad{\rm{d}}_{{\rm{i,m}}}^{{\rm{t}}}=\begin{cases}\lceil\sum\limits_{{\rm{r}}\in\mathbb{R}_{{\rm{O}}}}\sum\limits_{{\rm{p}}\in\mathbb{P}}\sum\limits_{\tau\in\mathbb{\tilde{T}}_{{\rm{R}}}({\rm{t}})}\mathscr{G}_{{\rm{p}}}^{{\rm{r,\tau}}}\tilde{\delta}_{{\rm{i,r}}}^{{\rm{m,p}}}/{\rm{C_{R}}}\rceil,\forall{\rm{i}}\in\mathbb{C},{\rm{t}}\in\mathbb{T}_{{\rm{R}}},{\rm{m}}\in\mathbb{M};\\ 0,else;\end{cases} (27)

Binary parameter δ~i,rm,p\tilde{\delta}_{{\rm{i,r}}}^{{\rm{m,p}}} with value 1 indicating that the passenger flow p{\rm{p}}\in\mathbb{P} at station r{\rm{r}}\in\mathbb{R} matches with the transportation task (OD pair) of class-m response vehicles departing from cell i.i.e., δ~i,rm,p=1\tilde{\delta}_{{\rm{i,r}}}^{{\rm{m,p}}}=1 if o~p=om,d~p=dm{\rm{\tilde{o}_{p}}}={\rm{o_{m}}},{\rm{\tilde{d}_{p}}}={\rm{d_{m}}}, and cell i is station r; and 0 otherwise. In this section, the time set 𝕋\mathbb{T} is divided into 𝕋R\mathbb{T}_{{\rm{R}}} periods, and 𝕋~R\mathbb{\tilde{T}}_{{\rm{R}}}(t) denotes the set of discrete time of time period t𝕋R{\rm{t}}\in\mathbb{T}_{{\rm{R}}}. For example, for a frequency-based response vehicle fleet, the set 𝕋~R\mathbb{\tilde{T}}_{{\rm{R}}}(2)={ωF,,2ωF}\{\omega_{\rm{F}},...,2\omega_{\rm{F}}\} if the departure frequency of response vehicle is ωF\omega_{\rm{F}}.

4.2 Formulations

To capture the real-time traffic dynamics, the constraints of response vehicle routing are formulated based on the well-known structure of SO-DTA. In our proposed model, the response vehicles are loaded by the method of cell transmission model(CTM). Furthermore, the state transition of cells is formulated as flow conservation constraints. Considering the character of cells, the flow conservations are also classified by cell types. That is, the flow conservation constraints should be distinguished among the source cells, sink cells, and other cells. Also, the demand and supply functions are relaxed as flow propagation constraints (Ziliaskopoulos [2000]). In addition, other necessary constraints, such as the initial state of links and cells, and nonnegative variables are also concluded.

minZ2=t𝕋Rm𝕄iSαtyi,mt\min Z_{2}=\sum_{{\rm{t}}\in\mathbb{T}_{{\rm{R}}}}\sum_{{\rm{m}}\in\mathbb{M}}\sum_{{\rm{i}}\in\mathbb{C}\setminus\mathbb{C}_{{\rm{S}}}}\alpha_{\rm{t}}y_{{\rm{i,m}}}^{{\rm{t}}}\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad (28)
s.t.yi,mtyi,mt1kΓ(i)zk,i,mt1+jΓ(i)zi,j,mt1=0,i{S,R},t{1,,|𝕋R|},m𝕄,s.t.y_{{\rm{i,m}}}^{{\rm{t}}}-y_{{\rm{i,m}}}^{{\rm{t-1}}}-\sum_{{\rm{k}\in\Gamma(i)}}z_{{\rm{k,i,m}}}^{{\rm{t-1}}}+\sum_{{\rm{j}\in\Gamma^{-}(i)}}z_{{\rm{i,j,m}}}^{{\rm{t-1}}}=0,\forall{\rm{i}}\in\mathbb{C}\setminus\{\mathbb{C}_{{\rm{S}}},\mathbb{C}_{{\rm{R}}}\},{\rm{t}}\in\{1,...,|\mathbb{T}_{{\rm{R}}}|\},{\rm{m}}\in\mathbb{M}, (29a)
yi,mtyi,mt1+zk,i,mt1=di,mt1,iR,t{1,,|𝕋R|},m𝕄,\ \quad y_{{\rm{i,m}}}^{{\rm{t}}}-y_{{\rm{i,m}}}^{{\rm{t-1}}}+z_{{\rm{k,i,m}}}^{{\rm{t-1}}}={\rm{d}}_{{\rm{i,m}}}^{{\rm{t-1}}},\forall{\rm{i}}\in\mathbb{C}_{\rm{R}},{\rm{t}}\in\{1,...,|\mathbb{T}_{{\rm{R}}}|\},{\rm{m}}\in\mathbb{M},\qquad\qquad\qquad\qquad\qquad (29b)
t𝕋RkΓ(S)zk,S,mt=t𝕋RiRdi,mt1,m𝕄,\ \quad\sum_{{\rm{t}}\in\mathbb{T}_{{\rm{R}}}}\sum_{{\rm{k}\in\Gamma({\rm{\mathbb{C}_{\rm{S}})}}}}z_{{\rm{k,{\rm{\mathbb{C}_{\rm{S}},m}}}}}^{{\rm{t}}}=\sum_{{\rm{t}}\in\mathbb{T}_{{\rm{R}}}}\sum_{{\rm{i}\in{\rm{\mathbb{C}_{\rm{R}}}}}}{\rm{d}}_{{\rm{i,m}}}^{{\rm{t-1}}},\forall{\rm{m}}\in\mathbb{M},\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad (29c)
jΓ(i)zi,j,mtyi,mt,ij{S,R},t𝕋R,m𝕄,\ \quad\sum_{{\rm{j}\in\Gamma^{-}(i)}}z_{{\rm{i,j,m}}}^{{\rm{t}}}\leq y_{{\rm{i,m}}}^{{\rm{t}}},\forall{\rm{i}}\neq{\rm{j}}\in\mathbb{C}\setminus\{\mathbb{C}_{{\rm{S}}},\mathbb{C}_{{\rm{R}}}\},{\rm{t}}\in\mathbb{T}_{{\rm{R}}},{\rm{m}}\in\mathbb{M},\qquad\qquad\qquad\qquad\qquad\quad (30a)
jΓ(i)zi,j,mtQi,m,i{S,R},t𝕋R,m𝕄,\ \quad\sum_{{\rm{j}\in\Gamma^{-}(i)}}z_{{\rm{i,j,m}}}^{{\rm{t}}}\leq{\rm{Q_{i,m}}},\forall{\rm{i}}\in\mathbb{C}\setminus\{\mathbb{C}_{{\rm{S}}},\mathbb{C}_{{\rm{R}}}\},{\rm{t}}\in\mathbb{T}_{{\rm{R}}},{\rm{m}}\in\mathbb{M},\qquad\qquad\qquad\qquad\qquad\qquad (30b)
kΓ(i)zk,i,mtQi,m,i{S,R},t𝕋R,m𝕄,\ \quad\sum_{{\rm{k}\in\Gamma(i)}}z_{{\rm{k,i,m}}}^{{\rm{t}}}\leq{\rm{Q_{i,m}}},\forall{\rm{i}}\in\mathbb{C}\setminus\{\mathbb{C}_{{\rm{S}}},\mathbb{C}_{{\rm{R}}}\},{\rm{t}}\in\mathbb{T}_{{\rm{R}}},{\rm{m}}\in\mathbb{M},\qquad\qquad\qquad\qquad\qquad\qquad (31a)
kΓ(i)zk,i,mtwmvm(Ni,mtyi,mt),i{S,R},t𝕋R,m𝕄,\ \quad\sum_{{\rm{k}\in\Gamma(i)}}z_{{\rm{k,i,m}}}^{{\rm{t}}}\leq\frac{{\rm{w_{m}}}}{{\rm{v_{m}}}}({\rm{N_{i,m}^{t}}}-y_{{\rm{i,m}}}^{{\rm{t}}}),\forall{\rm{i}}\in\mathbb{C}\setminus\{\mathbb{C}_{{\rm{S}}},\mathbb{C}_{{\rm{R}}}\},{\rm{t}}\in\mathbb{T}_{{\rm{R}}},{\rm{m}}\in\mathbb{M},\qquad\qquad\qquad\quad (31b)
di,mt={rOpτ𝕋~R(t)𝒢pr,τδ~i,rm,p/CR,i,t𝕋R,m𝕄;0,else;\ \quad{\rm{d}}_{{\rm{i,m}}}^{{\rm{t}}}=\begin{cases}\lceil\sum\limits_{{\rm{r}}\in\mathbb{R}_{{\rm{O}}}}\sum\limits_{{\rm{p}}\in\mathbb{P}}\sum\limits_{\tau\in\mathbb{\tilde{T}}_{{\rm{R}}}({\rm{t}})}\mathscr{G}_{{\rm{p}}}^{{\rm{r,\tau}}}\tilde{\delta}_{{\rm{i,r}}}^{{\rm{m,p}}}/{\rm{C_{R}}}\rceil,\forall{\rm{i}}\in\mathbb{C},{\rm{t}}\in\mathbb{T}_{{\rm{R}}},{\rm{m}}\in\mathbb{M};\\ 0,else;\end{cases}\qquad\qquad\qquad\quad (32)
yi,mt0,i,t=0,m𝕄,\ \quad y_{{\rm{i,m}}}^{{\rm{t}}}\leq 0,\forall{\rm{i}}\in\mathbb{C},{\rm{t}}=0,{\rm{m}}\in\mathbb{M},\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad (33a)
zi,j,mt0,i,j,t=0,m𝕄,\ \quad z_{{\rm{i,j,m}}}^{{\rm{t}}}\leq 0,\forall{\rm{i,j}}\in\mathbb{C},{\rm{t}}=0,{\rm{m}}\in\mathbb{M},\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\quad (33b)
yi,mt0,i,t𝕋R,m𝕄,\ \quad y_{{\rm{i,m}}}^{{\rm{t}}}\geq 0,\forall{\rm{i}}\in\mathbb{C},{\rm{t}}\in\mathbb{T}_{{\rm{R}}},{\rm{m}}\in\mathbb{M},\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\quad (34a)
zi,j,mt0,i,t𝕋R,m𝕄.\ \quad z_{{\rm{i,j,m}}}^{{\rm{t}}}\geq 0,\forall{\rm{i}}\in\mathbb{C},{\rm{t}}\in\mathbb{T}_{{\rm{R}}},{\rm{m}}\in\mathbb{M}.\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\quad (34b)

The objective (28) is to minimize the systematic total travel time of response vehicles. Constraint (29a) describes traffic flow conservation for all road cells, excluding source and sink cells. That is, the number of class-m response vehicles in a road cell i at time t is determined by the sum of this number at time t-1 and the number of class-m response vehicles going into this cell i at time t-1, and minus the number of class-m response vehicles leaving from cell i at time t-1. Note that, the classification of response vehicles is identified by their OD pairs. This flow conservation has revealed the temporal state transition of road cells. Constraint (29b) denotes the flow conservation constraint in the source cell. Constraint (29c) denotes the flow conservation constraint in the sink cell.

Constraints (30a)-(31b) have defined the process of traffic flow loading for class-m vehicles, which is based on the relaxation of the CTM. The maximum outflow from a road cell to its downstream road cells is limited by constraint (30a)-(30b). Firstly, the practical outflow of road cell i is restricted by the number of response vehicles in cell i. Secondly, the outflow capacity of road cell i should also be taken into account. Note that, Qi,m{\rm{Q_{i,m}}} is a parameter reflecting the road condition of road cells. In the meanwhile, the maximum inflow from upstream cells to a cell is described as constraints (31a) and (31b). Firstly, the practical inflow of a road cell i is restricted by the inflow capacity of this cell. Secondly, the available space for receiving response vehicles should also be considered. Note that, the available space is estimated by the spare space of this cell, as well as the free-flow speed and the backward shock wave propagation speed of response vehicles. Constraints (32) denotes the vehicle demand in each cell. Constraints (33a) and (33b) denote the initial state of cells and links. That is, the discrete road network is empty before assigning the response vehicles. Constraints (34a) - (34b) denote the decision variables of this model, and the decision variables are both continuous and nonnegative.

5 Case study

5.1 Basic experiment

5.1.1 parameter setting

Figure 8 depicts the entire Beijing Metro Line 9, which has thirteen metro stations from Guo Gong Zhuang Station (GGZ) to National Library Station (NL). An unexpected disruption is taking place between Feng Tai South Road Station (FTSR) and Military Museum Station (MM), with the disruption lasting from 8:00 to 9:00. The metro transportation system is divided into two areas: in MS-1, the station set concludes four stations: GGZ station, FTSP station, KYR station, and FTSR station. We denote this set as O1={1,2,3,4}\mathbb{R}_{{\rm{O}}}^{1}=\{1,2,3,4\}; In the MS-2, it also concludes four stations: MM station, BDZ station, BSBS station, NL station, and we denote this set as O2={10,11,12,13}\mathbb{R}_{{\rm{O}}}^{2}=\{10,11,12,13\}. Furthermore, the station set of disruption area can be denotes as D={4,5,6,7,8,9,10}\mathbb{R}_{{\rm{D}}}=\{4,5,6,7,8,9,10\}. The terminal station sets of disruption area can be denoted as: T1={4}\mathbb{R}_{{\rm{T}}}^{1}=\{4\}, T2={10}\mathbb{R}_{{\rm{T}}}^{2}=\{10\}.

Refer to caption
Figure 8: Beijing Metro Line 9

The partial timetable of Beijing Metro Line 9 is shown in Figure 9. In the original normal timetable generated by the Yizhuang metro line’s workday timetable, there are 118 train services from 7:20 to 9:30. There are 58 positive-direction train services and 60 negative-direction train services in this normal timetable. The volume of train service is set as C¯u=1000\rm{\bar{C}_{{\rm{u}}}}=1000.

Table 1: Parameters of response vehicles
Class Length (m) Passenger capacity Free-flow speed (m/s) Shock wave speed (m/s)
Bus 12 40 20 10
Table 2: Signal positions and their fixed time plans
Signal position (in cell #) Cycle time (time intervals) Green time (time intervals) Time when first green appear (time intervals)
3 5 2 0
4 5 2 0
11 5 2 4
20 5 2 4

The practical road condition should be considered when scheduling response vehicles in the disruption area. Figure D.1 of D depicts the topological structure of the road network along the disrupted metro line and its cell discretion grapha. The cell length is equal to the free-flow speed multiplied by the 20-second time interval. As a result, the cell length is 400 m, the maximum capacity is 11 vehicles per time step, and the maximum occupancy per cell is 33 vehicles. Because the stations from FTES to BJW are closed for safety, response vehicles evaluate twelve OD pairs: from the origin station FTSR to the destination station FTES, QLZ, LLQ, LLQE, BJW, and MM; and from the origin station MM to the destination stations BJW, LLQE, LLQ, QLZ, FTNA, and FTSR. The response vehicle parameters are consistent, as shown in Table 1. The maximum flow velocity of the bus is 1992 vph for each lane, according to the triangle fundamental diagram. Table 2 shows the signal intersections and their fixed time plans.

Refer to caption
Figure 9: Normal timetable

5.1.2 rescheduled metro timetable

As shown in Figure 9, an unexpected disruption occurs during the normal timetable from 8:00 to 9:00, and the disruption area spans from FSTR station to MM station. The spatio-temporal disruption area is a rectangle area in the new rescheduled timetable (as shown in Figure 10), and trains cannot run through it. To ensure the safety of two successive trains traveling in the same direction, we have set all minimum headways (including AA, AD, DA, and DD headways) to one minute. 13 train services before the disruption are canceled in the rescheduled timetable to meet headway constraints with other train services. That is, if these canceled train services were activated, the headway constraints would be violated. As a result, the unexpected disruption would result in train service cancellations before it occurred.

To avoid the conflict between train services and the spatio-temporal disruption area, train services have to be rescheduled to turn around at terminal stations of the disruption area. As shown by Figure 10, In the positive direction, 31 (of 58) train services have been rescheduled. In the meanwhile, 29 (of 60) negative direction train services have been rescheduled. These rescheduled train services are truncated as the blockage of disruption. For the positive direction train services, they have to turn around at FTSR station; while, for the negative direction train services, they turn around at MM station. Furthermore, it can be seen that no train services turn around after the disruption, and these turnaround operations are executed only before the disruption has ended. Therefore, the unexpected disruption would result in turnaround operations before the disruption has ended.

The unexpected disruption would result in a short recovery period after it has ended. During this period, the transport capacity is imbalanced. For the positive direction train services, the recovery time is 17 minutes, whereas the recovery time for negative direction train services is 22.5 minutes. The duration of the recovery period depends on the first train service after the disruption.

Statistical analysis shows that 61.9% of train services in the normal timetable have been rescheduled or canceled, while the disruption time occupancy is 46.2%. More effect on the normal timetable might be caused while the disruption area lies in the middle position of the normal timetable, this observation can be proved by the sensitive analysis part of this paper. As the directional difference of train services, even although the number of affected train services is similar in both two directions of train services, more disturbances would be caused for the positive direction train services as they have fewer train services. Therefore, the direction with fewer train services would occur more effect while facing with an unexpected disruption.

Refer to caption
Figure 10: Rescheduled timetable

The normal metro timetable has been rescheduled to ensure the safety of trains under the disruption condition, and also the passengers are assigned to this new rescheduled timetable. Note that, passengers boarding these rescheduled train services would accumulate at the terminal stations of the disruption area, if their trip crosses the disruption area, this would bring a high safety risk to FTSR station and MM station. Therefore, response vehicles should be scheduled timely to transport these accumulated passengers.

5.1.3 passenger measurement under the rescheduled timetable

Passenger accumulation of each station is an important index in metro disruption management since it reflects the real-time variation of passengers in a station. By observing the real-time passenger accumulation in a station, we can assess the passenger loading pressure of each station. There are 13 metro stations in our basic experiment, and the observation time is set from 8:00 to 9:00 (disruption period). Note that, the accumulated arrival/departure/accumulation flow at a station are calculated by the accumulated form of passenger flow,i.e., variables pApr,t/pDpr,t/pGpr,t\sum\limits_{{\rm{p}}\in\mathbb{P}}A_{{\rm{p}}}^{{\rm{r,t}}}/\sum\limits_{{\rm{p}}\in\mathbb{P}}D_{{\rm{p}}}^{{\rm{r,t}}}/\sum\limits_{{\rm{p}}\in\mathbb{P}}G_{{\rm{p}}}^{{\rm{r,t}}}. The result of passenger accumulation at each station is shown in Figure 11.

As shown in Figure 11 (a), the accumulated arrival curve approximates a linear relationship, while the accumulated departure curve climbs along the accumulated departure curve. The passengers originating from GGZ station can be boarded in time, as adequate train services are departing from GGZ station. Meanwhile, it can be seen that the passengers standed on the platform of GGZ station can be controlled under 500 all the time. In Figure 11 (b), the accumulated arrival curve approximates a linear relationship, and the accumulated departure curve climbs along the accumulated departure curve. Different from GGZ station, the arriving rate of passengers at FTSP station increase suddenly after 8:38, and it can also be met by our train services. The number of passengers standed on the platform of GGZ station and FTSP station can be controlled under 500 all the time, which is acceptable by metro managers.

The FTSR station, being the first terminal station of the disruption area in the positive direction, has a different accumulation tendency, as shown in Figure 11 (d). There are no positive direction train services departing from FTSR station; all positive direction train services finish their tasks at FTSR station, while a new negative direction train service departs from FTSR station. Thus, the newly activated turnaround train service will serve passenger demand in the negative direction; however, passengers originating from the FTSR will still have to wait in this station. Furthermore, transfer passengers wishing to transfer from the FTSR station to other stations in the positive direction must wait at the FTSR station. These two sorts of stranded passengers have caused the FTSR station’s passenger accumulation to significantly expand. However, it is not worried that the response vehicles would serve the stranded passengers in time.

Refer to caption
Figure 11: Passenger accumulation at each station

Figure 11 (e) depicts the passenger accumulation at closed stations, where the accumulation of passenger flows equals zero because these stations are closed and no passengers or trains arrive.

The passenger accumulation at MS-1 stations has been depicted in Figure 11 (a)-(e). Similarly, the passenger accumulation at MS-2 stations follows a similar pattern as that of MS-1 stations. The accumulated arrival curve approximates a linear relationship, as shown by the passenger accumulation at TJS station in Figure 11 (f), while the accumulated departure curve climbs along the accumulated arrival curve. Passengers traveling in the negative direction tend to gather at station MM. There are two sorts of passengers accumulating at MM station: passengers who originate at MM station and transfer passengers who travel from MM station to other stations. It should be noted that the response vehicles would serve the transfer passenger flows.

In Figure 11 (g)-(i), the passenger accumulation at stations of MS-2 (except for the terminal station of the disruption area) has been demonstrated. The accumulated arrival curve of these two stations approximates a linear relationship, while the accumulated departure curve climbs along the arrival curve. It is obvious that the passengers departing from these three stations will be picked up in time. Passenger accumulation at each station can be controlled within an acceptable range.

Refer to caption
Figure 12: Average arrival number & waiting time of passengers at each station

The average waiting time and passenger arrival are depicted in Figure 12. The bar chart depicts the number of passengers arriving at each stop. It can be seen that the FTSR and MM stations have the highest average number of arriving passengers. These two stations’ platforms must service more than 300 people per minute. There is also no passenger demand from FTES to BJW because these five stations are blocked during the disruption period. Furthermore, the average number of people coming in MS-1 is larger than in MS-2, indicating that MS-1 is under greater passenger pressure. The line chart depicts the average time passengers spend waiting at each station. Passengers’ average waiting time is greatest at FTSR and MM stations, with values greater than 30 minutes. This is because some passengers departing from these two stations must wait until the disruption is over if no response vehicles arrive. Furthermore, the average wait time at other open stations is less than 3 minutes, which is consistent with train service departure frequency. This results show that the new rescheduled timetable can provide passengers with an efficient mode of transportation, and the passengers will be picked up in time. As a result, passengers stranded at FTSR and MM stations would have a shorter wait if we offered timely response vehicle service, and other passengers would only have to wait 2 minutes before boarding a train. The impact of disruption can be mitigated by coordinating the optimization of metro and response vehicles.

Refer to caption
Figure 13: cumulative arrive curves of response vehicles

5.1.4 scheduling of response vehicles

Fig 13 (a) and Fig 13 (b) depict the cumulative arrival curves in two directions (i.e., positive direction and negative direction). The cumulative curves show a step-by-step change because the response vehicles are scheduled at fixed time intervals of 5 minutes. We can obtain the departure sequence and fleet size of response vehicles, which are combined with a space-time diagram to provide real-time guidance.

The network clearance time (NCT) is made up of two components: path holding time and path travel time. For example, the larger the NCT without considering dynamic traffic, the farther the station is from the origin station. However, the NCT of S4-S7 and S4-S8 is quite similar because S8 receives more response vehicles than S7. The NCT gap between S10-S5 and S10-S4 is 1 minute in the direction of S4, whereas the corresponding fleet size gap is 84 vehicles. The slope of the cumulative arrival curves at station S4 is greater becausethe shorter routes are prioritized for the fleets reaching station S4.

Table 3: Results of fleet size and NCT for all OD pairs
OD pair Number of vehicles NCT of response vehicles (min)
S4-S5 36 32.67
S4-S6 92 53.67
S4-S7 62 60.00
S4-S8 93 60.33
S4-S9 94 61.33
S4-S10 144 63.67
S10-S9 71 47.33
S10-S8 72 59.33
S10-S7 51 55
S10-S6 72 61.33
S10-S5 26 57
S10-S4 110 58

The results of fleet size and network clearance time for various OD pairs are summarized in Table 3. The maximum network clearance time provides a lower time limit for temporary exclusive lanes. The exclusive lanes are maintained in this case for at least 63.67 minutes, which can be used as the time threshold for designating exclusive lanes for response vehicles.

Refer to caption
Figure 14: Comparison of total travel time of dynamic response vehicles and fixed shortest path
Refer to caption
Figure 15: Comparison NCT of dynamic response vehicles and fixed shortest path

To compare the transport efficiency of response vehicles, the total travel time of the response vehicle is compared to the shortest path scheme. The shortest path scheme sets fixed routes with the shortest distance between two stations. In this case, the shortest route is (1, 5, 9, 10, 14, 19, 20, 23, 24, 29, 30, 32, 36, 37), and vehicles are unable to change routes. The results of the response vehicles and shortest path schemes are shown in Figure 14, where the TTT using the response vehicles scheme is 7% lower than the fixed shortest path scheme. However, as illustrated in Fig 15 (a)-(b), the NCT of different OD pairs may be greater than the fixed shortest path. Because the goal of scheduling response vehicles is to reduce total travel time for all vehicles and the NCT is determined by the capacity entering the destination station, some vehicles may stay at their original stations to avoid congestion and increase system costs.

Refer to caption
Figure 16: Number of rescheduled train services sensitive to disruption period

5.2 Sensitive analysis

5.2.1 timetable rescheduling sensitive to the disruption

To investigate the phenomenon throughout different disruption periods, the disruption area is set from the FTSR station to the MM station, with a one-hour duration. Figure 16 depicts the sensitive analysis of the disruption period on the normal timetable rescheduling. Apart from the disruption period of 6:00–7:00, it can be seen that the number of rescheduled train services is greater than the number of normal train services. Early train services would be less affected by the disruption since they would have a higher chance of avoiding the spatio-temporal disruption area. Furthermore, we can see that during other disruption periods, the disruption may not only affect normal train services during this disruption period, but also train services later in the period. This observation reflects the spread of disruptions to normal train services.

Refer to caption
Figure 17: Number of rescheduled train services sensitive to disruption area

Furthermore, we have chosen two typical disruption periods as our focused disruption periods: peak hour (8:00–9:00 a.m.) and off-peak hour (10:00–11:00 a.m.). The sensitive analysis of the disruption period on the normal timetable rescheduling has been depicted in Figure 17. The number of rescheduled train services grows as the number of disrupted stations increases. Moreover, during the peak hour disruption period (see Figure 17 (a)), more train services are rescheduled in the metro line’s central area. For example, if the number of stations in the disruption area is fixed at three, the number of rescheduled train services in the disruption area from QLZ to LLQ has the greatest value, and this value decreases when the disruption area is closed to the metro line’s terminal stations. During the off-peak hour disruption period (see Figure refsensitive area2 (b), more train services are rescheduled in terminal stations.

5.2.2 passenger accumulation sensitive to the disruption

Apart from the normal metro timetable, the sensitive analysis of the disruption on passenger accumulation is also crucial in metro disruption management. Due to the time-varying passenger demands at different stations, we have set the disruption area from FTSR station to MM station, and the disruption period is one hour. As a result, the sensitive analysis of the disruption period on passenger accumulation is depicted in Figure 18.

Refer to caption
Figure 18: Passenger flow sensitive to disruption period

Figure 18 shows that the total number of accumulated passengers is higher before 9:00. This is due to the fact that passenger demand is usually high during the normal timetable, causing the passenger accumulation to be significantly higher during the disruption period. When an unexpected disruption occurs before 9:00 a.m., the metro manager should pay more attention. Furthermore, the average waiting time at both the FTSR station and MM station is around 30 minutes, whereas at other stations it is less than 3 minutes. This is due to the fact that passengers stranded at these two terminals will not be able to board any transportation means until the disruption is over. As a result, the response vehicles must arrive in time, or passengers may be left waiting for a long period of time on the platforms of the FTSR and MM stations.

6 Conclusion

Metro disruption management is currently a popular topic in metro research. In this study, we developed a two-stage optimization structure to optimize both the train timetable and response vehicle. To begin, the train schedule was adjusted to prevent conflict with the disruption area. Second, the accumulated passengers was converted into a demand for response vehicles. We used dynamic traffic assignment to simulate and optimize the scheduling of response vehicles. Moreover, if no additional train rescheduling strategies are used, this study can be viewed as a benchmark.

This paper can be expanded in several ways. First, this paper only reschedules the train services to avoid their conflicts with disruptions. Other train service rescheduling strategies are also possible in this paper (like more flexible short-turning, skip-stopping, etc.). Second, rolling stock circulation is also important in practical operations. Third, apart from the traffic signals discussed in our paper, more complex road conditions should be considered.

Acknowledgements

This research was supported by the National Natural Science Foundation of China (Nos. 72288101, 71971015, 72071014) and the Fundamental Research Funds for the Central Universities (No. 2021PT206). The authors thank Su Guanghui and Sun Guofeng for providing valuable advice.

References

  • sin [2021] Singapore eyes (2021). URL: https://www.163.com/dy/article/G66KO3C305148HD5.html.
  • Ben-Tal et al. [2011] Ben-Tal, A., Chung, B. D., Mandala, S. R., & Yao, T. (2011). Robust optimization for emergency logistics planning: Risk mitigation in humanitarian relief supply chains. Transport. Res. B-Meth., 45, 1177–1189.
  • Bešinović et al. [2021] Bešinović, N., Wang, Y., Zhu, S., Quaglietta, E., Tang, T., & Goverde, R. M. (2021). A matheuristic for the integrated disruption management of traffic, passengers and stations in urban railway lines. IEEE Trans. Intell. Transp. Syst., .
  • Binder et al. [2017] Binder, S., Maknoon, Y., & Bierlaire, M. (2017). The multi-objective railway timetable rescheduling problem. Transport. Res. C-Emer., 78, 78–94.
  • Bueno-Cadena et al. [2020] Bueno-Cadena, C. E., Munoz, J. C., & Tirachini, A. (2020). An analytical model for controlling disruptions on a metro line. Transport. Res. C-Emer., 117, 102669.
  • Cacchiani et al. [2014] 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. Transport. Res. B-Meth., 63, 15–37.
  • Carey & Watling [2012] Carey, M., & Watling, D. (2012). Dynamic traffic assignment approximating the kinematic wave model: System optimum, marginal costs, externalities and tolls. Transport. Res. B-Meth., 46, 634–648.
  • Chiu et al. [2007] Chiu, Y. C., Zheng, H., Villalobos, J., & Gautam, B. (2007). Modeling no-notice mass evacuation using a dynamic traffic flow optimization model. Iie Transactions, 39, 83–94.
  • Daganzo [2009] Daganzo, C. (2009). A headway-based approach to eliminate bus bunching: Systematic analysis and comparisons. Transport. Res. B-Meth., 43, 913–921.
  • Daganzo [1994] Daganzo, C. F. (1994). The cell transmission model: A dynamic representation of highway traffic consistent with the hydrodynamic theory. Transport. Res. B-Meth., 28, 269–287.
  • Daganzo [1995] Daganzo, C. F. (1995). The cell transmission model, part ii: Network traffic. Transport. Res. B-Meth., 29, 79–93.
  • Daganzo & Pilachowski [2011] Daganzo, C. F., & Pilachowski, J. (2011). Reducing bunching with bus-to-bus cooperation. Transport. Res. B-Meth., 45, 267–277.
  • Delgado et al. [2012] Delgado, F., Munoz, J. C., & Giesen, R. (2012). How much can holding and/or limiting boarding improve transit performance? Transport. Res. B-Meth., 46, 1202–1217.
  • Dou et al. [2019] Dou, X., Wang, H., & Meng, Q. (2019). Parallel shuttle bus service design for planned mass rapid transit shutdown: The singapore experience. Transport. Res. C-Emer., 108, 340–356.
  • Gao et al. [2016] Gao, Y., Kroon, L., Schmidt, M., & Yang, L. (2016). Rescheduling a metro line in an over-crowded situation after disruptions. Transport. Res. B-Meth., 93, 425–449.
  • Ghaemi et al. [2017] Ghaemi, N., Cats, O., & Goverde, R. M. (2017). A microscopic model for optimal train short-turnings during complete blockages. Transport. Res. B-Meth., 105, 423–437.
  • Ghaemi et al. [2018a] Ghaemi, N., Cats, O., & Goverde, R. M. (2018a). Macroscopic multiple-station short-turning model in case of complete railway blockages. Transport. Res. C-Emer., 89, 113–132.
  • Ghaemi et al. [2018b] Ghaemi, N., Zilko, A. A., Fei, Y., Cats, O., Kurowicka, D., & Goverde, R. (2018b). Impact of railway disruption predictions and rescheduling on passenger delays. J. Rail Transport Planning & Management, .
  • Golightly & Dadashi [2017] Golightly, D., & Dadashi, N. (2017). The characteristics of railway service disruption: implications for disruption management. Ergonomics, 60, 307–320.
  • Gu et al. [2018] Gu, W., Yu, J., Ji, Y., Zheng, Y., & Zhang, H. M. (2018). Plan-based flexible bus bridging operation strategy. Transport. Res. C-Emer., 91, 209–229.
  • Guo et al. [2019] Guo, X., Wu, J., Zhou, J., Yang, X., Wu, D., & Gao, Z. (2019). First-train timing synchronisation using multi-objective optimisation in urban transit networks. Int. J. Prod. Res., 57, 3522–3537.
  • He & Peeta [2014] He, X., & Peeta, S. (2014). Dynamic resource allocation problem for transportation network evacuation. Net. Spa. Eco., 14, 505–530.
  • Hua & Ong [2018] Hua, W., & Ong, G. P. (2018). Effect of information contagion during train service disruption for an integrated rail-bus transit system. Public Transport, 10, 571–594.
  • Huang et al. [2020] Huang, Y., Mannino, C., Yang, L., & Tang, T. (2020). Coupling time-indexed and big-m formulations for real-time train scheduling during metro service disruptions. Transport. Res. B-Meth., 133, 38–61.
  • Evelien van der Hurk et al. [2016] Evelien van der Hurk, E., Koutsopoulos, H. N., Wilson, N., Kroon, L. G., & Maróti, G. (2016). Shuttle planning for link closures in urban public transport networks. Transport. Sci., 50, 947–965.
  • Jespersen-Groth et al. [2009] Jespersen-Groth, J., Potthoff, D., Clausen, J., Huisman, D., Kroon, L., Maróti, G., & Nielsen, M. N. (2009). Disruption management in passenger railway transportation, . (pp. 399–421).
  • Jiang et al. [2016] Jiang, Y., Szeto, W. Y., Long, J., & Han, K. (2016). Multi-class dynamic traffic assignment with physical queues: intersection-movement-based formulation and paradox. Transportmetrica, 12, 878–908.
  • Jin et al. [2014] Jin, J. G., Tang, L. C., Sun, L., & Lee, D.-H. (2014). Enhancing metro network resilience via localized integration with bus services. Transport. Res. E-Log., 63, 17–30.
  • Jin et al. [2016] Jin, J. G., Teo, K. M., & Odoni, A. R. (2016). Optimizing bus bridging services in response to disruptions of urban transit rail networks. Transport. Sci., 50, 790–804.
  • Kang et al. [2021] Kang, L., Li, H., Sun, H., Wu, J., Cao, Z., & Buhigiro, N. (2021). First train timetabling and bus service bridging in intermodal bus-and-train transit networks. Transport. Res. B-Meth., 149, 443–462.
  • Kang & Meng [2017] Kang, L., & Meng, Q. (2017). Two-phase decomposition method for the last train departure time choice in subway networks. Transport. Res. B-Meth., 104.
  • Ke et al. [2013] Ke, H., Friesz, T. L., & Tao, Y. (2013). A partial differential equation formulation of vickrey’s bottleneck model, part ii: Numerical analysis and computation. Transport. Res. B-Meth., 49, 75–93.
  • Kepaptsoglou et al. [2009] Kepaptsoglou, Konstantinos, & Karlaftis, M. G. (2009). The bus bridging problem in metro operations: conceptual framework, models and algorithms. Public Transp., 1, 275–297.
  • Kimms & Maiwald [2018] Kimms, A., & Maiwald, M. (2018). Bi-objective safe and resilient urban evacuation planning. European Journal of Operational Research, 269, 1122–1136.
  • Levin et al. [2015] Levin, M. W., Pool, M., Owens, T., Juri, N. R., & Travis Waller, S. (2015). Improving the convergence of simulation-based dynamic traffic assignment methodologies. Net. Spa. Eco., 15, 655–676.
  • Liu et al. [2021] Liu, J., Jiang, R., Li, X., Jia, B., Liu, Z., & Bouadi, M. (2021). Lane-based multi-class vehicle collaborative evacuation management. Transportmetrica B: transport dynamics, (pp. 1–23).
  • Louwerse & Huisman [2014] Louwerse, I., & Huisman, D. (2014). Adjusting a railway timetable in case of partial or complete blockades. Euro. J. Oper. Res, 235, 583–593.
  • Luo et al. [2018] Luo, Y., Wang, Y., Cao, F., Su, S., Yin, J., Zhang, M., Tang, T., & Ning, B. (2018). Train rescheduling and circulation planning in case of complete blockade for an urban rail transit line. In: Proceedings of the 97th Annual Meeting of the Transportation Research Board, Washington, DC, .
  • Narayanaswami & Rangaraj [2013] Narayanaswami, S., & Rangaraj, N. (2013). Modelling disruptions and resolving conflicts optimally in a railway schedule. Comput. Ind. Eng., 64, 469–481.
  • Nielsen et al. [2012] Nielsen, L. K., Kroon, L., & Maróti, G. (2012). A rolling horizon approach for disruption management of railway rolling stoc. Euro. J. Oper. Res., 220, 496–509.
  • Peeta & Ziliaskopoulos [2001] Peeta, S., & Ziliaskopoulos, A. K. (2001). Foundations of dynamic traffic assignment: The past, the present and the future. Net. Spa. Eco., 1, 233–265.
  • Pender et al. [2013] Pender, B., Currie, G., Delbosc, A., & Shiwakoti, N. (2013). Disruption recovery in passenger railways: International survey. Transport. res. rec, 2353, 22–32.
  • Petit et al. [2018] Petit, A., Ouyang, Y., & Lei, C. (2018). Dynamic bus substitution strategy for bunching intervention. Transport. Res. B-Meth., 115, 1–16.
  • Pnevmatikou et al. [2015] Pnevmatikou, A. M., Karlaftis, M. G., & Kepaptsoglou, K. (2015). Metro service disruptions: how do people choose to travel? Transportation, 42, 933–949.
  • Sbayti et al. [2007] Sbayti, H., Lu, C.-C., & Mahmassani, H. S. (2007). Efficient implementation of method of successive averages in simulation-based dynamic traffic assignment models for large-scale network applications. Transp. Re. Rec, 2029.
  • Schettini et al. [2022] Schettini, T., Jabali, O., & Malucelli, F. (2022). Demand-driven timetabling for a metro corridor using a short-turning acceleration strategy. Transport. Sci., .
  • Schmidt et al. [2018] Schmidt, M., Kroon, L., Schobel, A., & Bouman, P. (2018). The travelers route choice problem under uncertainty: Dominance relations between strategies. Oper. Res., 58, 247–249.
  • Shafiei et al. [2018] Shafiei, S., Gu, Z., & Saberi, M. (2018). Calibration and validation of a simulation-based dynamic traffic assignment model for a large-scale congested network. Simulation Modelling Practice and Theory, 86, 169–186.
  • Szeto & Lo [2006] Szeto, W., & Lo, H. K. (2006). Dynamic traffic assignment: properties and extensions. Transportmetrica, 2, 31–52.
  • Tan et al. [2020] Tan, Z., Xu, M., Meng, Q., & Li, Z.-C. (2020). Evacuating metro passengers via the urban bus system under uncertain disruption recovery time and heterogeneous risk-taking behaviour. Transport. Res. C-Emer., (p. 102761).
  • Tessitore et al. [2022] Tessitore, M. L., Sama, M., D’Ariano, A., Helouet, L., & Pacciarelli, D. (2022). A simulation-optimization framework for traffic disturbance recovery in metro systems. Transport. Res. C-Emer., 136, 103525.
  • Veelenturf et al. [2016] Veelenturf, L. P., Kidd, M. P., Cacchiani, V., Kroon, L. G., & Toth, P. (2016). A railway timetable rescheduling approach for handling large-scale disruptions. Transport. Sci., 50, 841–862.
  • Wang et al. [2019] Wang, J., Yuan, Z., & Yin, Y. (2019). Optimization of bus bridging service under unexpected metro disruptions with dynamic passenger flows. J. Adv. Transp., 2019.
  • Wang et al. [2014] Wang, Y., Guo, J., Ceder, A. A., Currie, G., Wei, D., & Hao, Y. (2014). Waiting for public transport services: Queueing analysis with balking and reneging behaviors of impatient passengers. Transport. Res. B-Meth., 63, 53–76.
  • Wang et al. [2016] Wang, Y., Yan, X., Zhou, Y., & Zhang, W. (2016). A feeder-bus dispatch planning model for emergency evacuation in urban rail transit corridors. PloS One, 11, e0161644.
  • Wang et al. [2021] Wang, Y., Zhao, K., D’Ariano, A., Niu, R., Li, S., & Luan, X. (2021). Real-time integrated train rescheduling and rolling stock circulation planning for a metro line under disruptions. Transport. Res. B-Meth., 152, 87–117.
  • Xie et al. [2010] Xie, C., Lin, D.-Y., & Travis Waller, S. (2010). A dynamic evacuation network optimization problem with lane reversal and crossing elimination strategies. Transportation Research Part E: Logistics and Transportation Review, 46, 295–316.
  • Xu et al. [2021] Xu, L., Ng, T. S., & Costa, A. (2021). Optimizing disruption tolerance for rail transit networks under uncertainty. Transport. Sci., 55, 1206–1225.
  • Xu et al. [2017] Xu, P., Corman, F., Peng, Q., & Luan, X. (2017). A train rescheduling model integrating speed management during disruptions of high-speed traffic under a quasi-moving block system. Transport. Res. B-Meth., 104, 638–666.
  • Xu et al. [2016] Xu, X., Li, K., & Yang, L. (2016). Rescheduling subway trains by a discrete event model considering service balance performance. Appl. Math. Model., 40, 1446–1466.
  • Yan et al. [2019] Yan, F., Zhang, S., Majumdar, A., Tang, T., & Ma, J. (2019). A failure mapping and genealogical research on metro operational incidents. IEEE Trans. Intell. Transp. Syst., 21, 3551–3560.
  • Yang et al. [2017] Yang, J., Jin, J. G., Wu, J., & Jiang, X. (2017). Optimizing passenger flow control and bus-bridging service for commuting metro lines. Computer-Aided Civil and Infrastructure Engineering, 32, 458–473.
  • Yang et al. [2020] Yang, L., Di, Z., Dessouky, M. M., Gao, Z., & Shi, J. (2020). Collaborative optimization of last-train timetables with accessibility: A space-time network design based approach. Transport. Res. C-Emer., 114, 572–597.
  • Yao et al. [2009] Yao, T., Mandala, S. R., & Chung, B. D. (2009). Evacuation transportation planning under uncertainty: A robust optimization approach. Net. Spa. Eco., 9, 171.
  • Zhan et al. [2021] Zhan, S., Wong, S., Shang, P., Peng, Q., Xie, J., & Lo, S. (2021). Integrated railway timetable rescheduling and dynamic passenger routing during a complete blockage. Transport. Res. B-Meth., 143, 86–123.
  • Zhang & Lo [2018] Zhang, S., & Lo, H. K. (2018). Metro disruption management: Optimal initiation time of substitute bus services under uncertain system recovery time. Transport. Res. C-Emer., 97, 409–427.
  • Zhang & Lo [2020] Zhang, S., & Lo, H. K. (2020). Metro disruption management: Contracting substitute bus service under uncertain system recovery time. Transport. Res. C-Emer., (pp. 98–122).
  • Zhu & Goverde [2020] Zhu, Y., & Goverde, R. M. (2020). Integrated timetable rescheduling and passenger reassignment during railway disruptions. Transport. Res. B-Meth., 140, 282–314.
  • Zhu & Goverde [2019] Zhu, Y., & Goverde, R. M. P. (2019). Dynamic passenger assignment for major railway disruptions considering information interventions. Net. Spa. Eco., 19, 1249–1279.
  • Ziliaskopoulos [2000] Ziliaskopoulos, A. K. (2000). A linear programming model for the single destination system optimum dynamic traffic assignment problem. Transport. Sci., 34, 37–49.
  • Zilko et al. [2016] Zilko, A. A., Kurowicka, D., & Goverde, R. M. (2016). Modeling railway disruption lengths with copula bayesian networks. Transport. Res. C-Emer., 68, 350–368.

Appendix

Appendix A Notations

Table A.1: Notations
Sets and indexes:
\mathbb{R}  Metro station set, indexed by symbol r,i.e., ={1,2,,r,,||}\mathbb{R}=\{1,2,...,\rm{r},...,|\mathbb{R}|\};
O\mathbb{R}_{{\rm{O}}}    Metro station set in the operational area, indexed by symbol r;
O1\mathbb{R}_{{\rm{O}}}^{1}    Metro station set in the MS-1, indexed by symbol r;
O2\mathbb{R}_{{\rm{O}}}^{2}    Operational metro station in the MS-2, indexed by symbol r;
D\mathbb{R}_{{\rm{D}}}    Metro station set in disruption area, indexed by symbol r;
T1\mathbb{R}_{{\rm{T}}}^{1}    First terminal station set of the disruption area in the positive direction, indexed by symbol r;
T2\mathbb{R}_{{\rm{T}}}^{2}    First terminal station set of the disruption area in the negative direction, indexed by symbol r;
\mathbb{P}  Passenger group set, indexed by symbol p,i.e., ={1,2,,p,,||}\mathbb{P}=\{1,2,...,\rm{p},...,|\mathbb{P}|\};
𝕌\mathbb{U}    Train service in the normal timetable, indexed by symbol u,v,i.e., 𝕌={1,2,,u,,v,|𝕌|}\mathbb{U}=\{1,2,...,\rm{u},...,\rm{v},...|\mathbb{U}|\};
𝕌D\mathbb{U}_{{\rm{D}}}    Disrupted train service set during disruption period, indexed by symbol u,v,i.e., 𝕌={1,2,,u,,v,|𝕌D|}\mathbb{U}=\{1,2,...,\rm{u},...,\rm{v},...|\mathbb{U}_{{\rm{D}}}|\};
𝕌A\mathbb{U}_{{\rm{A}}}   Train service set after disruption period, indexed by symbol u,v;
𝕌B\mathbb{U}_{{\rm{B}}}   Train service set before disruption period, indexed by symbol u,v;
𝕋\mathbb{T}     Discrete time set, indexed by symbol t,i.e., 𝕋={1,,t,,|𝕋|}\mathbb{T}=\{1,...,\rm{t},...,|\mathbb{T}|\};
𝕋D\mathbb{T}_{\rm{D}}     Discrete time set of disruption period, indexed by symbol t;
𝔾\mathbb{G}  The cell-based evacuation network, 𝔾=(,)\mathbb{G}=(\mathbb{C},\mathbb{H});
\mathbb{C}  Set of cells, indexed by symbol i,i.e.,={1,,i,,||}\mathbb{C}=\{1,...,\rm{i},...,|\mathbb{C}|\};
R\mathbb{C}_{{\rm{R}}}    Set of source cells;
S\mathbb{C}_{{\rm{S}}}    Set of sink cells;
\mathbb{H}  Set of intersections, indexed by symbol h,i.e., ={1,,h,,||}\mathbb{H}=\{1,...,{\rm{h}},...,|\mathbb{H}|\};
Γ(i)\Gamma({\rm{i}})  Set of receiving vehicles from upstream cell, indexed by symbol k;
Γ(i)\Gamma^{-}({\rm{i}})  Set of sending vehicles to downstream cell, indexed by symbol j;
𝕄\mathbb{M}   Set of different flow directions within each cell, indexed by m, i.e., 𝕄={1,2}\mathbb{M}=\{1,2\};
𝕋R\mathbb{T}_{\rm{R}}     Discrete time set of disruption period of response vehicle, indexed by symbol t,i.e., 𝕋R={0,,t,,|𝕋R|}\mathbb{T}_{\rm{R}}=\{0,...,{\rm{t}},...,|\mathbb{T}_{\rm{R}}|\};
𝕋~R\mathbb{\tilde{T}}_{{\rm{R}}}(t)   The set of discrete time of time period t, indexed by symbol τ\tau.i.e., 𝕋~R(t)={,τ,}\mathbb{\tilde{T}}_{{\rm{R}}}({\rm{t}})=\{...,\tau,...\}.
Parameters:
(1) parameters related to passenger flow p
o^p/d^p\rm{\hat{o}_{p}/\hat{d}_{p}}   Integer parameter, the origin/destination station of passenger group p;
n^p\rm{\hat{n}_{p}}     Integer parameter, the number of passenger group p;
t^p\rm{\hat{t}_{p}}      Real parameter, the arrival time of passenger group p at its origin station o^p\rm{\hat{o}_{p}};
f^p\rm{\hat{f}_{p}}      Binary parameter, wether the travel direction of passenger group p is positive, f^p=1\rm{\hat{f}_{p}}=1 if it is, and 0 otherwise;
o~p/d~p\rm{\tilde{o}_{p}/\tilde{d}_{p}}   Integer parameter, the transferred origin/destination station of passenger group p;
φpu,r\varphi_{{\rm{p}}}^{{\rm{u,r}}}     Binary parameter, wether passenger flow p occupies seats at station r by taking train service u, wether φpu,r=1\varphi_{{\rm{p}}}^{{\rm{u,r}}}=1 if it is,
    and 0 otherwise;
w˘pu\breve{{\rm{w}}}_{{\rm{p}}}^{{\rm{u}}}     Integer parameter, the waiting time if passenger flow p takes the train service u;
w^u,p{\rm{\hat{w}_{u,p}}}  Binary parameter, wether train service u departures from o^p\rm{\hat{o}_{p}}, w^u,p=1{\rm{\hat{w}_{u,p}}}=1 if it is, and 0 otherwise;
w~u,p{\rm{\tilde{w}_{u,p}}}  Binary parameter, wether arrival time of train service u at o^p\rm{\hat{o}_{p}} is greater than t^p\rm{\hat{t}_{p}}, w~u,p=1{\rm{\tilde{w}_{u,p}}}=1 if it is, and 0 otherwise;
f~u,p{\tilde{\rm{f}}_{\rm{u,p}}}    Binary parameter, wether the direction of train service u and passenger flow p are same. f~u,p=1{\tilde{\rm{f}}_{\rm{u,p}}}=1 if they are, and 0 otherwise;
θ~pt,r\tilde{\theta}_{{\rm{p}}}^{{\rm{t,r}}}   Binary parameter, wether passenger flow p originates from station r at time t.i.e., θ~pt,r=1\tilde{\theta}_{{\rm{p}}}^{{\rm{t,r}}}=1 if it is, and 0 otherwise;
ϑ~pt,r\tilde{\vartheta}_{{\rm{p}}}^{{\rm{t,r}}}   Binary parameter, wether passenger flow p has arrived at station r at time t.i.e., ϑ~pt,r=1\tilde{\vartheta}_{{\rm{p}}}^{{\rm{t,r}}}=1 if it does, and 0 otherwise;
θˇp,ut,r\check{\theta}_{{\rm{p,u}}}^{{\rm{t,r}}}  Binary parameter, wether passenger flow p takes train service u, and demands transferring at station r at time t.i.e., θˇp,ut,r=1\check{\theta}_{{\rm{p,u}}}^{{\rm{t,r}}}=1
    if it is, and 0 otherwise;
ϑˇp,ut,r\check{\vartheta}_{{\rm{p,u}}}^{{\rm{t,r}}}  Binary parameter, wether passenger flow p of taking train service u has arrived at station r at time t.i.e., ϑˇp,ut,r=1\check{\vartheta}_{{\rm{p,u}}}^{{\rm{t,r}}}=1 if it is,
    and 0 otherwise;
ϑ^u,pr,t\hat{\vartheta}_{{\rm{u,p}}}^{{\rm{r,t}}}  Binary parameter, wether passenger flow p of taking train service u has departed from station r at time t.i.e., ϑ^u,pr,t=1\hat{\vartheta}_{{\rm{u,p}}}^{{\rm{r,t}}}=1 if it is,
    and 0 otherwise;
ξp1/ξp2\xi_{\rm{p}}^{1}/\xi_{\rm{p}}^{2}  Binary parameter, wether the origin/destination of passenger flow p should be transferred;
(2) parameters related to train service
fu{\rm{f_{u}}}      Binary parameter, wether the travel direction of train service u is positive, fu=1{\rm{f_{u}}}=1 if it is, and 0 otherwise;
tu,ra{\rm{t}}_{{\rm{u,r}}}^{a}/tu,rd{\rm{t}}_{{\rm{u,r}}}^{d}   Real parameter, the arrival/departure time of train service u at station r in original normal timetable;
Θu\Theta_{{\rm{u}}}    Binary parameter, wether train service u conflicts with spatio-temporal disruption area, Θu=1\Theta_{{\rm{u}}}=1 if it is, and 0 otherwise;
δu,vr\delta_{{\rm{u,v}}}^{{\rm{r}}}  Binary parameter, wether train service v is the turnaround train service of u at station r. δu,vr=1\delta_{{\rm{u,v}}}^{{\rm{r}}}=1 if it is, and 0 otherwise;
θu,vr\theta_{{\rm{u,v}}}^{{\rm{r}}}  Binary parameter, wether train service u and v is conflicted at station r. θu,vr=1\theta_{{\rm{u,v}}}^{{\rm{r}}}=1 if it is, and 0 otherwise;
C¯u{\rm{\bar{C}_{u}}}    Integer parameter, the capacity of train service u;
(2) parameters related to response vehicle
CR{\rm{C_{R}}}  Maximum passenger holding capacity of response vehicles;
Ni,mt{\rm{N_{i,m}^{t}}}   Maximum number of response vehicles that can be accommodated in cell i at time t;
αt\alpha_{\rm{t}}   Length of time step t during disruption period;
δ~i,rm,p\tilde{\delta}_{{\rm{i,r}}}^{{\rm{m,p}}}   Binary parameter, wether the passenger flow p at station r matches with the transportation task (OD pair) of class-m response
    vehicles departing from cell i, δ~i,rm,p=1\tilde{\delta}_{{\rm{i,r}}}^{{\rm{m,p}}}=1 if it is, and 0 otherwise;
di,mt{\rm{d}}_{{\rm{i,m}}}^{{\rm{t}}}   Integer parameter, the number of m-class response vehicles originating from cell i at time t;
Qi,m{\rm{Q_{i,m}}}   Integer parameter, maximum number of response vehicles that can flow into or out of cell i at time t;
vm{{\rm{v_{m}}}}  Real parameter, free-flow velocity of m-class response vehicles;
wm{{\rm{w_{m}}}}  Real parameter, backward shock wave propagation speed of response vehicles;
(4) other parameters
M  very big number;
sbegin/send{\rm{{s}_{begin}}}/{\rm{{s}_{end}}} Begin/end station of disruption area;
τbegin/τend\tau_{{\rm{begin}}}/\tau_{{\rm{end}}} Begin/end time of disruption period;
r1/r2{\rm{r}_{1}^{*}}/{\rm{r}_{2}^{*}} Terminal stations of disruption area;
Decision variables:
(1)variables related to train service u
aua_{{\rm{u}}}   Binary variable, wether train service u is activated;
su,rs_{{\rm{u,r}}}     Binary variable, wether station r is visited by train service u;
tu,ra/tu,rdt_{{\rm{u,r}}}^{a}/t_{{\rm{u,r}}}^{d}  Real variable, the arrival/departure time of train service u at station r;
CurC_{{\rm{u}}}^{{\rm{r}}}      Integer variable, the number of passengers in train service u before it departures from station ;
(2)variables related to passenger p
xpux_{{\rm{p}}}^{{\rm{u}}}   Integer variable, the number of passenger flow p taking train service u;
xpx_{{\rm{p}}}   Integer variable, the number of passenger flow p who has not boarded any train;
𝒢pr,t\mathscr{G}_{{\rm{p}}}^{{\rm{r,t}}}   Integer variable, instantaneous accumulation flow p of station r at time t;
Apr,tA_{{\rm{p}}}^{{\rm{r,t}}}    Integer variable, accumulated arrival flow p of station r at time t;
Dpr,tD_{{\rm{p}}}^{{\rm{r,t}}}    Integer variable, accumulated departure flow p of station r at time t;
Gpr,tG_{{\rm{p}}}^{{\rm{r,t}}}    Integer variable, accumulated stranded flow p of station r at time t;
(3)variables related to response vehicles
yi,mty_{{\rm{i,m}}}^{{\rm{t}}}    Real variable, the number of response vehicles on cell i at time t;
zi,j,mtz_{{\rm{i,j,m}}}^{{\rm{t}}}    Real variable, the number of inflow response vehicles from cell i to cell i+1 at a time step [t,t+1);

Appendix B Definitions

Spatio-temporal disruption area is a rectangle area in the train timetable, in which the train service can not go through. As shown in Figure B.1, the spatio-temporal disruption area is bounded by the convex hull of four disruption nodes. i.e.,(sbegin,τbegin{\rm{{s}_{begin},\tau_{begin}}}), (send,τbegin{\rm{{s}_{end},\tau_{begin}}}),(send,τend{\rm{{s}_{end},\tau_{end}}}),(send,τend{\rm{{s}_{end},\tau_{end}}}). sbegin{\rm{{s}_{begin}}} and send{\rm{{s}_{end}}} are the terminal stations of disruption area, and τbegin/τend\tau_{{\rm{begin}}}/\tau_{{\rm{end}}} is the begin/end time of disruption. There are three train services u1,u2, and u3 representing the train service before/during/after the disruption. Train services u1 and u3 would not travel past the spatio-temporal disruption area, while train service u2 has to stop at station sbegin{\rm{s}_{begin}} as it will run through the spatio-temporal disruption area. Therefore, train service u1 and u3 have not to be rescheduled, as it does not conflict with the spatio-temporal disruption area; however, reschedule strategies should be executed on train service u2 to run into the spatio-temporal disruption area.

Refer to caption
Figure B.1: spatio-temporal disruption area
Refer to caption
Figure B.2: Relation between train service and spatio-temporal disruption unit

Spatio-temporal disruption unit is a rectangle area bounded by disrupted metro line track and disruption period 𝕋D\mathbb{T}_{{\rm{D}}}. As shown in Figure B.2 (a)-B.2 (b), two instances have been illustrated to reveal the possible relationships between train services and spatio-temporal disruption units. Five typical train services of positive direction have traveled through line section (r, r+1), of which three train services(train service u2,u3,u4) conflict with spatio-temporal disruption unit while two train services(train service u1,u5) otherwise. By the observation of these five train services, can we see that the train service u conflicts with the spatio-temporal disruption unit if its departure/arrival time at station r/r+1 is in the range of disruption period 𝕋D\mathbb{T}_{{\rm{D}}}. Similar conclusions can also be obtained from another five train services in the negative direction (see Figure B.2 (b)).Note that, the spatio-temporal disruption area is compromised of several spatio-temporal disruption units. If we want to judge whether a train service conflicts with the spatio-temporal disruption area, we have to check whether this train service conflicts with the spatio-temporal disruption units of this area one by one. Given the normal timetable and disruption information (sbegin{\rm{s_{begin}}},send{\rm{s_{end}}},τbegin\tau_{begin},τend{\rm{\tau_{end}}}), the classification of train services can be obtained by C.1-C.2. C.1 presents the classification of train services, and C.2 gives the method of determining whether a train service conflicts with spatio-temporal disruption units. Additionally, the parameter Θu\Theta_{{\rm{u}}} can be determined by these two algorithms.

Appendix C Algorithms

C.1 Classification of train services

Table C.1: Algorithm 1: Classification of train services
Algorithm 1: Classification of train services
00: (Initialization) 𝕌B\mathbb{U}_{{\rm{B}}}, 𝕌D\mathbb{U}_{{\rm{D}}}, 𝕌A:=Φ\mathbb{U}_{{\rm{A}}}:=\Phi
01: For u 𝕌\in\mathbb{U}
02:  If train service u does not conflict with spatio-temporal disruption area( judge by Algorithm 2.)
03:   If the arrival/departure time of train service u at its origin station tu,ra>τend||tu,rd>τendt_{{\rm{u,r}}}^{a}>\tau_{\rm{end}}||t_{{\rm{u,r}}}^{d}>\tau_{\rm{end}}
04:    𝕌A\mathbb{U}_{{\rm{A}}}\leftarrow u;
05:   Else if the arrival/departure time of train service u at its origin station tu,ra<τbegin||tu,rd<τbegint_{{\rm{u,r}}}^{a}<\tau_{\rm{begin}}||t_{{\rm{u,r}}}^{d}<\tau_{\rm{begin}}
06:    𝕌B\mathbb{U}_{{\rm{B}}}\leftarrow u;
07:   Else
08:    𝕌O\mathbb{U}_{{\rm{O}}}\leftarrow u;
09:   End if
10:  Else
11:    𝕌O\mathbb{U}_{{\rm{O}}}\leftarrow u;
11:    Adjust the arrival/departure time of train service u at each station r(r \in\mathbb{R}) tu,ra/tu,rdt_{{\rm{u,r}}}^{a}/t_{{\rm{u,r}}}^{d} by Algorithm 2;
12:  End if
13: End for
14: Output:𝕌B\mathbb{U}_{{\rm{B}}},𝕌O\mathbb{U}_{{\rm{O}}}, 𝕌A\mathbb{U}_{{\rm{A}}};

C.2 Detection of the conflict between a train service and spatio-temporal area

Table C.2: Algorithm 2: Detection of the conflict between a train service and spatio-temporal area
Algorithm 2: Detection of the conflict between a train service and spatio-temporal area
00: Input: train service u and its station arrival/departure time tu,ra/tu,rd{\rm{t}}_{{\rm{u,r}}}^{a}/{\rm{t}}_{{\rm{u,r}}}^{d} in the original normal timetable
01:(Initialization) Θu:=0\Theta_{{\rm{u}}}:=0;
02: For r [sbegin,send]\in[{\rm{{s}_{begin}}},{\rm{{s}_{end}}}]
03:  If tu,ra(τbegin,τend)||tu,rd(τbegin,τend){\rm{t}}_{{\rm{u,r}}}^{a}\in(\tau_{\rm{begin}},\tau_{\rm{end}})||{\rm{t}}_{{\rm{u,r}}}^{d}\in(\tau_{\rm{begin}},\tau_{\rm{end}});
04:   Θu=1\Theta_{{\rm{u}}}=1;
05:  End if
06: End for
07: Output:Θu\Theta_{{\rm{u}}};

Note that, the detection of the conflict between a train service u and spatio-temporal area is judged by the relation between the arrival/departure time of train service u at each station of the disruption area and the disruption period [sbegin,send][{\rm{{s}_{begin}}},{\rm{{s}_{end}}}]. If there is a time belonging to the disruption period, then train service u conflicts with the spatio-temporal area (Θu=1\Theta_{{\rm{u}}}=1), and Θu=0\Theta_{{\rm{u}}}=0 otherwise.

C.3 Dynamic filling algorithm

Table C.3: Algorithm 3: Dynamic filling algorithm
Algorithm 3: Dynamic filling algorithm
00: (Initialization) Let φpu,r\varphi_{{\rm{p}}}^{{\rm{u,r}}} be a ||×|𝕌|×|||\mathbb{P}|\times|\mathbb{U}|\times|\mathbb{R}| zero matrix, and input related parameters.
01: For u 𝕌\in\mathbb{U}
02:  If Θu=1\Theta_{{\rm{u}}}=1
03:   For p \in\mathbb{P}
04:    If f^p=1{\rm{\hat{f}_{p}}}=1
05:     For r=o^p:d^p1{\rm{\hat{o}_{p}}}:{\rm{\hat{d}_{p}}}-1
06:      If r sbegin\neq{\rm{{s}_{begin}}}
07:       φpu,r=1\varphi_{{\rm{p}}}^{{\rm{u,r}}}=1;
08:      Else
09:       φpu,r=1\varphi_{{\rm{p}}}^{{\rm{u,r}}}=1, break;
10:      End if
11:     End for
12:    Else
13:     For r=d^p+1:o^p{\rm{\hat{d}_{p}}}+1:{\rm{\hat{o}_{p}}}
14:      If r send\neq{\rm{{s}_{end}}}
15:       φpu,r=1\varphi_{{\rm{p}}}^{{\rm{u,r}}}=1;
16:      Else
17:       φpu,r=1\varphi_{{\rm{p}}}^{{\rm{u,r}}}=1, break;
18:      End if
19:     End for
20:    End if
21:   End for
22:  Else
23:   For p \in\mathbb{P}
24:    If f^p=1{\rm{\hat{f}_{p}}}=1
25:     For r=o^p:d^p1{\rm{\hat{o}_{p}}}:{\rm{\hat{d}_{p}}}-1
26:      φpu,r=1\varphi_{{\rm{p}}}^{{\rm{u,r}}}=1;
27:     End For
28:    Else
29:     For r=d^p+1:o^p{\rm{\hat{d}_{p}}}+1:{\rm{\hat{o}_{p}}}
30:      φpu,r=1\varphi_{{\rm{p}}}^{{\rm{u,r}}}=1;
31:     End for
32:    End If
33:   End for
34:  End if
35: End for
36: Output:φpr\varphi_{{\rm{p}}}^{{\rm{r}}};

Note that, the identification of passenger holding is distinguished by the train service. If the train service u conflicts with the spatio-temporal area, then the value of φpu,r\varphi_{{\rm{p}}}^{{\rm{u,r}}} would be filled by a dynamic filling procedure. that is, the parameter φpu,r\varphi_{{\rm{p}}}^{{\rm{u,r}}} is set to one from his origin station to the terminal station of the disruption area; however, if the train service u does not conflict with spatio-temporal area, then the value of φpu,r\varphi_{{\rm{p}}}^{{\rm{u,r}}} is set to one along the stations from origin station of passenger flow p to station before his destination station.

Appendix D Figures

Refer to caption
Figure D.1: Road network

Appendix E Proofs

E.1 Proof of Remark 1.

We first prove that if M maxp,u𝕌𝕌~{w˘pu}\geq\max\limits_{{\rm{p}\in\mathbb{P}},{\rm{u}}\in\mathbb{U}\cup\mathbb{\tilde{U}}}\{\breve{{\rm{w}}}_{{\rm{p}}}^{{\rm{u}}}\}, then the passengers can be assigned completely. For any passenger flow p (p{\rm{p}\in\mathbb{P}}), if this passenger flow is assigned into a feasible train service u(u𝕌𝕌~{\rm{u}\in\mathbb{U}\cup\mathbb{\tilde{U}}}), then the waiting time of this passenger flow would be z1=w˘puz_{1}=\breve{{\rm{w}}}_{{\rm{p}}}^{{\rm{u}}}; Otherwise, if it does not be assigned into any trains, then the penalty cost would be z2=Mz_{2}={\rm{M}}. It is obvious that z1z2z_{1}\leq z_{2} if M maxp,u𝕌𝕌~{w˘pu}\geq\max\limits_{{\rm{p}\in\mathbb{P}},{\rm{u}}\in\mathbb{U}\cup\mathbb{\tilde{U}}}\{\breve{{\rm{w}}}_{{\rm{p}}}^{{\rm{u}}}\}. Therefore, to minimize the objective function, the passengers are ought to be assigned to its feasible train services.

Secondly, we give an example to prove that if M¡maxp,u𝕌𝕌~{w˘pu}\max\limits_{{\rm{p}\in\mathbb{P}},{\rm{u}}\in\mathbb{U}\cup\mathbb{\tilde{U}}}\{\breve{{\rm{w}}}_{{\rm{p}}}^{{\rm{u}}}\}, then the passengers would not be assigned completely. For any passenger flow p(p{\rm{p}\in\mathbb{P}}), let M maxu𝕌𝕌~{w˘pu}\leq\max\limits_{{\rm{u}}\in\mathbb{U}\cup\mathbb{\tilde{U}}}\{\breve{{\rm{w}}}_{{\rm{p}}}^{{\rm{u}}}\}, then the passenger group p is better to be stranded, as the stranded cost(M) is less than the waiting time of any train service u(w˘pu\breve{{\rm{w}}}_{{\rm{p}}}^{{\rm{u}}}).Q.E.D.