Adjusting Train Timetables Based on Passenger Flow for Cross-Line Trains

Abstract

Urban rail transit becomes increasingly convenient for passengers by networking single lines. The urban rail transit network with cross-line trains has different characteristics from the traditional network. The trains can run to different lines at the crossing station, and the operation delay may be spread to different lines because of the operation schedule. A model for adjusting the running delay of cross-line trains is proposed in this paper. The optimization objective is to minimize the total delay time and the number of stranded passengers. In this paper, different scales of delay are analyzed and the operation order of the trains is allowed to be changed at the crossing station. Case simulations achieve good optimization results on the total delay time and the number of stranded passengers. Optimization diagrams are given under different strategies. The model and methodologies are also applied to Beijing Metro Line 13, and good simulation results are achieved for different scales of delay.

In the past decades, the rapid development of urban rail transit has played an important role in daily transportation. It has led to further increases in the passenger demand. With the fast growth in passenger flow, the existing urban rail transit operation has been unable to meet the transportation demand. In particular, in the case of cross-line trains operation, the problem becomes more complicated. With the extension of the rail transit network, delays caused by small disturbances to the timetable may have a much more significant effect through the cross-line. Therefore, it is crucial to study the delay adjustment of trains on such a network.

To solve the problem, researchers intend to approach the problem from different perspectives. Some researchers have investigated the adjustment of single-line delays. Louwersea and Huismanab ( 1 ) presented integer programming formulations based on event-activity networks for situations of a partial and a complete blockade. Yu et al. ( 2 ) established a delay propagation mechanism model for high-speed train operation based on the reachable matrix for the train scheduling problem. Dong et al. ( 3 ) proposed a multi-objective delay adjustment model for the delayed train by adjusting the actual stop time of the train. Xie et al. ( 4 ) developed a train timetable and stop plan synchronization optimization model that was passenger and energy-saving oriented. In this model, the objectives were minimized train delay, energy consumption, and travel time of the trains. Lee et al. ( 5 ) put forward a delay prediction model and verified the model through simulation. The problem of train trajectory optimization with general operation constraints and signal constraints was addressed by Wang and Goverde ( 6 ). When the train was delayed, the train’s trajectory was recalculated based on the adjusted schedule to minimize the delay and energy consumption.

Other studies discussed delay adjustments on multiple lines. A set of disruption resolution scenarios to manage seriously disturbed traffic conditions in a large network was investigated by Coman and D’Ariano ( 7 ). The paper considered some methods to solve the delay, such as canceling the train, changing the route, and overrunning, and evaluated each method according to the travel time, train service frequency, and delay propagation. Heilporn et al. ( 8 ) presented two equivalent mixed integer linear programming models for the delay management problem, and solved two models by a branch and cut procedure and by a constraint generation approach, respectively. Cadarso et al. ( 9 ) proposed a two-step approach that combined an integrated optimization model for the timetable and rolling stock with a model of passengers’ behavior. Cavone et al. ( 10 ) presented a self-learning decision making procedure for robust real-time train rescheduling with disturbances. The procedure was applicable to aperiodic timetables of mixed-tracked networks.

Meanwhile, some other researchers tried to alleviate the interference or interruption by adjusting the train stop mode and operation route. In Huang et al. ( 11 ), a nonlinear mixed integer programming model with two different restoration strategies (such as alternating train directions and allowing short turns) was established, with passenger satisfaction and headway deviation as the main optimization objectives. Kang et al. ( 12 ) directed their attention to the adjustment of the last train schedule and put forward a last train adjustment model. The purpose of the scheduling adjustment model was to reduce the deviation between the planned schedule and the adjusted schedule, and minimize the running time and dwell time as much as possible. Canca et al. ( 13 ) proposed a train adjustment model for rail transit to alleviate disturbances. The model generated points and time (such as turn-back point locations, departure and arrival times, and short-turning offsets) to reduce passenger waiting time and maintain a certain quality of service. This paper studied the influence of mediation on interruption adjustment and put forward a rescheduling model for subway lines ( 14 ). The article considered the crossover in the rescheduling process and rescheduled the train diagram under delays ( 15 ).

However, there is little literature on the delay adjustment of an urban rail transit network with cross-line trains. Yang et al. ( 16 ) established an optimization model with the goal of minimizing the total train delay time. Han et al. ( 17 ) studied the planning of a cross-rail high-speed line, and established a planning model aiming at the periodicity of line planning, the number of cross-track high-speed trains, the distance of cross-track trains, and the stops of cross-track trains in operation, while meeting the passenger demand and the constraints of the number of trains available. Yang et al. ( 18 ) propose an integrated optimization with tactical cross-line planning and an operational express train mode to fully utilize line capacities and reduce the total trip time without additional operating costs and investments. To deal with the poor inter-region collaboration of the dispatching work between different regions based on the regional collaboration ideology and multi-objective collaboration ideology, Li ( 19 ) established a train diagram model and a train operation adjustment model, respectively. There are many researches on cross-track adjustment of high-speed railways, but there are few studies on cross-line train adjustment of urban rail transit. The adjustment of train operation under interconnection needs to consider the relationship of trains between different lines, as well as the headway, arrival–departure interval, and so on. Since the delay adjustment of cross-line trains is more complex than single-line adjustment, the impact of passenger flow cannot be ignored.

In this paper, the Adjustment Strategy section puts forward the layout of the urban rail transit network with the crossing station, and two adjustment strategies are given as the stop time adjustment and the departure order adjustment. Corresponding to these two strategies, the optimal model aiming at minimizing the total delay time and the number of stranded passengers is established in the The Model of Delay Adjustment section. The algorithm implemented to solve the optimization model is introduced in the Model Solving section. In the Case Analysis section, the simulation verification of the model is done and the delay adjustment operation diagrams under different targets are analyzed and compared.

Adjustment Strategy

