Optimization method of urban rail train operational plan based on O-D time-varying demand

Abstract

Purpose

Under the constraints of given passenger service level and coupling travel demand with train departure time, this study optimizes the train operational plan in an urban rail corridor to minimize the numbers of train trips and rolling stocks considering the time-varying demand of urban rail passenger flow.

Design/methodology/approach

The authors optimize the train operational plan in a special network layout, i.e. an urban rail corridor with dead-end terminal yard, by decomposing it into two sub-problems: train timetable optimization and rolling stock circulation optimization. As for train timetable optimization, the authors propose a schedule-based passenger flow assignment method, construct the corresponding timetabling optimization model and design the bi-directional coordinated sequential optimization algorithm. For the optimization of rolling stock circulation, the authors construct the corresponding optimization assignment model and adopt the Hungary algorithm for solving the model.

Findings

The case study shows that the train operational plan developed by the study's approach meets requirements on the passenger service quality and reduces the operational cost to the maximum by minimizing the numbers of train trips and rolling stocks.

Originality/value

The example verifies the efficiency of the model and algorithm.

Citation

Shi, F., Tu, X. and Zhao, S. (2022), "Optimization method of urban rail train operational plan based on O-D time-varying demand", Railway Sciences, Vol. 1 No. 1, pp. 148-166. https://doi.org/10.1108/RS-04-2022-0008

1. Introduction

The operation efficiency and service level of urban rail transit (URT) lines largely depend on the train operational plan. A high-quality train operational plan usually involves the weighing of the interests of both passengers and operators, on the one hand, to provide better service for passengers, and on the other hand, reduce operation costs for operators (Guihaire & Hao, 2008).

A train operational plan includes a train timetable and rolling stock circulation. The existing studies on train timetable focus more on reducing passenger travel costs, such as reducing passengers' waiting time (Yalcınkaya & Bayhan, 2009), transfer time (Wong, Yuen, & Leung, 2008) and total travel time (Kaspi & Raviv, 2013) and optimizing periodic train timetable (Odijk, 1996). Qin and Shi (2005) comprehensively considered the travel cost of passengers and the operating cost of operators. However, all these studies assumed that the all-day travel demand was fixed or an ideal flow of passenger arriving at the station evenly. In fact, the travel demand of passengers fluctuates with time, which is called time-varying demand (Vuchic, 2017). Based on the time-varying origin-destination (O-D) demand and considering the amount of trains in round trips and seat occupancy rate, Niu and Zhou (2013) contained the design of a genetic algorithm to optimize the time headway between train departures, to reduce the passengers’ waiting time. Taking the suburban railway in Germany as the background, Albrecht (2009) emphasized that it was necessary to determine the flexible train headway so as to adapt to the time-varying passenger flow. Deng, Zeng, Gao and Zhou (2012) and Shi, Zhou, Chen and Deng (2008) established a bi-level programming model of passenger train operation schedule based on the flexible demand and contained the design of an optimization algorithm based on the simulated annealing algorithm. The implementation of a train timetable must be guaranteed by the rolling stock circulation (Ceder, 2002). Based on the given train operation timetable, Freling, Wagelmans and Paixão (2001) studied the train dispatching issue of a single yard. The problem of comprehensively optimizing the train operational plan was complex, with few relevant research results. Shi, Zhao, Zhou, Wang and Michael (2017) put forward a two-stage optimization method of train timetable and rolling stock circulation to meet the service level according to the time-varying section demand of URT lines. At the same time, Zhou, Shi, Chen and Deng (2011) provided a certain referential value for the optimization of urban rail train operational plan. Although the above references fail to optimize the urban rail train operational plan based on O-D time-varying demand, they have certain enlightening significance on the ideas and methods of optimization.

Based on the research results of the above references and aiming at the O-D time-varying demand of URT lines, this paper, taking the URT lines with a single dead-end yard as the research background, puts forward a passenger flow distribution method based on train timetable. The proposed method realizes the coupling between O-D time-varying demand and train timetable under the restriction of given passenger service level. And then the paper builds a two-stage optimization model of train timetable and rolling stock circulation with the goal of minimizing the number of trains in round trips and the number of allocated passenger trains and proposes a two-stage solution algorithm.

2. Problem statement

The URT line has m stations, s1,s2,⋯,sm, and all stations are taken as S. Stations - sm are in the down direction D of the line, and stations sm–s1 are in the up direction U. The sum of the travel time of a train from station su to sv and the dwell time at station sv is τ(su,sv). The train parking capacity of termination stations s1 and sm is N1 and Nm, respectively (including immediate turning-around trains), the turning-around operation time is r1 and rm, respectively, and the all-day operation period is [T1,T2].

The passenger travel demand of the line is time-varying, and the time-varying travel demand between stations su,sv∈S is an intensity distribution function quv(t),t∈[T1,T2] in the all-day operation period [T1,T2] and the total O-D travel demand between stations su,sv∈S is ∫T1T2quv(t)dt. For every O-D pair, the intensity distribution function quv(t),t∈[T1,T2] is usually represented by a uniform-headway step function, and each headway is taken as 1 min or 5 min. It is assumed that the demand ∫T1T2quv(t)dt is a continuous function about t.

