Optimization on metro timetable considering train capacity and passenger demand from intercity railways

Haiyang Guo (Key Laboratory of Transport Industry of Big Data Application Technologies for Comprehensive Transport, Ministry of Transport, Beijing Jiaotong University, Beijing, China)
Yun Bai (Anhui Transport Consulting and Design Institute Co. Ltd, Anhui, China)
Qianyun Hu (Anhui Transport Consulting and Design Institute Co. Ltd, Anhui, China)
Huangrui Zhuang (Key Laboratory of Transport Industry of Big Data Application Technologies for Comprehensive Transport, Ministry of Transport, Beijing Jiaotong University, Beijing, China)
Xujie Feng (MOT, China Academy of Transportation Sciences, Beijing, China)

Smart and Resilient Transportation

ISSN: 2632-0487

Article publication date: 1 February 2021

Issue publication date: 4 May 2021

Abstract

Purpose

To evacuate passengers arriving at intercity railway stations efficiently, metros and intercity railways usually share the same station or have stations close to each other. When intercity trains arrive intensively, a great number of passengers will burst into the metro station connecting with the intercity railway station within a short period, while the number of passengers will decrease substantially when intercity trains arrive sparsely. The metro timetables with regular headway currently adopted in real-world operations cannot handle the injected passenger demand properly. Timetable optimization of metro lines connecting with intercity railway stations is essential to improve service quality.

Design/methodology/approach

Based on arrival times of intercity trains and the entire process for passengers transferring from railway to metro, this paper develops a mathematical model to characterize the time-varying demand of passengers arriving at the platform of a metro station connecting with an intercity railway station. Provided the time-varying passenger demand and capacity of metro trains, a timetable model to optimize train departure time of a bi-direction metro line where an intermediate station connects with an intercity railway station is proposed. The objective is to minimize waiting time of passengers at the connecting station. The proposed timetable model is solved by an adaptive large neighborhood search algorithm.

Findings

Real-world case studies show that the prediction accuracy of the proposed model on passenger demand at the connecting station is higher than 90%, and the timetable model can reduce waiting time of passengers at the connecting station by 28.47% which is increased by 5% approximately than the calculation results of the generic algorithm.

Originality/value

This paper puts forward a model to predict the number of passengers arriving at the platform of connection stations via analyzing the entire process for passengers transferring from intercity trains to metros. Also, a timetable optimization model aiming at minimizing passenger waiting time of a metro line where an intermediate station is connected to an intercity railway station is proposed.

Keywords

Citation

Guo, H., Bai, Y., Hu, Q., Zhuang, H. and Feng, X. (2021), "Optimization on metro timetable considering train capacity and passenger demand from intercity railways", Smart and Resilient Transportation, Vol. 3 No. 1, pp. 66-77. https://doi.org/10.1108/SRT-06-2020-0004

Publisher

:

Emerald Publishing Limited

Copyright © 2020, Haiyang Guo, Yun Bai, Qianyun Hu, Huangrui Zhuang and Xujie Feng.

License

Published in Smart and Resilient Transport. Published by Emerald Publishing Limited. This article is published under the Creative Commons Attribution (CC BY 4.0) licence. Anyone may reproduce, distribute, translate and create derivative works of this article (for both commercial and non-commercial purposes), subject to full attribution to the original publication and authors. The full terms of this licence maybe seen at http://creativecommons.org/licences/by/4.0/legalcode


1. Introduction

Intercity railway stations which combine National Railway, public transports and pedestrians are the primary sites for passengers mustering and evacuation. Affected by the arrivals of intercity trains, a large number of passengers could arrive at intercity railway stations intensively. It is essential to match the metro timetable and the arrival times of intercity trains in a good manner, to reduce the waiting time of passengers and evacuate passengers mustering at intercity railway stations timely (Chen, 2010).

In daily operation, most metro lines adopt peak/off-peak based timetables. However, for metro lines connecting with intercity railway stations, whose inbound passenger flow varies significantly over a short period due to the discrete arrivals of intercity trains, regular timetables might increase waiting time of passengers (Sun et al., 2014). Therefore, it is necessary to optimize timetable of such metro lines according to the time-varying passenger demand at the connecting station.