Figure 1 shows a schematic map of an urban rail transit network formed by two lines with two tracks for the cross-line express mode. We use $\mathrm{A}{\left(\mathrm{B}\right)}_i$ to represent the ith station on line A(B). Then, line A and line B include n and m stations, respectively, and ${\mathrm{A}}_x$ and ${\mathrm{B}}_y$ denote the transfer stations between line A and line B. There are three types of train service plans: $I^A$ represents local trains that stop at all stops from station A₁ to station ${\mathrm{A}}_n$ on line A; $I^B$ represents local trains that stop at all stops from station B₁ to station ${\mathrm{B}}_m$ on line B; and $I^k$ represents cross-line trains that stop at a subset of stations from station A₁ to ${\mathrm{A}}_x$ and station ${\mathrm{B}}_y$ to station ${\mathrm{B}}_m$ , where A₁ and ${\mathrm{B}}_m$ are terminal stations at which the cross-line trains turn back on line A and line B, respectively. In this study, A _x and B _y can be integrated into a single station, which we call the crossing station.

Figure 1.

Layout of the urban rail transit network.

There are altogether six routing paths on the network list as follows.

1. Routing 1 (up): The direction from station A₁ to station ${\mathrm{A}}_n$ is defined as the up direction of line A.

2. Routing 2 (down): The direction from station ${\mathrm{A}}_n$ to station ${\mathrm{A}}_1$ is defined as the down direction of line A.

3. Routing 3 (up): The direction from station ${\mathrm{B}}_1$ to station ${\mathrm{B}}_m$ is defined as the up direction of line B.

4. Routing 4 (down): The direction from station ${\mathrm{B}}_m$ to station ${\mathrm{B}}_1$ is defined as the down direction of line B.

5. Routing 5 (up): The direction from station ${\mathrm{A}}_1$ to station ${\mathrm{B}}_m$ is defined as the up direction of the cross-line trains.

6. Routing 6 (down): The direction from station ${\mathrm{B}}_m$ to station ${\mathrm{A}}_1$ is defined as the down direction of the cross-line trains.

The operation of cross-line trains is completed through the crossovers at one end of the platform, as shown in Figure 2. The cross-line trains cross the crossover from the station of line A to the station of line B. They stop normally at the station of the crossing station, but after crossing the crossover, they directly leave the station without stopping again. The network discussed in this paper is a classic example of a cross-line train rail network with crossing-line stations. Different from a network without cross-line trains, two methods can be applied for delay adjustment in such a network. One method is adjusting the train stop time, and the other method is adjusting the running order of the trains.

Figure 2.

Layout of the crossing station.

Adjustment of the Train Stop Time

In the timetable, the planned stop time of the train is greater than the minimum stop time. Therefore, when there is a train delay, the stop time of the train at each station can be adjusted to reduce the train delay gradually. However, the impact on passengers needs to be taken into account when the stop time of each station is adjusted. When the train is delayed, the number of waiting passengers on the platform is certainly more than that of the normal passenger flow. If the stop time of the train at each station is adjusted to the minimum stop time, some passengers will not be able to get on and off the train in time. Therefore, it is necessary to adjust the stop time of the train at each station according to the number of waiting passengers on the platform.

The length of the train stop time is subject to the needs of passengers getting on and off, so the train stop time depends on the passenger volume of the station, the number of train doors, the dredging and management of the station, and so on. The unadjustable time, such as trains’ action time of opening and closing doors, is defined as S $\min$ for all trains at any station of any line. It is found that the stop time is proportional to the number of passengers getting on and off the train, and there is approximately a linear relationship between the passengers on and off the train. The number of people getting on at j station on train i of line $\ell$ is $U_{i,j}^{\ell }$ , whereas the number of passengers getting off at j station on train i of line $\ell$ is ${\mathrm{Dn}}_{i,j}^{\ell }$ . The stop time at j station on train i of line $\ell$ is defined as $S_{i,j}^{\ell }$ . Here, a and b are the time for passengers to get on and off, respectively. Then the stop time of the train at the station can be obtained through Equation 1, where nd is the number of doors:

$$S_{i,j}^{\ell }\ge S_{min}+\frac{a*U_{i,j}^{\ell }+b*{\mathrm{Dn}}_{i,j}^{\ell }}{\mathrm{nd}}$$

(1)

The train affected by the delay may run through some inter-stations sections. After that, the delay may be absorbed and the train will recover to the scheduled timetable when it arrives at some station.

Adjusting the Running Order of Trains

For urban rail transit with a single track, it is impossible to adjust the order of the trains for some large-scale delays. When a train is delayed, the following trains can only wait in order in such networks. However, for urban rail transit with cross-lines, the running order of trains on local lines and cross-lines can be adjusted at crossing stations.

With the planned order, after the cross-line train passes through the crossover from the station ${\mathrm{A}}_x$ to line B, the local-line train on line B leaves from station ${\mathrm{B}}_y$ with the required headway. If there is a delay in the cross-line train and the delay is large, the subsequent train on line B at station ${\mathrm{B}}_y$ will aggravate the impact of the delay. In this situation, the train on line B may need to leave station ${\mathrm{B}}_y$ at the planned time, and the cross-line train waits for departure at station ${\mathrm{A}}_x$ until the departure time meets the required headway of cross-line operation. The order of the cross-line train and local train is changed to minimize the total delay.

The Model of Delay Adjustment

Symbol Definition

To simplify the description of the model, the symbols are first defined in Tables 1 and 2.

Table 1.

Symbols of Parameters for the Mathematical Formulation