2.1 Train operational plan

A train timetable includes the number of train operation pairs n and the departure time of every train at each station. The departure time of the k-th down-direction train at station su is taken as xku, and the departure time of the k-th up-direction train at station su is taken as yku. The urban rail trains are operated according to the mode of stop at each station, and the dwell time and section travel time of trains are given, so the departure time of trains from the originating station completely decides the departure time at each station along the way. So, the train timetable can be expressed as the departure time set of all the down-direction trains from the originating station X=(x11,x21,⋯,xn1), and the departure time set of all the up-direction trains from the originating station Y=(y1m,y2m,⋯,ynm).

The rolling stock circulation is mainly affected by the layout of the yard. There are many forms of yard layout on URT lines, and each layout form corresponds to different types of rolling stock circulations. In this paper, the optimization problem of train timetable and train connection is discussed in the context of the single end yard form. The characteristics of urban rail lines with a single end yard and train operation organization form are as follows:

There is only one yard p on the line, which is adjacent to the termination station s1, and the yard p has no capacity limit; if the station s1 reaches saturation, the newly arrived train must park at the yard p; if the station sm is saturated, a train can only arrive after any train leaves the station sm.

Thus, it can be seen that all the morning trains are provided to the station s1 by the yard p. They depart from the station s1 and arrive at station sm or turn back to the station s1 or stay at station sm; after any such train arrives at station s1, it can turn back to the station sm or park at the station or return to the yard; all the evening trains return to yard p.

2.2 Passenger service level

Consider the passenger service level from the following three aspects.

1. Departure time limit of the first and last trains: the departure time of the first down and up-direction trains shall be no later than the latest departure time tLD,tLU∈[T1,T2], respectively; the departure time of the last down and up-direction trains is, respectively, no earlier than the earliest departure time tED,tEU∈[T1,T2].

2. Train headway limit: the minimum train headway is τmin, and the maximum train headway is τmax.

3. Train passenger capacity limit: the train passenger carrying capacity is C, and the conventional passenger carrying coefficient is α (0<α<1). Generally, the section passenger capacity of the train does not exceed αC, unless the train departs at the minimum train headway. When the train departs at the minimum train headway, the maximum section passenger capacity of the train reaches αC, but does not exceed the train passenger carrying capacity C. The demand exceeding the passenger carrying capacity C  is regarded as the stranded passenger flow at the station.

2.3 Optimization of the train operational plan

To sum up, the optimization of train operational plan can be described as follows: given the URT line composed of station sequence s1,s2,⋯,sm and the operation time period [T1,T2], the time-varying travel demand quv(t),t∈[T1,T2] between stations su,sv∈S, the sum τ(su,sv) of train travel time between stations su,sv∈S and dwell time at station sv, the service level related parameters tLD,tLU, tED,tEU, τmin,τmax,C,αC and the parking capacity N1 and Nm of termination stations s1 and sm, optimize the number of train pairs n, the departure time X=(x11,x21,⋯,xn1) of the down-direction trains and the departure time Y=(y1m,y2m,⋯,ynm) of the up-direction trains as well as the connection relationship of trains at the terminal of station s1 under the constraints of passenger service level and parking capacity, so as to minimize the number of train pairs n, the number of allocated passenger trains and the train connection time in turn.

3. Passenger flow distribution based on the train timetable

The passenger flow distribution based on the train timetable is to simulate the boarding behavior of passengers and calculate the remaining capacity of trains at each station according to the passenger flow volume, the number of alighting passengers and the capacity of each train when it arrives at each station and determine the allowable number of boarding passengers. The passenger volume exceeding the allowable boarding number is regarded as stranded passenger flow, and stranded passenger flow volume of each station is recorded, respectively, according to the destination. When the demand exceeds the allowable boarding number, the demand at each destination shall be subject to the boarding principle of equal proportion to appropriately embody the principle of first-come-first-served.

The defined variables Pˇ(u,v,k),Pˆ(u,v,k), respectively, represent the passenger flow volume remained on the k-th down-direction train and the k-th up-direction train when leaving the station su, with station sv as the destination. For Pˇ(u,v,k), the value range is set as u=0,1,⋯,m−1;v=u+1,u+2,⋯,m;k=1,2,⋯,n, and the initial value is specified as P(0,v,k)=0. For Pˆ(u,v,k), the value range is set as u=m+1,m,⋯,2;v=u−1,u−2,⋯,1;k=1,2,⋯,n, and the initial value is specified as P(m+1,v,k)=0. Especially, when the destination station is v=0, the variables Pˇ(u,0,k),Pˆ(u,0,k), respectively, represent the total passenger flow volume remained on the k-th down-direction train and the k-th up-direction train leaving the station su (also called section passenger flow volume of trains).