In the domain of demand-oriented metro timetable optimization, Barrena et al. (2014a, 2014b) proposed timetable optimization model under dynamic passenger demand, Niu and Zhou (2013), Niu et al. (2015a), Niu et al. (2015b) analyzed waiting behaviors of passengers at stations and constructed timetable optimization model with the aim of minimizing passenger waiting time. While, above studies did not take transfer behaviors of passengers into account. Wu et al. (2015) put forward a model to minimize total waiting time of passengers including transfer passengers in a metro network. It only considered passengers transferring between different metro lines, however. Besides, passenger demands considered in above researches were all obtained through analyzing historic data because passenger demands are similar in working days. For metro lines connecting with intercity railway stations, a slight change in arrival times of intercity trains can have a significant impact on passenger demand at the connecting station. Therefore, historic data of connecting stations is not universal and a passenger demand forecast model based on arrival times of intercity trains is called for.

Hu et al. (2016) built a train departure time optimization model for a metro line whose start station is connected to an intercity railway station, on the basis of characterizing the time-varying demand of passengers transferring from intercity trains to metros. Whereas, the transfer passenger demand predication model proposed did not take into account the influence of transfer facility layout. Also, the developed timetable model is only practical for single-direction metro lines where the start station is the connecting station and the capacity of metro trains can be neglected. It is not adaptable enough for a metro line where an intermediate station is connected to an intercity railway station.

To solve this problem, this paper puts forward a model to predict the number of passengers arriving at the platform of connection stations via analyzing the entire process for passengers transferring from intercity trains to metros. Furthermore, a timetable optimization model aiming at minimizing passenger waiting time of a metro line where an intermediate station is connected to an intercity railway station is proposed. At last, an ALNS algorithm is developed to find the optimal solution of the proposed model.

2. Model on transfer passenger demand predication

The entire process for passengers transferring from intercity trains to metros is shown in Figure 1. According to arrivals of intercity trains and the transfer process of passengers, a model for calculating the number of passengers taking escalators and stairs, which are located at platforms of an intercity railway station is proposed firstly, and the calculation result is regarded as the passenger flow input. Then, take the impact of each transfer facility (i.e. escalators/stairs, exit gates etc). into account and adjust the input passenger flow distribution orderly until the number of passengers arriving at the connecting station platform is obtained.

Transfer facilities considered of the transfer process are divided into two types: node facilities and facilities with branches. Facilities with branches are where two parallel facilities are provided for passengers to pass the same area, including escalators/stairs in addition with buying tickets at the station/using smart cards. Node facilities are those with capacity constraints, like exit gates of intercity railway stations and security check points of metro stations. It is worth noting that escalators/stairs are also node facilities where passengers are influence by capacity constraints after making choice between escalators and stairs.

2.1 Passenger flow input

It is very likely that more than one train get to the intercity railway station during the study period [0, T]. Therefore, the number of input passengers is calculated by the sum of passenger distribution of multiple trains:

(1)  C(t)=k=1KAk(t)
where C(t) is the total number of input passengers at time t; Ak (t) is the number of input passengers for train k at time t; K is the total number of intercity trains getting to the station during study period [0, T].

In general, transfer passengers spend different time walking from intercity trains to escalators/stairs which are located at platforms of an intercity railway station. According to the Henderson’s research that walking speed of passengers follows normal distribution whose mean is μ, standard deviation is σ (Henderson, 1971). With the distribution of passenger walking speed and walking distance of passengers, the distribution of passenger walking time can be calculated. Substitute the capacity of intercity trains, the number of input passengers for train k at time k is calculated by:

(2) Ak(t)=QkH(μ,δ,t,lk)
(3) Qk=Pk×ε
where Qk is number of transfer passengers from train k reaching the intercity railway platform; H is the distribution of passenger walking time; lk is the average distance for passengers walking from train k to escalators/stairs on the intercity railway platform; Pk is the capacity of train k; ε is the load factor of intercity trains.