Symbol	Description
$L$	Set of urban rail transit lines
$M$	A sufficiently large positive integer
$\ell$	Index of all lines, $\ell$ $\in L$
$p$	Index of the local lines, p $\in L$
$k$	The index of path of the cross-line trains, k $\in L$
$J$	Set of stations
$J^{\ell }$	Set of stations on line $\ell$ , where $|J^{\ell }|$ is the total number of stations on line $\ell$
$j$	Station index, j $\in J$
$I$	Set of trains
$I^{\ell }$	Set of trains on line $\ell$ , where $|I^{\ell }|$ is the total number of trains on line $\ell$
$i$	Train index, i $\in I$
$\mathrm{Tc}$	Passenger capacity of trains
nd	Number of train doors
$R_j^{\ell }$	The minimum running time of a train on line $\ell$ from station j to j+1
$a_{i,j}^{\ell }$	The planned arrival time of train i on line $\ell$ at the station j
$d_{i,j}^{\ell }$	The planned departure time of train $i$ on line $\ell$ at station j
$\mathrm{Td}$	Minimum headway
$\mathrm{Tdf}$	Minimum interval between arrival and departure of sequential trains
$S_{min}$	Minimum dwelling time required because of train door response time, action time, and so on
$\mathrm{Tzz}$	Crossing time from line $\ell$ to line p
$O{D}_{j,k}$	The number of passengers who come in from station j and get off after arriving at station k in a unit time
$P{P}_{j,k}$	The proportion of passengers boarding from station j to station k
$P{r}_j$	Passenger entry rate at station j, unit: person/s
${\omega }_1$ , ${\omega }_2$	The weights of objective functions in the multi-objective function

Table 2.

Decision Variables in the Model

Variable	Definition
$A_{i,j}^{\ell }$	The actual arrival time of train i at station j on line $\ell$
$D_{i,j}^{\ell }$	The actual departure time of train i at station j on line $\ell$
$U_{i,j}^{\ell }$	The number of people getting on train i at station j of line $\ell$
${\mathrm{Dn}}_{i,j}^{\ell }$	The number of people getting off train i at station j of line $\ell$
$F_{i,j}^{\ell }$	The number of passengers on the platform when train i arrives at station j of line $\ell$
$P_{i,j}^{\ell }$	The number of passengers on train i when it arrives at station j of line $\ell$
${\mathrm{FL}}_{i,j}^{\ell }$	The number of passengers stranded on the platform when train i leaves station j of line $\ell$
$S_{i,j}^{\ell }$	The dwelling time of train i at station j on line $\ell$
$x_{i,j}^{\ell }$	Binary variable: if the sum of the number of passengers on board and the number of waiting passengers is less than the train capacity, $x_{i,j}^{\ell }$ = 1; otherwise, $x_{i,j}^{\ell }$ = 0
$y$	Binary variable: if y = 1, the operation sequence of cross-line trains and B-line trains is changed; otherwise, y = 0

Assumption: Cancellation of the train service will not be considered.

Objective Function

In the adjustment methods of cross-line urban rail transit, the goal is to optimize the total delay time of the train operation and the number of passengers stranded on the platform. The total delay of the train operation is Z1, and Z1 is the total difference between the scheduled timetable and actual timetable. It should be larger than 0 and less than a maximum value $Z{1}_{max}$ . The number of passengers stranded on the platform is Z2, and Z2 is the summation of the number of all passengers stranded on the platform. It should be larger than 0 and less than $Z{2}_{max}$ . The maximum numbers $Z{1}_{max}$ and $Z{2}_{max}$ are the values with no adjustment for the delay, and the objective function will be 1 with any weight values of $\omega 1$ and $\omega 2$ . The weight values $\omega 1$ and $\omega 2$ denote the importance of these two terms, and satisfy $0\le \omega 1\le 1$ , $0\le \omega 2\le 1$ , $\omega 1$ + $\omega 2$  = 1.

The objective is as follows:

$$minZ=\omega 1*\frac{Z1}{Z{1}_{max}}+\omega 2*\frac{Z2}{Z{2}_{max}}$$

(2)

$$Z1=\sum _{\ell \in L}\sum _{i=\in I}\sum _{i=\in J}(|A_{i,j}^{\ell }-a_{i,j}^{\ell }|+|D_{i,j}^{\ell }-d_{i,j}^{\ell }|)$$

(3)

$$Z2=\sum _{\ell \in L}\sum _{i=\in I}\sum _{i=\in J}{\mathrm{FL}}_{i,j}^{\ell }$$

(4)

where ${\mathrm{FL}}_{i,j}^{\ell }$ is the number of passengers stranded on the platform when train i leaves station j of line $\ell$ , as follows:

$${\mathrm{FL}}_{i,j}^{\ell }=F_{i,j}^{\ell }-U_{i,j}^{\ell },\forall i\in I^{\ell },\forall j\in J^{\ell },\forall \ell \in L$$

(5)

Here, ${\mathrm{Dn}}_{j,k}^{\ell }$ is the number of people getting off train i at station j of line $\ell$ , as follows:

$$\begin{array}{c}\multicolumn{1}{c}{{\mathrm{Dn}}_{j,k}^{\ell }=\sum _{q=1}^{j}P{P}_{q,j}*U_{i,q}^{\ell },\forall i\in I^{\ell },\forall q\in J^{\ell },}\\ \multicolumn{1}{c}{\forall j\in J^{\ell },\forall k\in J^{\ell },\forall \ell \in L}\end{array}$$

(6)

where $P{P}_{j,k}$ is the proportion of passengers leaving from station j to station k, as follows:

$$P{P}_{j,k}=\frac{O{D}_{j,k}}{P{r}_j},\forall j\in J,\forall k\in J$$

(7)

and $\underset{j}{\mathrm{Pr}}$ is the passenger entry rate at station j, as follows:

$${\mathrm{Pr}}_j=\sum _{k=j}^{J}O{D}_{j,k},\forall j\in J,\forall k\in J$$

(8)

Constraints

• Constraint 1: Safety headway constraints between trains:

$$D_{i+1,j}^{\ell }-D_{i,j}^{\ell }\ge \mathrm{Td},\forall i\in I^{\ell },\forall j\in J^{\ell },\forall \ell \in L$$

(9)