The defined variables Rˇ(u,v,k),Rˆ(u,v,k), respectively, represent the stranded passenger flow volume when the k-th down-direction train and the k-th up-direction train leave the station su, with station sv as their destination. For Rˇ(u,v,k), the value range is set as u=1,2,⋯,m−1;v=u+1,u+2,⋯,m;k=0,1,2,⋯,n, and the initial value is specified as Rˇ(u,v,0)=0. For Rˆ(u,v,k), the value range is set as u=m,m−1,⋯,2;v=u−1,u−2,⋯,1;k=0,1,2,⋯,n and the initial value is specified as Rˆ(u,v,0)=0. Especially, when the destination station is v=0, the variables Rˇ(u,0,k),Rˆ(u,0,k), respectively, represent the total stranded passenger flow volume when the k-th down-direction train and the k-th up-direction train leave the station su.

Based on the given train timetable, the bidirectional stranded passenger flow volume and passenger flow volume of each station are calculated, respectively.

1. Down direction

In the sequence of k=1,2,⋯,n;u=1,2,⋯,m−1;v=u+1,u+2,⋯,m, the stranded passenger flow volume and the passenger flow volume are worked out recursively and, in turn, are as follows.

First, work out the total stranded passenger flow volume, namely

(1)Rˇ(u,0,k)=max{0,∑v=u+1m(Pˇ(u−1,v,k)+Rˇ(u,v,k−1)+∫xk−1uxkuquv(t)dt)−C}

where, x0u=T1.

Second, decompose it into the stranded passenger flow volume Rˇ(u,v,k) of each terminal station v by Rˇ(u,0,k). If Rˇ(u,0,k)=0, there is no stranded passenger flow volume; otherwise, it is distributed to each termination station v according to the equal proportion rule of boarding demand, namely