2.2 Facilities with branches

Facilities with branches are where passengers need to make choice according to their conditions. For example, they need to decide whether to take escalators or stairs, whether to buy tickets at the station or use smart cards directly. Investigations on passengers using facilities with branches infer that it takes passengers nearly the same time to go through escalators and stairs, while the time they spent on buying tickets at the station is longer than using smart cards. As a result, the number of passengers choosing escalators and stairs is calculated, respectively, by:

(4) L1(t)=aL0(t)
(5) L2(t)=(1α)L0(t)
where L1(t) is the number of passengers choosing stairs at time t; L2(t) is the number of passengers choosing escalators at time t; L0(t) is the number of passengers who intend to take escalators/stairs; α is the proportion of passengers who choose stairs.

The number of passengers passing AFC is calculated by:

(6) S(t)=bS0(t)+(1b)S0(tt0)
where S(t) is the number of passengers going through AFC at time t; S0(t) is the number of passengers intend to use AFC machines; b is the proportion of passengers passing AFC machines directly with smart cards; t0 is the service lag time for passengers buying tickets at the station instead of using smart cards.

2.3 Node facilities

Generally speaking, passengers who intend to take escalators will move to stairs when the entry of escalators is too crowded. Therefore, considering the capacity constraints of escalators/stairs, the number of passengers choosing stairs and escalators is re-calculated, respectively, by:

(7)  L1(t)=L1(t)+max{0, η(L2(t)c2)}
(8) L2(t)=L2(t)max{0,(1 η)(L2(t)c2)
where η is the number of passengers who change their choice and decide to take stairs rather than escalators; c2 is service capacity of escalators.

Based on the re-calculated L1(t) and L2(t), the number of passengers going through stairs and escalators is expressed by:

(9) L3(t+1)=min{L1(t+1)+max{0, L1(t)c1}, c1}
(10) L4(t+1)=min{L2(t+1)+max{0, L2(t)c2}, c2}
where L3(t) is the number of passengers going through stairs at time t; L4(t) is the number of passengers going through escalators at time t; c1 is the capacity of stairs; c2 is the capacity of escalators.

Exit gates and security check points have similar effect on the distribution of passenger flow, which is expressed respectively by:

(11) J1(t+1)=min{J0(t+1)+max{0, J0(t)c3}, c3}
(12) G1(t+1)=min{G0(t+1)+max{0, G0(t)c4}, c4}
where J1(t) is the number of passengers passing security check points at time t; G1(t) is the number of passengers getting through exit gates at time t; J0(t) and G2(t) are the number of passengers who intend to be through security check points and exit gates, respectively.

3. Timetable optimization model and solution methodologies

For a bi-direction metro line, number its stations sequentially from the up direction to the down direction as Figure 2 shows. Although station 1 and station 2 N, station 2 and station 2 N –1, ……, station N + 1 and station N refer to the same station in terms of geographic location, they are numbered separately to make the timetable model more understandable. Station n, that is station 2 Nn +* 1, is the metro station which connects to an intercity railway station.

3.1 Objective function

Divide the study period [0, T] into a host of time intervals denoted by t (t = 1,2,3,4…). Assume that all passengers arrive at metro stations at the end of each time interval, and all metro trains start their operation from the terminal station where the depot is located and turn around at the other terminal station. To evacuate passengers that get to the platform of connecting stations, this paper takes minimizing passenger waiting time at connecting stations as the objective of the timetable optimization model and it is calculated by:

(13) minW=W1+W2
(14) W1=j=1Kv=n+12Nt(Lj1n, Ljn]Pn,v(t)(TDjnt)
(15) W2=j=1Kv=2Nn+22Nt(Lj12Nn+1, Lj2Nn+1]P2Nn+1(t)(TDj2Nn+1t)
where W1 is the waiting time of passengers at the connecting station when traveling toward up direction; W2 is the waiting time of passengers at the connecting station when traveling toward down direction; Pn,v(t) is the number of passengers traveling from connecting station n to station v; TDjn is the time when train j departs from station n; K is the total number of trains departing from the start terminal during the study period; Ljn is the effective loading time of train j at station n.

Based on train departure times at the first station, running times at sections and dwell times at stations, train departure times at the connection station on up direction and down direction are expressed by:

(16) TDjn=TDj1+u=1ndju+u=1n1rju
(17) TDj2Nn+1=TDj1+u=12Nn+1dju+u=12Nnrju
where dju is the dwell time of train j at station u; rju is the running time of train j from station u to station u + 1.

3.2 Constraints

Whether passengers waiting on a platform can board the oncoming train successfully depends on the available loading capacity of the train. To determine the number of passengers who can board the train, effective loading time is introduced, that is the critical time that the number of passengers onboard reaches the maximum loading capacity. The effective loading time for train j is at station u is calculated by:

(18) Lju=min{TDju,max{τt(Lj1, τu]v=u+12NPu,v(t)CRju1+u=1u1Bju,u}}
(19) Bju,v=t(Lj1u, Lju]Pu,v(t)
(20) Qju=Rju1uu1Bju,u
(21) Rju=Qju+v=u+12NBju,v
where Bju,v is the number of passengers traveling from station u to v who board train j successfully; Qju is the number of passengers left on train j after some passengers get off at station u; Rju is the number of onboard passengers after train j departs from station u; C is maximum loading capacity of metro trains.

To cover all passenger demand over the study period [0, T], departure times of the first train and the last train are pre-determined, which are denoted by:

(22) TD01=0
(23) TDK+11=T

Constraints of the headway between two adjacent trains are calculated by:

(24) hminTDj1TDj11hmax
where hmin is the minimum headway; hmax is the maximum headway.

3.3 Solution methodologies

For the proposed timetable optimization model which has a large solution space, the Adoptive Large Neighborhood Search (ALNS) method is adopted. ALNS is a kind of metaheuristic method, based on destroy and repair operators randomly selected as each iteration via roulette wheel mechanism. The probability of each operator to be choose depends on their past performance (fitness value).

To be specific, weights ωi and scores si of operators are introduced to the algorithm, which are initially set to ones and zeros respectively. At each iteration, the score of the selected operator will be increased by σ1 if it finds a new best solution, by σ2 if it finds a solution better than the incumbent or by σ3 if the solution is not better but still accepted. After a certain number of iterations, the weights of operators which determine the probability of selection, will be updated by considering their scores. After the update, all scores are reset to zeros. Thus, the term “adoptive” in ALNS refers to the process of selection of more effective operators based on their past performance.

The acceptance criterion is based on simulated annealing. That is for a given solution s, a neighbor solution s' is always accepted if f(s′) < f(s), and otherwise can be accepted with the probability of e −(f(s′) < f(s))/τ, where f(s) is the fitness value and τ > 0 is the current temperature. The start temperature is τstart which decreased by a cooling rate factor ∅ for each iteration. The iteration stops when τ is lower than the end temperature τend. The whole process of the algorithm is shown in the Figure 3.

The destroy operators adopted in this paper are as follows: randomly select and remove ρ train services; identify the two consecutive trains with the smallest interval and removes the earlier one, this procedure repeats ρ times; and remove the train with smallest passenger demand in one of its tracks, which repeats ρ times.

The repair operators adopted include: randomly select ρ time instants of departure time at the first station and insert ρ train services; insert a train randomly in the largest inter-departure interval, which repeats ρ times; and insert a train just before the train with the largest passenger demand, which repeats ρ times.

4. Case studies

The developed transfer passenger demand predication model and timetable optimization model are applied to Beijing Metro Line 9 where an intermediate station called Beijing West Metro Station connects to Beijing West Railway Station. The study period is 12:30–14:00 on a working day when intercity trains get to Beijing West Railway Station intensively.

4.1 Passenger demand predication of the connecting station

Based on investigations on the entire process for passengers transferring from intercity trains of Beijing West Railway Station to Beijing Metro Line 9, parameters of the passenger demand predication model are obtained, which are shown in table 1.

As Beijing Metro Line 9 and Beijing Metro Line 7 are both connected with Beijing West Railway Station, this paper assumes that half of the passengers who intend to transfer from intercity trains to metros take Beijing Metro Line 9. Based on arrival times of intercity trains at Beijing West Railway Station over the study period and above parameters, the result of passenger demand predication is shown in Figure 4.

4.2 Accuracy of passenger demand predication

Compare the accuracy of passenger demand predication in this paper to that calculated by Hu in 2016 under different length of time intervals. As Table 2 shows, the predication model proposed in this paper has a smaller error and this advantage becomes more significant as the time interval becomes longer.

4.3 Timetable optimization of Beijing metro line 9

Input the results of passenger demand predication at the connecting station to the timetable optimization model and use the ALNS algorithm to find the solutions. In our implementation, to achieve a maximum number of iterations imax of 70000, we set the start temperature τstart = 60000, the end temperature τend = 0.01 and the cooling rate ϕ=(τend/τstart)1/imax=0.9998. Scores are updated with σ1 = 10, σ2 = 5 and σ3 =2. The weights and scores are updated every 200 iterations. The minimum passenger waiting time calculated at each iteration is shown in Figure 5.

The optimized timetable and the calculated passenger demand at the connecting station are shown together in Figure 6. It can be seen that compared to the timetable with even headway, the optimized timetable can match the injected passenger demand of the connecting station more properly as it dispatches more metro trains during the periods when passengers arrive intensively, which can remit the shortage of transport capacity meanwhile avoid the waste of capacity when the number of passengers is not that large.

Table 3 represents passenger waiting time of current timetable and the optimized timetable. It is found that the optimized timetable reduces passenger waiting time at the connecting station by 28.47%, which is increased by 5% than the calculation results of the generic algorithm (Guo et al., 2020). Although the passenger waiting time at other stations increases by 2%, it is too low to affect riding experience of passengers. It is also noted that saving rate of passenger waiting time is higher when train capacity is neglected. However, this situation is not realistic, and the maximum load factor will be about 138.94% if operating trains under this condition. If train capacity is considered, the maximum load factor is only 97.63%, which is restricted well within 100%. As a result, the congestion on metro trains can be relieved and service quality for passengers can be improved.

5. Conclusions

Focusing on the metro line where an intermediate station connects with an intercity railway station, a mathematical model is proposed to predict the number passengers getting to the platform of the connecting station through analyzing the entire process for passengers transferring from intercity trains to metro trains. Compared to the existing research, the passenger demand predication model in this paper is more accurate.

According to the calculated passenger demand, a timetable optimization model with the aim of minimizing passenger waiting time at a connecting station is established and solved by ALNS algorithm. Real-world case studies indicate that the optimized timetable can reduce passenger waiting time at the connecting station by 28.47% with negligible influence on passengers at other stations. The saving rate is increased by 5% than that of the generic algorithm.

The timetable optimization model proposed in this paper takes train capacity into account, which improves service quality for passengers to some extent. However, this paper only considers the case that a metro line connects with an intercity railway station. However, some intercity railway stations connect with several metro lines. How to optimize their timetables coordinately will be introduced in the further work.

Figures

Process for passengers transferring from intercity trains to metros

Figure 1.

Process for passengers transferring from intercity trains to metros

Representation of a metro line

Figure 2.

Representation of a metro line

Flowchart of the adopted ALNS algorithm

Figure 3.

Flowchart of the adopted ALNS algorithm

Calculated passenger demand at Beijing West Metro Station

Figure 4.

Calculated passenger demand at Beijing West Metro Station

Minimum passenger waiting time at each iteration

Figure 5.

Minimum passenger waiting time at each iteration

Optimized timetable and the calculated passenger demand at the connecting station

Figure 6.

Optimized timetable and the calculated passenger demand at the connecting station

Parameters of the passenger demand predication model

Parameters Value
μ Average walking speed 1.34 m/s
δ Standard deviation 0.26
c1 Capacity of stairs 54 Pax/10s
c2 Capacity of escalators 54 Pax/10s
c3 Capacity of security points 45 Pax/10s
c4 Capacity of exit gates 96 Pax/10s
ε Load factor of intercity trains 70%
α Proportion of passengers taking stairs 0.25
b Proportion of passengers using smart cards 0.60

Accuracy comparison of passenger demand predication models

Time interval (minutes) Average error
This paper (%) Hu et al. (2016) (%)
0.5 8.36 10.12
1 7.96 10.07
2 7.52 8.25
5 5.07 5.66
10 4.20 4.55

Passenger waiting time of current timetable and the optimized timetable

Train capacity Considered Neglected
Passenger waiting time at the connecting station
Current timetable 24,490 23,943
Optimized timetable 17,517 18,064
Saving rate (%) 28.47 24.55
Passenger waiting time at other stations
Current timetable 22,562 22,562
Optimized timetable 23,014 23,050
Saving rate (%) −2 −2.16
Average load factor (%) 84.38 93.56
Maximum load factor (%) 97.63 138.94

References

Barrena, E., Canca, D., Coelho, L.C. and Laporte, G. (2014a), “Single-line rail rapid transit timetabling under dynamic passenger demand”, Transportation Research Part B: Methodological, Vol. 70, pp. 134-150.

Barrena, E., Canca, D., Coelho, L.C. and Laporte, G. (2014b), “Exact formulations and algorithm for the train timetabling problem with dynamic demand”, Computers and Operations Research, Vol. 44 No. 3, pp. 66-74.

Chen, J.F. (2010), Study on Transfer between Railway Passenger Station and Urban Mass Transit, Beijing Jiaotong University, Beijing, (in Chinese).

Guo, H., Bai, Y., Hu, Q., Zhuang, H. and Feng, X. (2020), “Optimization on metro timetable considering train capacity and passenger demand from intercity railways”, Proceedings of the 4th International Conference on Electrical and Information Technologies for Rail Transportation (EITRT) 2019.

Henderson, L.F. (1971), “The statistics of crowd fluids”, Nature, Vol. 229 No. 5284, pp. 381-383.

Hu, Q., Yun, B., Yunwen, C., Yao, C. and Zhijie, C. (2016), “Optimization of subway timetable at the railway-subway transfer station”, Journal of Railway Science and Engineering, Vol. 13 No. 12, pp. 2503-2507 (in Chinese).

Niu, H. and Zhou, X. (2013), “Optimizing urban rail timetable under time-dependent demand and oversaturated conditions”, Transportation Research Part C: Emerging Technologies, Vol. 36, pp. 212-230.

Niu, H., Tian, X. and Zhou, X. (2015a), “Demand-driven train schedule synchronization for high-speed rail lines”, IEEE Transactions on Intelligent Transportation Systems, Vol. 16 No. 5, pp. 2642-2652.

Niu, H., Zhou, X. and Gao, R. (2015b), “Train scheduling for minimizing passenger waiting time with time-dependent demand and skip-stop patterns: nonlinear integer programming models with linear constraints”, Transportation Research Part B: Methodological, Vol. 76, pp. 117-135.

Sun, L., Jin, J.G., Lee, D.H., Axhausen, K.W. and Erath, A. (2014), “Demand-driven timetable design for metro services”, Transportation Research Part C: Emerging Technologies, Vol. 46, pp. 284-299.

Wu, J.J., Liu, M.H., Sun, H.J., Li, T.F., Gao, Z.Y. and Wang, D.Z.W. (2015), “Equity-based timetable synchronization optimization in urban subway network”, Transportation Research Part C: Emerging Technologies, Vol. 51, pp. 1-18.

Acknowledgements

This work was supported by the National Natural Science Foundation of China (71971016).

Corresponding author

Haiyang Guo can be contacted at: 17120803@bjtu.edu.cn