$$A_{i+1,j}^{\ell }-A_{i,j}^{\ell }\ge \mathrm{Td},\forall i\in I^{\ell },\forall j\in J^{\ell },\forall \ell \in L$$

(10)

The stations that both local-line trains and cross-line trains stop at are as follows:

$$D_{i,j}^k-D_{i,j}^p\ge \mathrm{Td},\forall i\in I^{\ell },\forall j\in J^{\ell },p\in L$$

(11)

$$D_{i+1,j}^p-D_{i,j}^k\ge \mathrm{Td},\forall i\in I^{\ell },\forall j\in J^{\ell },p\in L$$

(12)

$$A_{i,j}^k-A_{i,j}^p\ge \mathrm{Td},\forall i\in I^{\ell },\forall j\in J^{\ell },p\in L$$

(13)

$$A_{i+1,j}^p-A_{i,j}^k\ge \mathrm{Td},\forall i\in I^{\ell },\forall j\in J^{\ell },p\in L$$

(14)

• Constraint 2: Train dwelling time at stations:

$$\begin{array}{c}\multicolumn{1}{c}{30\ge S_{i,j}^{\ell }\ge S_{min}+\frac{a*U_{i,j}^{\ell }+b*{\mathrm{Dn}}_{i,j}^{\ell }}{\mathrm{nd}},}\\ \multicolumn{1}{c}{\forall i\in I^{\ell },\forall j\in J^{\ell },\forall \ell \in L}\end{array}$$

(15)

$$D_{i,j}^{\ell }-A_{i,j}^{\ell }=S_{i,j}^{\ell },\forall i\in I^{\ell },\forall j\in J^{\ell },\forall \ell \in L$$

(16)

• Constraint 3: The number of people getting on train i at station j of line $\ell$ is as follows:

$$\begin{array}{c}{U}_{i,j}^{\ell }\le \{\begin{array}{cc}{F}_{i,j}^{\ell }\hfill & F_{i,j}^{\ell }+P_{i,j}^{\ell }-{\mathrm{Dn}}_{i,j}^{\ell }<\mathrm{Tc}\hfill \\ \multicolumn{1}{c}{\mathrm{TC}-P_{i,j}^{\ell }+{\mathrm{Dn}}_{i,j}^{\ell }}& F_{i,j}^{\ell }+P_{i,j}^{\ell }-{\mathrm{Dn}}_{i,j}^{\ell }\ge \mathrm{Tc}\hfill \end{array}\hfill \\ \multicolumn{1}{c}{\forall i\in I^{\ell },\forall j\in J^{\ell },\forall \ell \in L}\end{array}$$

(17)

• Constraint 4: The number of passengers on the platform when train i arrives at station j of line $\ell$ is as follows:

$$\begin{array}{c}{F}_{i,j}^{\ell }=\{\begin{array}{cc}{\mathrm{FL}}_{i,j}^{\ell }+(d_{i+1,j}^{\ell }-d_{i,j}^{\ell })*{\mathrm{Pr}}_j\hfill & i=1\hfill \\ \multicolumn{1}{c}{{\mathrm{FL}}_{i,j}^{\ell }+(D_{i+1,j}^{\ell }-D_{i,j}^{\ell })*{\mathrm{Pr}}_j}& i\ne 1\hfill \end{array}\hfill \\ \multicolumn{1}{c}{\forall i\in I^{\ell },\forall j\in J^{\ell },\forall \ell \in L}\end{array}$$

(18)

• Constraint 5: Arrival and departure time constraints of different trains at the same station:

$$A_{i+1,j}^{\ell }-D_{i,j}^{\ell }\ge \mathrm{Tdf},\forall i\in I^{\ell },\forall j\in J^{\ell },\forall \ell \in L$$

(19)

The stations that both local-line trains and cross-line trains stop at are as follows:

$$|A_{i,j}^k-D_{i,j}^p|\ge \mathrm{Tdf},\forall i\in I^{\ell },\forall j\in J^{\ell },\forall p\in L$$

(20)

$$|A_{i+1,j}^{\ell }-D_{i,j}^k|\ge \mathrm{Tdf},\forall i\in I^{\ell },\forall j\in J^{\ell },\forall p\in L$$

(21)

• Constraint 6: The actual arrival time of train i at station j is as follows:

$$A_{i,j+1}^{\ell }\ge D_{i,j}^{\ell }+R_j^{\ell },\forall i\in I^{\ell },\forall j\in J^{\ell },\forall \ell \in L$$

(22)

• Constraint 7: Cross-line trains run from line A to line B at the transfer station :

$$D_{i,O}^k=D_{i,O+1}^k+\mathrm{Tzz},\forall i\in I^{\ell }$$

(23)

• Constraint 8: The actual arrival and departure time are not less than the planned arrival and departure time:

$$A_{i,j}^{\ell }\ge a_{i,j}^{\ell },\forall i\in I^{\ell },\forall j\in J^{\ell },\forall \ell \in L$$

(24)

$$D_{i,j}^{\ell }\ge d_{i,j}^{\ell },\forall i\in I^{\ell },\forall j\in J^{\ell },\forall \ell \in L$$

(25)

In addition, we define a binary variable y to indicate whether the trains are changing order at the crossing station or not. If the cross-line trains change the running order with the trains of line $\ell \prime$ , let y = 1; otherwise, let y = 0.

If the running order of cross-line trains and trains of line $\ell \prime$ is changed, Equations (12), (14), and (21) will also be changed as follows.

The stations that both local-line trains and cross-line trains stop at:

$$\begin{array}{c}\{\begin{array}{cc}{D}_{i+1,j}^p-D^{k}i,j\ge \mathrm{Td}\hfill & y=0\hfill \\ \multicolumn{1}{c}{D_{i,j}^K-D_{i+1,j}^p\ge \mathrm{Td}}& y=1\hfill \end{array}\hfill \\ \multicolumn{1}{c}{\forall i\in I^{\ell },\forall j\in J^{\ell },\forall p\in L}\end{array}$$

(26)

$$\begin{array}{c}\{\begin{array}{cc}{A}_{i+1,j}^p-A^{k}i,j\ge \mathrm{Td}\hfill & y=0\hfill \\ \multicolumn{1}{c}{A_{i,j}^k-A_{i+1,j}^p\ge \mathrm{Td}}& y=1\hfill \end{array}\hfill \\ \multicolumn{1}{c}{\forall i\in I^{\ell },\forall j\in J^{\ell },\forall p\in L}\end{array}$$

(27)

$$\begin{array}{c}\{\begin{array}{cc}{A}_{i,j}^k-D_{i,j}^p\ge \mathrm{Tdf}\hfill & y=0\hfill \\ \multicolumn{1}{c}{A_{i,j}^k-D_{i+1,j}^p\ge \mathrm{Tdf}}& y=1\hfill \end{array}\hfill \\ \multicolumn{1}{c}{\forall i\in I^{\ell },\forall j\in J^{\ell },\forall p\in L}\end{array}$$

(28)

Model Solving

The model in this paper is a mixed integer nonlinear programming problem. There are many methods to solve liner programming problem. However, the nonlinear parts in the model need to be linearized first.

In constraint 3, the number of people getting on train i at station j is $U_{i,j}^{\ell }$ . A binary variable $x_{i,j}^{\ell }$ is introduced to represent the change of the value of the function, as follows:

$$\begin{array}{c}\{\begin{array}{cc}{F}_{i,j}^{\ell }+P_{i,j}^{\ell }-{\mathrm{Dn}}_{i,j}^{\ell }\le \mathrm{Tc}\hfill & x_{i,j}^{\ell }=1\hfill \\ \multicolumn{1}{c}{F_{i,j}^{\ell }+P_{i,j}^{\ell }-{\mathrm{Dn}}_{i,j}^{\ell }\ge \mathrm{Tc}}& x_{i,j}^{\ell }=0\hfill \end{array}\hfill \\ \multicolumn{1}{c}{\forall i\in I^{\ell },\forall j\in J^{\ell },\forall \ell \in L}\end{array}$$

(29)

Take a number M that is much larger than the number obtained by the formula as follows:

$$\begin{array}{c}\{\begin{array}{c}{F}_{i,j}^{\ell }+P_{i,j}^{\ell }-{\mathrm{Dn}}_{i,j}^{\ell }-\mathrm{Tc}\le M*(1-x_{i,j}^{\ell })\hfill \\ \multicolumn{1}{c}{F_{i,j}^{\ell }+P_{i,j}^{\ell }-{\mathrm{Dn}}_{i,j}^{\ell }-\mathrm{Tc}\ge -M*x_{i,j}^{\ell }}\end{array}\hfill \\ \multicolumn{1}{c}{\forall i\in I^{\ell },\forall j\in J^{\ell },\forall \ell \in L}\end{array}$$

(30)

Then combining the function value of $U_{i,j}^{\ell }$ with Equation 29, we have the following:

$$U_{i,j}^{\ell }=F_{i,j}^{\ell }*x_{i,j}^{\ell }+(1-x_{i,j}^{\ell })*(\mathrm{Tc}-P_{i,j}^{\ell }+{\mathrm{Dn}}_{i,j}^{\ell })$$

(31)

Because the solver cannot handle the nonlinear part, the nonlinear part of Equation 31 is represented by $f_{i,j}^A$ , and it can be converted into the following:

$$U_{i,j}^{\ell }=f_{i,j}^{\ell }+(\mathrm{Tc}-P_{i,j}^{\ell }+{\mathrm{Dn}}_{i,j}^{\ell })$$

(32)

$$f_{i,j}^{\ell }=(F_{i,j}^{\ell }-\mathrm{Tc}+P_{i,j}^{\ell }-{\mathrm{Dn}}_{i,j}^{\ell })*x_{i,j}^{\ell }$$

(33)

Next, choose a number M that is much greater than $f_{i,j}^A$ , and then $f_{i,j}^A$ can be converted into the following:

$$\{\begin{array}{c}{f}_{i,j}^{\ell }\le M*x_{i,j}^{\ell }\hfill \\ \multicolumn{1}{c}{f_{i,j}^{\ell }\ge -M*x_{i,j}^{\ell })}\\ \multicolumn{1}{c}{f_{i,j}^{\ell }\le F_{i,j}^{\ell }+P_{i,j}^{\ell }-{\mathrm{Dn}}_{i,j}^{\ell }-\mathrm{Tc}+M*(1-x_{i,j}^{\ell })}\\ \multicolumn{1}{c}{f_{i,j}^{\ell }\ge F_{i,j}^{\ell }+P_{i,j}^{\ell }-{\mathrm{Dn}}_{i,j}^{\ell }-\mathrm{Tc}-M*(1-x_{i,j}^{\ell })}\end{array}$$

(34)

After that, the model can be solved by the branch and bound algorithm.

Case Analysis

The urban rail transit network for the case analysis is shown in Figure 3. There are two lines, line a and line B, with six routing paths. There are seven stations on line A and eight stations on line B. The cross-line trains run from ${\mathrm{A}}_1$ to ${\mathrm{A}}_3$ and from ${\mathrm{B}}_4$ to ${\mathrm{B}}_8$ . This paper only analyzes the problem of the delay adjustment of up trains, and the method also works for the down trains.

Figure 3.

Layout of the urban rail transit network.

Parameters

The minimum stopping time and minimum running time are shown in Table 3. The cross-line operation time is 120 s and the minimum headway is 120 s. The arrival and departure interval constraints are 90 s. The time for each passenger to get on and off the train is 0.5 s. The planned schedule of the train is shown in Table 4. There are seven trains on line A, six trains on Line B, and the number of cross-line trains is six.

Table 3.

Schedule Dwelling Time and Minimum Running Time

Station	Dwelling time (s)	Interval	Running time (s)	Station	Dwelling time (s)	Interval	Running time (s)
A1	30	A1–A2	114	B1	30	B1–B2	116
A2	30	A2–A3	191	B2	30	B2–B3	112
A3	30	A3–A4	135	B3	30	B3–B4	181
A4	30	A4–A5	106	B4	30	B4–B5	92
A5	30	A5–A6	111	B5	30	B5–B6	93
A6	30	A6–A7	103	B6	30	B6–B7	141
A7	30			B7	30	B7–B8	148
				B8	30

Table 4.

Scheduled Departure Time of Trains at the First Station (Unit: s)

Line	Train
	1	2	3	4	5	6	7
A	60	395	730	1070	1410	1745	2085
B	30	330	660	990	1320	1670	na
Cross-line	200	545	895	1240	1590	1940	na

Note: na = not applicable.

In this case, the first cross-line train is delayed at the second station ${\mathrm{A}}_2$ . If there are no trains to be adjusted, all relevant trains will be red delayed according to the initial delay.

Adjustment Results of Small-Scale Delays

When the train leaves station, there is a delay given as 120 s. The model to delay all subsequent trains according to the length of time the first train has been delayed is named “No adjustment $s_1$ .” The total delay time will be 26,927 s and the number of stranded passengers is as large as 509. The objective function value is 1. The model with adjustment for small-scale delay is named “Optimization model $s_2$ .” The operation diagrams of the trains before and after adjustment are obtained according to the optimization result with a weight ratio of 0.5 to 0.5, as shown in the Figure 4. The red lines are cross-line trains, and the black lines are local-line trains. The solid lines are the actual operation time after the delay adjustment, and the dotted lines are the planned operation time before the delay. It can be found that the trains on line A are only affected by one train after the delayed cross-line train. The trains on line B and the trains on line A are only affected by the delayed cross-line trains.

Figure 4.

Delay adjustment operation diagram of small-scale delay: (a) diagram of line A trains and cross-line trains and (b) diagram of line B trains and cross-line trains (color online only).

The solution results of the models are shown in Table 5. Different weights are analyzed for different importance of the total delay time and the stranded passengers. It shows that different weights have little effect on the total delay time, but they have a great influence on the number of stranded passengers. The initial delay of the first cross-line train is 120 s, but the departure time at the last station is only 60 s later than the planned arrival time. For the trains on line A affected by the delayed cross-line train, the departure time at the last station is 21 s later than planned. For the trains on line B affected by the delayed cross-line train, the departure time at the last station is 9 s later than planned. This shows that the model in this paper has a good performance for delay adjustment. For small-scale delays, the model can greatly reduce the impact of passengers and enable trains to meet the requirements of delay limits. The number of passengers stranded because of train delays is 15.

Table 5.

Model Performance of Small-Scale Delay

$\omega 1:\omega 2$	Method	Objective function Z	Total delay time (s) Z1	Stranded passengers Z2	Optimization percentage (%)
	No Adjustment $s_1$	1	26,927	509	na
0.3:0.7	Optimization model $s_2$	0.0519	2062	21	94.81%
0.5:0.5	Optimization model $s_2$	0.0531	2067.8	15	94.69%
0.7:0.3	Optimization model $s_2$	0.0232	2086	0	97.68%

Note: na = not applicable.

Adjustment Results of Large-Scale Delay

When the train leaves station, there is a delay time given as 600 s. Without adjustment, the model to delay all subsequent trains according to the length of time the first train has been delayed is named “No adjustment $l_1$ .” The total delay time will be 68,088 s and the number of stranded passengers is as large as 3860. The objective function value is 1. In the situation of large-scale delay, the model without changing of the train order is named “Order unchanged $l_2$ ,” and the model that allows changing of the train order is named “Optimization model $l_3$ .” The operation diagrams of the trains before and after adjustment are obtained according to the optimization result with a weight ratio of 0.5 to 0.5, as shown in the Figure 5. The red lines are cross-line trains, and the black lines are local-line trains. The solid lines are the actual operation time after the delay adjustment, and the dotted lines are the planned operation time before the delay.

Figure 5.

Delay adjustment operation diagram of large-scale delay: (a) diagram of line A trains and cross-line trains and (b) diagram of line B trains and cross-line trains (color online only).

The solution results of the models are shown in Table 6. Different weights have little effect on the total delay time, but have a great influence on the number of stranded passengers. When there is a large-scale delay, changing the operation order of line B trains and cross-line trains will lead to different delay time. The model proposed in this paper can automatically select a better strategy. Although the number of stranded passengers in the entire rail transit network is 388, the stranded passengers are mainly concentrated on the trains on line A affected by the delayed cross-line train. The trains on line B that are scheduled to operate after the delayed cross-line train will not be affected by the delay and can still run according to the plan. Therefore, the strategy of changing the operation order can reduce more the total delay time compared with the unchanged one.

Table 6.

Model Performance of Large-Scale Delay

$\omega 1:\omega 2$	Method	Objective function Z	Total delay time (s) Z1	Stranded passengers Z2	Optimization percentage (%)
	No Adjustment $l_1$	1	68,088	3860	na
0.3:0.7	Order unchanged $l_2$	0.1974	15,740	458	80.26%
0.3:0.7	Optimization model $l_3$	0.1454	14,143.6	458	85.46%
0.5:0.5	Order unchanged $l_2$	0.1665	15,793.4	390	83.35%
0.5:0.5	Optimization model $l_3$	0.1546	14,210	388	84.54%
0.7:0.3	Order unchanged $l_2$	0.1375	15,811.9	374	86.25%
0.7:0.3	Optimization model $l_3$	0.1305	14,215	374	86.95%

Note: na = not applicable.

For large-scale delay, adjustment models can greatly reduce the total delay time and the number of stranded passengers. The model that allows changing the order of trains improves the performance further than the model without changing the order.

The Simulation Results of Beijing Metro Line

Simulations are also done on the urban rail transit network of Beijing Subway 13 A and B, as shown in Figure 6. There are two lines, line A and line B, with six routing paths. There are 18 stations on line A and 15 stations on line B. The cross-line trains run from the station ${\mathrm{A}}_1$ to ${\mathrm{A}}_{11}$ , ${\mathrm{A}}_{11}$ to ${\mathrm{B}}_4$ , and ${\mathrm{B}}_4$ to station ${\mathrm{B}}_{15}$ . This paper only analyzes the problem of delay adjustment of up trains, and the method also works for the down trains.

Figure 6.

The layout of Beijing Subway lines 13 A and B.

The minimum stopping time and minimum running time are shown in Table 7. The cross-line operation time is 120 s, and the minimum headway is 120 s. The arrival and departure interval constraints are 90 s. The planned schedule of the train is shown in Table 8. There are 11 trains on line A, 11 trains on line B, and the number of cross-line trains is 11.

Table 7.

Schedule Dwelling Time and Minimum Running Time

Station	Dwelling time (s)	Interval	Running time (s)	Station	Dwelling time (s)	Interval	Running time (s)
A1	30	A1–A2	90	B1	30	B1–B2	136
A2	30	A2–A3	131	B2	30	B2–B3	132
A3	30	A3–A4	92	B3	30	B3–B4	205
A4	30	A4–A5	93	B4	30	B4–B5	92
A5	30	A5–A6	127	B5	30	B5–B6	93
A6	30	A6–A7	88	B6	30	B6–B7	141
A7	30	A7–A8	236	B7	30	B7–B8	148
A8	30	A8–A9	88	B8	30	B8–B9	136
A9	30	A9–A10	114	B9	30	B9–B10	124
A10	30	A10–A11	161	B10	30	B10–B11	254
A11	30	A11–A12	135	B11	30	B11–B12	121
A12	30	A12–A13	106	B12	30	B12–B13	92
A13	30	A13–A14	111	B13	30	B13–B14	93
A14	30	A14–A15	103	B14	30	B14–B15	133
A15	30	A15–A16	234	B15	30	na	na
A16	30	A16–A17	108	na	na	na	na
A17	30	A17–A18	111	na	na	na	na
A18	30	na	na	na	na	na	na

Note: na = not applicable.

Table 8.

Scheduled Departure Time of Trains at the First Station (unit: s)

Line	Train
	1	2	3	4	5	6	7	8	9	10	11
A	170	5510	8850	11,190	11,530	11,870	22,210	22,550	22,890	33,230	33,570
B	1257	11,597	11,937	22,277	22,617	22,957	33,297	33,637	33,977	44,317	44,657
Cross-line	340	6680	11,020	11,360	11,700	22,040	22,380	22,720	33,060	33,400	33,740

Suppose the first case is that the initial delay value is 120 s, which occurs when the first cross-line train departs station A02. The planned operation diagrams and the actual operation diagrams after delay adjustment are shown in Figure 7. The dotted lines in the figure are the planned trains diagram, and the solid lines are the actual trains diagram after delay adjustment. The red lines are the diagram of cross-line trains, the black lines in Figure 7(a) are the A line trains diagram, and the black lines in Figure 7(b) are the B line trains diagram. Under this initial delay, the model to delay all subsequent trains according to the length of time the first train has been delayed is named “No adjustment $s_1$ .” The solution of the optimization model under the small-scale delay is named “Optimization model $s_2$ .” The results are shown in Table 9. Optimization model $s_2$ greatly reduces the impact on total delay time, and no passengers are stranded.

Figure 7.

Delay adjustment operation diagrams of 160 s delay: (a) diagram of line A trains and cross-line trains and (b) diagram of line B trains and cross-line trains (color online only).

Table 9.

Solution Result of the Beijing Subway Line 13

$\omega 1:\omega 2$	Method	Objective function Z	Total delay time (s) Z1	Stranded passengers Z2	Optimization percentage (%)
	No adjustment $s_1$	1	143,114	250	na
0.5:0.5	Optimization model $s_2$	0.000932	1329	0	99.91%
	No adjustment $l_1$	1	712,781	23,692	na
0.5:0.5	Order unchanged $l_2$	0.1945	98,604	5938	80.55%
0.5:0.5	Optimization model $l_3$	0.1844	96,790	5518	81.56%

Note: na = not applicable.

Suppose the second case is that the initial delay value is 600 s, which occurs when the first cross-line train departs station A02. The planned operation diagram and the adjusted operation diagram without considering the change of operation order after delay are shown in the Figure 8. The planned operation diagram and the actual operation diagram with the optimal goal after delay adjustment are shown in the Figure 9. The dotted lines in the figure are the planned train diagram, and the solid lines are the actual trains diagram after delay adjustment. The red lines are the diagrams of cross-line trains, the black lines in Figure 9(a) are the A line trains diagrams, and the black lines in Figure 9(b) are the B line trains diagrams. Under this initial delay, the model to delay all subsequent trains according to the length of time the first train has been delayed is named “No adjustment $l_1$ .” In the situation of large-scale delay, the model without changing of the train order is named ”Order unchanged $l_2$ .” In the situation of large-scale delay, the model that allows changing the train order is named “Optimization model $l_3$ .” As can be seen from Table 9, Optimization model $l_3$ can greatly reduce the total delay time and the number of stranded passengers. The result of Optimization model $l_3$ considering changing the operation order is better than that of Order unchanged model $l_2$ .

Figure 8.

Delay adjustment operation diagram of 600 s delay without considering the change of operation order: (a) diagram of line A trains and cross-line trains and (b) diagram of line B trains and cross-line trains (color online only).

Figure 9.

Delay adjustment operation diagram of 600 s delay with considering the change of operation order: (a) diagram of line A trains and cross-line trains and (b) diagram of line B trains and cross-line trains (color online only).

Thus, it can be seen that under different degrees of initial delay, this model can greatly reduce the impact of delay on the trains on the line. For the large-scale delay, it is possible to reduce the total delay by considering changing the running order of cross-line trains and local trains.

Analysis of Different Optimization Objectives

In the above sections, the weighted value of the total delay time and the number of stranded passengers is studied as the delay adjustment target. In this part, the delay adjustment results obtained by different optimization objectives will be compared and analyzed.

Firstly, the waiting time of passengers affected by delay is taken as the optimization target. The passenger waiting time is divided into two parts: one is the waiting time of the passengers who get on the train smoothly, and the other is the waiting time of the stranded passengers. Passenger waiting time reflects the impact of delay on passengers in the station. Taking it as the optimization target of delay adjustment can decrease the waiting time of passengers in the station and may reduce the number of passengers who transfer to other public transport because of long waiting times. It is helpful to alleviate the decline in the attractiveness of urban rail transit caused by delay. The objective function is as follows:

$$\begin{array}{cc}\multicolumn{1}{c}{Z=}& \sum _{\ell \in L}\sum _{i=\in I}\sum _{j=\in J}{U}_{i,j}^{\ell }*\frac{D_{i,j}^{\ell }-D_{i-1,j}^{\ell }}{2}\hfill \\ \multicolumn{1}{c}{+}& \gamma \sum _{\ell \in L}\sum _{i=\in I}\sum _{i=\in J}{\mathrm{FL}}_{i,j}^{\ell }*(D_{i+1,j}^{\ell }-D_{i,j}^{\ell })\hfill \end{array}$$

(35)

To facilitate the calculation, the waiting time of each passenger who successfully boards the train is half of the interval between the train and the previous train on average, that is, half of the interval between the departure of the train ( $D_{i,j}^{\ell }$ ) and that of the previous train ( $D_{i-1,j}^{\ell }$ ). Here, ${\mathrm{FL}}_{i,j}^{\ell }$ is the number of passengers stranded because the passengers at station j fail to board train i. Take the waiting time of each stranded passenger as the result of $\gamma$ multiplying the interval between the departure of the train ( $D_{i,j}^{\ell }$ ) and that of the next train ( $D_{i+1,j}^{\ell }$ ). Because the actual waiting time of each stranded passenger is different, $\gamma$ is the coefficient between the average waiting time of stranded passengers and the interval of the departure time. However, the waiting time of each stranded passenger is longer than the departure interval of the two sequential trains at the station. Therefore, the waiting time of each stranded passenger is taken as the result of $\gamma$ multiplied by the departure interval.

Secondly, the delay time of the passengers on the train is taken as the optimization target. Taking the delay time of passengers on the train as the research object can reflect the degree of deviation between the actual arrival time of passengers and the planned time of arrival. Optimizing the delay time of passengers can reduce the impact of delay on their travel and alleviate the decline in passenger satisfaction caused by some delay. The objective function is as follows:

$$Z=\sum _{\ell \in L}\sum _{i=\in I}\sum _{i=\in J}{\mathrm{Dn}}_{i,j}^l*(A_{i,j}^l-a_{i,j}^l)$$

(36)

The difference between the actual time of arrival of the passengers at the stations and the planned arrival time of the trains is regarded as the delay time of the passengers. The delay time of the passengers on the train can be obtained by adding up the delay times of the passengers who get off the train through the stop.

The simulation results using the same lines and data are shown in the Figure 10. With the total delay time taken as the objective function, the train diagram obtained by optimization is defined as “Optimization 1.” The operation diagram obtained by optimizing the passenger waiting time as the objective function is defined as “Optimization 2.” With the delay time of passengers on the trains taken as the objective function, the operation diagram is defined as “Optimization 3.”

Figure 10.

Train diagrams with different targets: (a) diagram of line A trains and cross-line trains and (b) diagram of line B trains and cross-line trains.

Figure 10 shows that there is little difference between the adjusted train diagrams of line A and line B with different optimization objectives, but there is a substantial difference between the diagrams of cross-line trains. For Optimization 2, the arrival and departure time of the second cross-line train are later than that of the operation diagrams of the other optimization objectives. For passengers with more passenger flow at the station, their waiting time can be reduced. For Optimization 3, the arrival and departure time of cross-line trains are earlier than that for the operation diagrams of the other optimization objectives. For passengers who miss the train, their waiting time may be relatively long. The arrival time of the cross-line train in the operation diagram obtained by Optimization 3 is earlier than that in the operation diagram with Optimization 2. Passengers who are about to arrive at the station will undoubtedly choose this kind of operation diagram.

According to different passenger flow distributions, different objectives should be used as the optimization target of delay adjustment. For stations with high demand by passengers, it may be better to take the passenger waiting time as the target of the delay and adjustment.

Conclusion and Future Work

This paper proposes a delay adjustment model of the urban rail transit network with cross-line trains based on considering the interaction between passenger flow and train operation. Simulations have been done for an example case and Beijing Metro Line 13. The results show that different strategies should be adopted for different scales of initial delay. When the initial delay is small, only the stop time needs to be adjusted. Compared with the no adjustment case, the performance has been improved by 94.69% with equal importance of the total delay time and stranded passengers with a small initial delay. While the initial delay is large, it is necessary to change the running order of the cross-line trains and local-line trains at the transfer station besides the adjustment of the stop time. By doing this, the performance has been improved by 84.54% with the equal importance of the total delay time and stranded passengers with a large initial delay. Different weights are analyzed based on different importance of the total delay time and stranded passengers. It shows that different weights have little effect on the total delay time, but they have a great influence on the number of stranded passengers. Similar results have also achieved on a simulation of Beijing Metro Line 13 and good performance is presented with tables and diagrams.

There are still many issues that can be further studied. One area for consideration is how to handle the stochasticity of train delays. The optimization model and algorithm need to be further improved with new challenges.