(2)Rˇ(u,v,k)={0,if Rˇ(u,0,k)=0Rˇ(u,0,k)Rˇ(u,v,k−1)+∫xk−1uxkuquv(t)dt∑v=u+1m(Rˇ(u,v,k−1)+∫xk−1uxkuquv(t)dt),if Rˇ(u,0,k)>0

Finally, work out the total passenger flow volume Pˇ(u,0,k) on the train leaving the station su and the passenger flow volume Pˇ(u,v,k) at different destinations, namely

(3)Pˇ(u,v,k)=Pˇ(u−1,v,k)+Rˇ(u,v,k−1)+∫xk−1uxkuquv(t)dt−Rˇ(u,v,k)

(4)Pˇ(u,0,k)=∑v=u+1mPˇ(u,v,k)

1. Up direction

In the sequence of k=1,2,⋯,n;u=m,m−1,⋯,2;v=u−1,u−2,⋯,1, the stranded passenger flow volume and the passenger flow volume are worked out recursively and, in turn, are as follows.

First, work out the total stranded passenger flow volume, namely

(5)Rˆ(u,0,k)=max{0,∑v=1u−1(Pˆ(u+1,v,k)+Rˆ(u,v,k−1)+∫yk−1uykuquv(t)dt)−C}

where y0u=T1.

Second, decompose it into the stranded passenger flow volume Rˆ(u,v,k) of each terminal station v by Rˆ(u,0,k), i.e. if Rˆ(u,0,k)=0, there is no stranded passenger flow volume; otherwise, it is distributed to each terminal station v according to the equal proportion rule of boarding demand, namely

(6)Rˆ(u,v,k)={0,if Rˆ(u,0,k)=0Rˆ(u,0,k)Rˆ(u,v,k−1)+∫yk−1uykuquv(t)dt∑v=1u−1(Rˆ(u,v,k−1)+∫yk−1uykuquv(t)dt),if Rˆ(u,0,k)>0

Finally, work out the total passenger flow volume Pˆ(u,0,k) on the train leaving the station su and the passenger flow volume Pˆ(u,v,k) at different destinations, namely

(7)Pˆ(u,v,k)=Pˆ(u+1,v,k)+Rˆ(u,v,k−1)+∫yk−1uykuquv(t)dt−Rˆ(u,v,k)

(8)Pˆ(u,0,k)=∑v=1u−1Pˆ(u,v,k)

4. Optimization model of train timetable

The constraints related to train departure time are as follows.

1. The constraints on departure time of the first train. The first bidirectional train departure time x11,y1m needs to meet the following conditions.

   • The constraints on the latest departure time tLD,tLU, namely x11≤tLD, y1m≤tLU

   • The maximum passenger flow volume of the first train does not exceed the train passenger carrying capacity C, without constraints of stranding. The departure times when the maximum section passenger flow volume of the first train reaches the train passenger carrying capacity C without stranding are recorded, respectively, as x¯11,y¯1m. That is to say, the maximum total passenger flow volume of the first down-direction train entering station sw (w=2,3,⋯,m) with the departure time from the originating station as x¯11 is equal to the train passenger carrying capacity C without stranding, namely

(9)max2≤w≤m∑u=1w−1∑v=wm∫T1x¯11+τ(s1,su)quv(t)dt=C

Formula (9) is the basis for solution of x¯11. Similarly, the maximum total passenger flow volume of the first up-direction train entering station sw (w=2,3,⋯,m−1) with the departure time from the originating station as y¯1m is equal to the train passenger carrying capacity C without stranding, namely

(10)max1≤w≤m−1∑u=w+1m∑v=1w∫T1y¯1m+τ(sm,su)quv(t)dt=C

Formula (10) is the basis for solution of y¯1m. So x11≤x¯11,  y1m≤y¯1m.

Considering the above two parts, the constraints on the departure time of the first train are obtained as follows:

(11)x11≤min{tLD,x¯11}

(12)y1m≤min{tLU,y¯1m}

1. The constraints on the earliest departure time of the last train are expressed as follows:

(13)xn1≥tED

(14)ynm≥tEU

1. The constraints on the minimum train headway. The train headway in the same direction shall not be less than the minimum train headway, namely

(15)xi+11−xi1≥τmin,      i=1,2,⋯,n−1

(16)yj+1m−yjm≥τmin,     j=1,2,⋯,n−1

1. The constraints on the maximum train headway. The train headway in the same direction shall not be greater than the maximum train headway, namely

(17)xi+11−xi1≤τmax,      i=1,2,⋯,n−1

(18)yj+1m−yjm≤τmax,     j=1,2,⋯,n−1

1. Relationship between the train leaving time at each station and the departure time at the originating station.

Since τ(s1,su),τ(sm,su), respectively, represent the sum of the travel time of train in section (s1,su),(sm,su) and the dwell time at station su, the following relationship is satisfied.

(19)xiu=xi1+τ(s1,su),       su∈S\{sm}

(20)yju=yjm+τ(sm,su),     su∈S\{s1}

The variables xiu and yju are only used for the passenger flow distribution in Formulas (1)–(8). They can also be taken as the intermediate variables.

1. Constraint on train connection at station sm of no-yard end. Before the i-th up-direction train leaves, the i-th down-direction train must arrive at the station sm. As τ(s1,sm) represents the sum of the travel time of the train in the section (s1,sm) and the dwell time at station sm, and rm is the turning-around operation time at the station sm,

(21)xi1+τ(s1,sm)+rm≤yim,      i=1,2,⋯,n

1. Constraint on train parking capacity at station sm of no-yard end. Before the i-th down-direction train arrives at station sm, the i-N_m up-direction train must leave the station. As τ(s1,sm) represents the sum of the travel time of the train in the section sm and the dwell time at station, and rm is the turning-around operation time of the station sm, so

(22)xi1+τ(s1,sm)≥yi−hmm,    i>hm

1. Coupling of travel demand and train departure time from the originating station. If the train departs at the minimum train headway, the maximum section passenger capacity of the train reaches the conventional passenger carrying capacity αC, but does not exceed the maximum passenger bearing capacity C; otherwise, the section passenger capacity of the train does not exceed the conventional passenger carrying capacity αC. Namely

(23)Pˇ(u,0,i)≥αC,      xi1−xi−11=τmin,su∈S\{sm}

(24)Pˆ(u,0,j)≥αC,      yjm−yj−1m=τmin, su∈S\{s1}

(25)Pˇ(u,0,i)≤αC,      xi1−xi−11>τmin,su∈S\{sm}

(26)Pˆ(u,0,j)≤αC,      yjm−yj−1m>τmin,su∈S\{s1}

As the limits of train capacity C have been considered during the calculation of the passenger flow volume Pˇ(u,i),Pˆ(u,j) on the train, there is no need to add related constraints.

Taking the minimization of the number of train pairs n as the objective function of optimization and the above-mentioned relationship as the constraints, the optimization model of train timetable is constructed as follows:

(27)minZ=n

s.t. Formulas (1)–(26).

5. Optimization algorithm of train timetable

5.1 Algorithm thought

In the optimization model of train timetable, the number of train pairs n is a variable, and all departure time variables xi1,yjm are related to the variable n, so the optimization model is not a linear model. It can be seen that for the objective function of minimizing the number of train pairs n, the number of train pairs is minimized accordingly as long as each x11,x21,⋯ and y1m,y2m,⋯ is maximized.

The solving process is divided into three steps: maximizing the departure time of the first train, maximizing the departure time of the intermediate train and the termination conditions.

1. Maximizing the first train departure time x11,y1m

According to the obtained x¯11 and  y¯1m as well as Formulas (11), (12) and (21), maximize x¯11 and  y¯1m to obtain

(28)y1m=min{tLU,y¯1m}

(29)x11=min{tLD,x¯11,y1m−τ(s1,sm)−rm}

In fact, try to make y¯1m=tLU first and verify Formula (10), if max1≤w≤m−1∑u=w+1m∑v=1w∫T1y¯1m+τ(sm,su)quv(t)dt≤C, then y¯1m≥tLU. Now, it is not necessary to work out y¯1m specifically, and y1m=tLU can be obtained directly. If max1≤w≤m−1∑u=w+1m∑v=1w∫T1y¯1m+τ(sm,su)quv(t)dt>C. There must be y¯1m to make Formula (10) valid in the interval (T1,tLU), and such y¯1m can be searched with the method of bisection.

Similarly, try to make x¯11=min{tLD,y1m−τ(s1,sm)−rm} first and verify Formula (9); if max2≤w≤m∑u=1w−1∑v=wm∫T1x¯11+τ(s1,su)quv(t)dt≤C, then x¯11≥min{tLD,y1m−τ(s1,sm)−rm}. Now, it is not necessary to work out x¯11 specifically, and x11=min{tLD,y1m−τ(s1,sm)−rm} can be obtained directly. If max2≤w≤m∑u=1w−1∑v=wm∫T1x¯11+τ(s1,su)quv(t)dt>C, then, search x¯11 satisfying Formula (9) in the interval [T1,min{tLD,y1m−τ(s1,sm)−rm}] with the method of bisection.

1. Maximizing the departure time xi1,yjm(i=2,3,…,n−1;j=2,3,…,n−1) of intermediate trains

It might as well to set it under the constraint conditions of Formula (1)–(26). x11,x21,⋯,xi−11 and y1m,y2m,⋯,yj−1m have been worked out to the maximum extent one by one. Try to work out the xi1,yjm or either of them below.

Firstly, based on xi−11 and yj−1m, as well as the constraints of Formulas (1)–(20) and Formulas (23)–(26), maximize the preliminary values x¯i1 and y¯jm.

For the down direction, consider the following three circumstances, respectively.

1. Try to make xi1=xi−11+τmin and work out Formulas (1)–(8) to distribute the passenger flow of the down-direction train i. If Formula (23) is valid, i.e. Pˇ(u,0,i)≥αC,su∈S\{sm}, the constraint conditions of Formulas (1)–(20) and Formulas (23)–(26) are met, work out the maximum value x¯i1=xi−11+τmin of xi1.

2. If the above attempt is unsuccessful, try to make xi1=xi−11+τmax and work out Formulas (1)–(8) for passenger flow distribution of the down-direction train i. If Formula (25) is valid, i.e. Pˇ(u,0,i)≤αC,su∈S\{sm}, the constraint conditions of Formulas (1)–(20) and Formulas (23)–(26) are met, work out the maximum value x¯i1=xi−11+τmax of xi1.

3. If the above two attempts are unsuccessful, there must be an x¯i1 which makes Formula (25) valid in the interval [xi−11+τmin,xi−11+τmax]. In the interval, the method of bisection is used for search x¯i1. For every searched object x¯i1, make xi1=x¯i1, work out Formulas (1)–(8) to distribute the passenger flow of the down-direction train i. If Formula (25) is valid, and the maximum section passenger flow volume of the train is equal to αC, namely maxsu∈S\{sm}Pˇ(u,0,i)=αC, the maximum possible value x¯i1 of xi1 is worked out.

Similarly, work out the maximum possible value y¯jm of yjm.

Then, based on xi−11, yj−1m,x¯i1, y¯jm and the constraint conditions of Formulas (21) and (22), maximize the xi1,yjm or either of them.

If i−j=0, the constraint condition of Formula (21) must be considered. If y¯jm≤x¯i1+τ(s1,sm)+rm, schedule the down-direction train i and the up-direction train  j at the same time and make yjm=y¯jm,xi1=y¯jm−τ(s1,sm)−rm; if y¯jm>x¯i1+τ(s1,sm)+rm, preferentially schedule the down-direction train i, while the up-direction train  j will not be scheduled for the time being and make xi1=x¯i1.

If 0<i−j<Nm, there is no need to consider the constraint conditions of Formulas (21) and (22). Compare the scheduled arrival time x¯i1+τ(s1,sm) of the down-direction train i  with the scheduled departure time y¯jm of the up-direction train  j and select the smaller one as the current train to be scheduled preferentially, i.e. xi1=x¯i1 or yjm=y¯jm.

If i−j=Nm, the constraint condition of Formula (22) must be considered. If y¯jm<x¯i1+τ(s1,sm), preferentially schedule the up-direction train  j, while the down-direction train i will not be scheduled for the time being and make yjm=y¯jm; if y¯jm≥x¯i1+τ(s1,sm), schedule the up-direction train j and the down-direction train i at the same time and make xi1=x¯i1,yjm=x¯i1+τ(s1,sm).

If i−j<0, then j−1>i−1. According to the optimization rule of associative serialization and the constraint condition of Formula (21), xj−11 will be determined at the latest together with yj−1m. However, yj−1m has been determined in the assumed condition, while xj−11 has not yet been determined, which is contradictory. Therefore, i−j<0 will not happen.

If i−j>Nm, j−1+hm<i−1. According to the optimization rule of associative serialization and the constraint condition of Formula (22), xj−1+hm1 will be determined at the latest together with yj−1m. However, yj−1m has been determined in the assumed condition, while xj−1+hm1 has not yet been determined, which is contradictory. Therefore, i−j>Nm will not happen.

1. Termination conditions

When both xi1≥tED,yjm≥tEU are valid, the minimum number of train pairs n=max{i,j}=i is obtained. Just send the redundant trains at station sm to station s1 according to the minimum train headway τmin.

According to the above-mentioned algorithm thought and corresponding steps, design the solving algorithm for Formula (1)–(27) of model.

5.2 Optimization algorithm for bidirectional associative serialization of the latest departure time of trains

6. Optimization method of rolling stock circulation

6.1 Optimization model of rolling stock circulation

The sequence set of down-direction train number departing from station s1 is {i|i=1,2,⋯,n} and that of arrived up-direction train number is {j|j=1,2,⋯,n}. The rolling stock circulation problem is to determine the connection relationship of train numbers in the two directions. Each departing down-direction train from the originating station is either the up-direction train that arrived before or the train from yard p. We describe the rolling stock circulation problem with assignment problem.

Optimizing and working out the rolling stock circulation problem with the help of assignment problem is namely to optimize the assignment between {j|j=1,2,⋯,n} and {i|i=1,2,⋯,n}. The assignment meets the following restrictions: M⊂{(j,i)|j,i=1,2,⋯,n}. For any (j,i),(j′,i′)∈M, satisfy that if j=j′, then i≠i′; if i=i′, then j≠j′. For any j=1,2,⋯,n,i=1,2,⋯,n, define the assignment fee cji as follows.

(30)cji={xi1−(yjm+τ(s1,sm)),xi1−(yjm+τ(s1,sm))≥r1K,xi1−(yjm+τ(s1,sm))<r1

where K is a sufficiently large number, and K=24nh is usually taken.

In Formula (30), xi1−(yjm+τ(s1,sm))≥r1 indicates the required turning-around operation time r1 when the train arrives at or passes station s1 between the final arrival time of the up-direction train number j and the departure time of the down-direction train number i, which is sufficient to complete the train turning-around operation. Corresponding connection cost is time difference xi1−(yjm+τ(s1,sm)). xi1−(yjm+τ(s1,sm))<r1 indicates the required turning-around operation time r1 when the train fails to arrive at station s1 between the final arrival time of the up-direction train number j and the departure time of the down-direction train number i, which is insufficient to complete the turning-around operation of the train. Corresponding connection cost is K. Since the value of K exceeds the possible connection time of all train numbers, all train numbers with K as the connection cost are invalid assignments for (j, i). For these invalid assignments, all down-direction train numbers i come from yard p, and all up-direction train numbers j return to yard  p.

Define the assignment variable as follows:

(31)xji={1,(j,i)∈M0,(j,i)∉M

The assignment model for the establishment of rolling stock circulation problem is as follows:

(32)min∑j=1n∑i=1ncjixji

s.t.

(33)∑j=1nxji=1,   i=1,2,⋯,n

(34)∑i=1nxji=1,   j=1,2,⋯,n

(35)xji=0,1,         j,i=1,2,⋯,n 

Formulas (30)–(35) of the assignment model take the minimization of connection time as the optimization objective, which is equivalent to the minimum number of non-connectable trains, the minimum operating hours of all trains and then the minimum number of allocated passenger trains.

It is worth noting that the assignment model does not consider the train parking capacity N1 constraint of station s1, but as long as part of the effective assignment of the optimal solution M∗ is transferred to yard p for connection, the train parking capacity constraint of station s1 can be satisfied, i.e. work out M¯*⊂M* and satisfy

(36)yjkm+τ(sm,s1)≥xjk−h11 ,    k>h1,(jk,ik)∈M¯*

where (jk,ik)∈M¯* is generated by sorting the up-direction trains j in (j,i)∈M¯*.

The simplest way to solve M¯* is to sort the up-direction trains j in (j,i)∈M* first to obtain (jk,ik)∈M*, and then check whether Formula (36) is valid for k in turn. Only those (jk,ik)∈M* making Formula (36) valid are included in M¯*.

The objective function value obtained in this way will not change the minimum connection time of the assignment model, but different solving methods will have different number of round trips to and from yard p of station s1, so the minimization scheme of the number of round trips will not be discussed here.

6.2 Optimization algorithm of rolling stock circulation

Hungarian algorithm can be used to work out the optimal solution of assignment problem. Hungarian algorithm is used to work out the assignment model, which is divided into the following two steps.

• Step 1: Use the method for working out the optimal solution of assignment problem with Hungarian algorithm to solve the optimal assignment scheme M∗.

• Step 2: Work out the assignment scheme M¯* in yard p. Sort the up-direction trains j in (j,i)∈M* to get (jk,ik)∈M*, and then check whether Formula (36) is valid for k in turn. Only those (jk,ik)∈M* making Formula (36) valid are included in M¯*.

It is worth noting that in Step 1, what is obtained by Hungarian algorithm is the assignment scheme M* with the minimum connection cost and the minimum number of allocated passenger trains. In the matrix corresponding to the scheme, the row and column corresponding to each zero element correspond to a valid assignment (j,i)∈M, while the row and column corresponding to invalid assignment corresponds to up-direction train number j returning to yard p and down-direction train number i coming from yard p. Step 2: further consider the constraint of train parking capacity at the station of the end with yard and work out the assignment scheme M¯* of connection in yard p, so the situation of train entering and leaving the yard can be obtained.

7. Case study

Beijing Metro Line 5 was taken as an example to verify the method in this paper. There are 23 stations on the line, as shown in Figure 1. The down direction is from Tiantongyuan North to Songjiazhuang, and Taipingzhuang depot is at Tiantongyuan North Station. The dwell time of trains at Lishuiqiao, Datunlu East, Huixin Xijie Nankou, Yonghegong Lama Temple, Dongsi, Dongdan, Ciqikou and Puhuangyu Stations is 45 s, while the dwell time at other stations is 30 s. The section operation time is calculated with reference to the departure time and dwell time of the first train at each station, as shown in Figure 1. Therefore, the sum τ(su,sv) of travel time in each section (su,sv) and dwell time at station sv is deduced, in which the whole travel time is 3 065 s = 51 min 5 s. The maximum train passenger carrying capacity C=1 200 persons/train, the conventional passenger carrying coefficient α=0.7, the minimum and maximum train train headways are τmin=2.5min and τmax=15min. The turning-around operation time of station is r1=rm=2min, the parking capacity is N1=Nm=2 trains and the whole-day operation period is 4: 00-24: 00. Both the latest bidirectional departure time tLD,tLU of the first train is 6: 20; the earliest bidirectional departure time tED,tEU of the last train is 22: 30.

The actual O-D passenger flow data of the line on a certain day in 2014 is adopted as the time-varying demand. Due to the limited length, they are not listed in detail. In order to increase the intensity of passenger flow demand, O-D passenger flow demand is magnified twice as O-D passenger flow demand for the example.

The train operational plan obtained from the optimization method is as shown in Figure 2. In the figure, the line segment between station s1 and station sm is the train path. For brevity, the dwell time information along the way is not marked. The broken line between station s1 and the outside of station sm indicates the connection relationship of trains. The solid arrow outside the station s1 indicates that the train comes from or returns to the yard, and the hollow arrow indicates that the train is connected at the yard, so as to solve the difficulty that station s1 cannot meet the parking capacity N1. The combination of D and numbers indicates the train number in the down direction, and the combination of U and numbers indicates the train number in the up direction. In order to avoid too intensive marking of train number, the interval between train number marking is about ten trains.

According to the optimized train operational plan, 194 train pairs are operated, 62 trains are needed, the train connection time is 850.36 min and the number of round trips to and from yard is 124.

It can be seen from Figure 2 that the train operation frequency is intensive in the morning and evening peaks, the train headway changes with the change of passenger flow demand and the change rule is relatively smooth. The following train connection status, train headway and cause of dominant direction at turning-around station are analyzed as follows.

1. Train connection status of turning-around station

In order to analyze the train connection status of turning-around station sm, it can be seen from Figure 2 that the train connection status can be generally divided into three stages: the first stage is immediate turning-around, the second stage is continuous saturation of parking capacity and the third stage is immediate turning around.

By comparing the originating and terminating time of the bidirectional trains at the turning-around station sm, it is found that

The down-direction trains 1–36 and up-direction trains 1–36 are all connected by immediate turning round, i.e. the connection time is the turning-around operation time rm=2min. The connection time between the down-direction train 37 and the up-direction train 37 exceeds the turning-around operation time rm. After that, the connection time keeps increasing, and the turning-around station sm starts to accommodate the parking of temporarily unnecessary trains, and the saturation rate of parking capacity becomes larger and larger.

The departure of the up-direction train 44 releases the parking capacity of the turning-around station sm in saturation and ensures that the down-direction train 46 can finally arrive at station sm (according to the following finding: the terminating time of the down-direction train 46 is equal to the departure time of the up-direction train 44 from the originating station, but the terminating time of the down-direction train 45 is greater than the departure time of the up-direction train 43 from the originating station). After that, the turning-around station sm enters the continuous saturation state of parking capacity.

The final arrival of the down-direction train 104 ends the continuous saturation state of parking capacity (according to the following finding: the terminating time of the down-direction train 104 is slightly shorter than the departure time of the up-direction train 102 from the originating station, but the terminating time of the down-direction train 103 is equal to the departure time of the up-direction train 101 from the originating station). After that, the saturation rate of the parking capacity of the station sm becomes smaller and smaller and then completely unsaturated. The turning-around time becomes shorter and shorter, until the down-direction train 112 and the up-direction train 112 are still not connected in an immediate turning-around manner. The down-direction trains 113-194 and up-direction trains 113-194 are connected by immediate turning-around.

Immediate turning-around and continuous saturation of parking capacity indicate the demand dominance in different directions. Immediate turning-around means that the up direction is the dominant direction, i.e. the train operation in up direction follows the up demand, and the down direction provides trains for up direction in time. The continuous saturation of the parking capacity of the turning-around station means that the down direction is the dominant direction, i.e. the train operation in down direction follows the down demand, and the up direction releases parking capacity in time for down arrival turning-around station.

1. Train headway

In order to analyze the train headway, the change rule of the train headway of adjacent trains in up and down directions is as shown in Figure 3. In the figure, the i-th blue diamond sign marks the train headway between the down-direction train i and the down-direction train i+1, and the  j-th red plus sign marks the train headway between the up-direction train j and the up-direction train j+1.

It can be seen from Figure 3 that for the train headway curve of trains i=1,2,⋯,36, the change rule of the up/down direction is completely consistent with that of train i+1, except that the down direction is advanced by τ(s1,sm)+rm=53min5s, which is caused by the dominant up direction.

At this stage, the dominant position of the up direction ends with the arrival of the down-direction train 37. The demand of down direction increases, and the train headway decreases. There is a turning point in the curve of the train headway of the down-direction train, but the train headway of the up-direction train is still increasing. Until the final arrival of the up-direction train 43, the up and down-direction trains, respectively, determine the train headway according to their respective requirements, and the down-direction trains that arrive intensively and are temporarily unnecessary can be parked at the turning-around station sm for standby.

There is a sudden change in the train headway between the up-direction trains 43 and 44, i.e. the isolated point corresponding to the plus sign surrounded by a circle in Figure 3. At this time, the up-direction train 44 must depart to release the parking capacity of the turning-around station sm in saturation and ensure that the down-direction train 46 can finally arrive at station sm. After that, the departure time of the up-direction train i and the final arrival time of the down-direction train i+2 at the turning-around station sm remain equal, which reflects the dominant position of the down direction, and makes the train headway of the up-direction train consistent with that of the down-direction train.

At this stage, the dominant position of the down direction ends with the arrival of the down-direction train 104. The demand in the up direction increases, and the train headway decreases greatly, but the departure time of the down-direction train still decreases slowly. Until the final arrival of the down-direction train 112, the train headway between the up and down-direction trains shall be determined according to their respective requirements, and the gap between the up-direction train departure and the down-direction train arrival shall be filled by the train parked at the turning-around station s_m.

There is a sudden change in the train headway between the down-direction trains 112 and 113, i.e. the isolated point corresponding to the diamond sign surrounded by a circle in Figure 3. At this time, the down-direction train 113 must arrive at the turning-around station sm and serve as the up-direction train 113 in an immediate turning-around mode to ensure that the up-direction train 113 can depart on time from the originating station. After that, the train headway of the down-direction train is consistent with that of the up-direction train, which reflects the dominant position of the up direction.

1. Cause of dominant direction

The cause of dominant direction in each stage is related to the demand and the absence of yard at the turning-around station. The absence of yard at the turning-around station results in the demand of the up-direction train k lagging behind that of the down-direction train k for about 1 h, which makes it necessary to compare the demand of up/down direction based on misalignment. Therefore, the causes of dominant direction in the three stages are analyzed as follows.

In the first stage, the down-direction train is closer to the low ebb of morning shift, and the up-direction train is closer to the morning peak, which shows that the demand for up-direction train is greater, so the up direction is the dominant direction.

In the second stage, the down-direction train is closer to the morning peak and the up-direction train is closer to the low ebb at noon, which shows that the demand for down-direction train is greater, so the down direction is the dominant direction.

In the early third stage, the down-direction train is closer to the low ebb at noon, and the up-direction train is closer to the evening peak, which shows that the demand for up-direction train is greater, so the up direction is the dominant direction. In the later third stage, as the evening peak in the up direction lasts longer, the up direction is always the dominant direction. During the evening shift, all the up and down-direction trains depart at the maximum headway τmax=15min and naturally turn back immediately.

To sum up, the train connection status, train headway and the cause of dominant direction of each stage at the turning-around station all reflect the obvious rationality of the train operational plan, which is attributed to the optimization of the train operational plan combining the passenger flow distribution and service level, so the train operational plan is highly consistent with the passenger travel demand, and the number of train operation trips and the number of allocated passenger trains are minimized.

8. Conclusion

1. The optimization problem of train operational plan on URT lines can be described as a two-stage optimization problem of train timetable and rolling stock circulation based on service level, aiming to minimize the number of train operation pairs and the number of allocated passenger trains and optimize the train connection relationship at the end with yard. For a given train timetable, the passenger flow distribution of O-D time-varying demand can be obtained by recursion formula and thus the coupling between passenger flow demand and train timetable can be realized.

2. For URT lines with a single end yard, under the constraints of train connection and parking capacity at the end without yard and combined with the passenger flow distribution with O-D time-varying demand, the serialization optimization method can be adopted to maximize the train departure time step by step and realize the association optimization of bidirectional train timetable.

3. Based on the optimal train timetable, the rolling stock circulation problem at the end with yard is described as an assignment problem. An assignment model can simultaneously determine the optimal connection relationship of trains at the termination station and the trains to and from the yard.

4. In the train operational plan of URT lines with a single end yard, the change rule of train headway in the up-direction lags behind that in the down direction. In the time period when the up direction is dominant, the lag is slightly larger; in the time period when the down direction is dominant, the lag is slightly smaller.

Figures

Figure 1

Station and section operation time (Unit: s)

Figure 2

Schematic diagram of train operational plan of URT line

Figure 3

Schematic diagram of train headway