Passenger Demand-Oriented High-Speed Train Stop Planning with Service-Node Features Analysis

Abstract

As a critical foundation for train traffic management, a train stop plan is associated with several other plans in high-speed railway train operation strategies. The current approach to train stop planning in China is based primarily on passenger demand volume information and the preset high-speed railway station level. With the goal of efficiently optimising the stop plan, this study proposes a novel method that uses machine learning techniques without a predetermined hypothesis and a complex solution algorithm. Clustering techniques are applied to assess the features of the service nodes (e.g., the station level). A modified Markov decision process (MDP) is conducted to express the entire stop plan optimisation process considering several constraints (service frequency at stations and number of train stops). A restrained MDP-based stop plan model is formulated, and a numerical experiment is conducted to demonstrate the performance of the proposed approach with real-world train operation data collected from the Beijing-Shanghai high-speed railway.

This work is licensed under http://creativecommons.org/licenses/by/4.0/ (the “License”). Notwithstanding the ProQuest Terms and Conditions, you may use this content in accordance with the terms of the License.

1. Introduction

In most countries, high-speed railway (HSR) is significant in daily life owing to its reliability, safety, low emissions, and energy savings. Due to increasing passenger demand and the growing high-speed railway network scale, the transport organisation becomes increasingly complex. However, train operation management must be maintained at an acceptable efficiency level. The train stop plan is a key element in the operation plan for satisfying the increasing passenger demand and reducing the operational costs of the railway company. The stop plan can impact the frequency of train service and the load of trains at each station, which directly influences transportation resource utilisation. Assad [1] presented the train operation plan as an optimisation problem with hierarchical structures. As a critical part of the train operation plan, the train stop planning (TSP) problem was first proposed by Patz [2]. Generally, it is considered as a subproblem of the train operation plan. As a critical link in the structure of train operational management plans, the stop plan is strongly correlated with route, stop pattern, travel range, number, type, and level of all involved trains. It focuses on determining three primary variables: stations served by each train, number of stops for each train, and service frequency at each station.

With a limited train fleet size and station capacity, it is critical for the stop plan to simultaneously consider passenger demand and train stop patterns, with the goal of achieving service-demand equilibrium with the given transportation resources. A contradiction always exists in the TSP problem: a sufficient number of train stops are required for serving passengers along the railway line, but too many train stops result in reduced operating efficiency and low resource utility. Railway companies must find an effective means of balancing transportation costs and varying passenger demand.

The TSP provides a critical foundation for a complete train timetable for the entire railway network, especially for railway systems that cannot compute the timetable directly due to the scale of operations. In China, the TSP is practically determined based on passenger volume prediction and the preset station level, an indicator of the significance of each station. This is a convenient way to quickly find a solution; the subjective station levels may implicitly include abundant information. However, with changing society and economics along the railway, this parameter is not updated fast enough and can lead to an unreasonable train stop plan solution. As a basic decision support plan, the train stop plan is typically underestimated in the literature (see Section 2). Thus, in our train stop plan study, we consistently consider railway properties, such as travel distance, train fleet size, types of trains, and service-node features, such as scale, population, and economics, and examine how these factors jointly influence the train stop plan solution. To resolve this issue, a data-mining approach is applied using the railway and a service-node factors dataset to analyse the station level, an important foundation for making a stop plan. A modified Markov decision process (MDP), called as RMDP stop plan model, is proposed to explore the best policy for the stop plan using all the train operation data through iterative training and feedback based on the station level.

This study makes contributions in the following areas: (i) railway properties and city features are listed as input parameters to better reflect environmental influence and improve train stop plan quality, (ii) a data-mining technique is applied to explore the station level through quantitative analysis of effective features using a dataset from the Beijing-Shanghai high-speed railway, and (iii) a restrained Markov decision process (RMDP) is proposed to find the optimal policy to achieve a better train stop plan.

The remainder of this paper is organised as follows: Section 2 reviews the recent literature related to the train stop plan problem; Section 3 introduces the problem background and framework of stop plan and proposes a stop plan scheduling model based on reinforcement learning approach; the experiment and numerical results are presented in Section 4; and conclusions and future research are presented in Section 5.

2. Literature Review

The hierarchical structure of the train operation plan comprises the following sequential subproblems: train operation zone, stop schedule (including train stop planning and train time tabling), rolling stock, and crew scheduling [3, 4]. Generally, train stop plans are considered synthetically with other subproblems in train operation plans [5–8]. Recently, Niu et al. [9] constructed an optimal model considering train stop planning and time tabling for minimising passenger waiting time to balance the time-dependent demand. Yang et al. [10] developed an optimisation method for both train stop planning and train scheduling problems to provide collaborative operation strategies. Altazin et al. [11] aimed to minimise the recovery and waiting times of passengers with a multiobjective model considering the stop schedule. Wang et al. [12] studied the integration of train scheduling and rolling stock circulation planning under time-varying passenger demand. Qi et al. [4] considered dynamic passenger flow and proposed a robust optimisation model for train time tabling and stop planning. Zhu and Goverde [13] formulated a timetable rescheduling model with flexible stopping and flexible turning considering retiming, reordering, and cancelling. The TSP problem is commonly combined with other subproblems.

However, the stop plan is always simplified or taken as one known input condition. Such treatment, albeit idealistic, may ignore the influence of the stop plan on actual operation. The stop plan is also an important subproblem related to passenger service quality and is influenced by a series of factors (e.g., stop stations and station service frequency). Thus, the TSP problem must be considered.

A few studies have focused on the pure TSP problem. Li et al. [14] proposed a model to minimise the total number of trains stopping and the node service frequency with a constraint of the number of trains stopping. Niu et al. [15] formulated an optimal model considering uncertain passenger flow demand at each station to minimise the total stop times of all trains. Xu et al. [16] focused on balancing the number of trains between major station stops and high frequency stops, aiming to minimise the total passenger time loss generated from both train stops and transfers. However, most of these studies focused on the optimisation model construction based on varying factors.

The solution algorithm design is another critical component of the optimisation problem, with complex factors, scale of variables, and constraints. With regard to optimisation model studies, this type of problem is always NP hard, even with certain idealistic parameter assumptions that lead to unstudied variables without empirical analysis and time-consuming searching for appropriate solutions for the TSP problem [4].

The reinforcement learning approach is an alternative to the optimisation method for solving TSP and is widely used in decision problems [17–19]. However, to the best of our knowledge, limited studies have applied reinforcement learning to solve TSP.

3. Methodologies

3.1. Problem Description

With station location, station capacity, passenger demand, train operational zones, train travel distance, fleet size, number of stops, skip-stop strategy, and train type as railway operation inputs and administrative level, population, and GDP of cities as environmental inputs, our study aims to generate a capacity-equilibrium train stop plan with the best trade-off between quality of passenger transportation service and rail operation cost. A stop plan regulates the stop pattern of each train in a railway line, stopping or not stopping for passenger boarding/alighting at each station.

Train stop planning must always select some stations for each train based on passenger demand. Although increased train stops provide better passenger service, they also lead to reduced transportation efficiency (increase in travel time, less train throughput, and mismatching service supply). We introduce a clustering analysis and a modified Markov decision process-based framework to consider the railway and its environmental factors to determine a coordinated train stop plan solution that uses reasonable transportation resources and adequately satisfies the passenger demand.

3.2. Solution Framework

To solve the TSP problem, a machine learning-based two-stage solution framework is developed to gain insights into the impacts of the station characteristics and formulate a new model to achieve the optimal stop plan. In the first stage, unsupervised clustering analysis is applied to explore the railway properties and service-node features along the railway line to classify the stations; this is the primary input of the TSP problem. In the second stage, a restrained Markov decision process (RMDP) is used to optimise the high-speed railway stop plan. The framework is shown in Figure 1.

[figure omitted; refer to PDF]

Generally, a greater number of stops at stations and for trains increases passenger convenience. However, it always leads to a higher capacity occupation, increased operation costs, and increased total travel time. Thus, both constraints are important for balancing the operation cost and service quality.

For the quality of passenger service, passenger demand is an indispensable factor influencing the maximum number of stops at each station. Hence, we must consider another parameter: the train stop rate of station z, denoted as ${\gamma }_z$, which is connected between the maximum number of stations and the passenger flow. It is expressed as$$\begin{array}{}\text{(10)}& {\gamma }_z=\frac{f_1+f_2}{\rho }\cdot \alpha \cdot {\beta }_z,\end{array}$$where $f_1$ and $f_2$ are the passenger flow departures from station $i$ and arriving at station $i$, respectively. $\rho$ is the passenger flow density of the section. The coefficient $\alpha$ is valued by the average number of stops by the same type of trains, which is often set by the railway department. ${\beta }_z$ is the weight coefficient based on the station level expressed as$$\begin{array}{}\text{(11)}& {\beta }_z=\frac{F_z}{{{\displaystyle \sum }}_{j=1}^Z{F}_j}.\end{array}$$

We can obtain the maximum stop time for each station $q_z={\gamma }_z\times Q$, where Q is the maximum number of stations.

For the capacity-equilibrium utilisation, the maximum number of stops of each train plays a significant role in the operation. It is always set pragmatically, considering the train type and the total train quantity.

In each epoch, the state parameters remember the temporal number of stops for each station and the temporal combined number of stop schemes. All state parameters are updated with the state transition until $n_z$ and $w_t$ meet the maximum number of stops at station z in stop scheme $w_T$.

Each action related to a substate set including several stop schemes satisfies the constraints. However, only one state is related to an action during a common MDP. Thus, we selected one stop scheme from the substate set for each action. To maintain the system performance, it is effective to calculate the instant rewards for an action to choose the best stop scheme from all the alternatives in the substate set. Denote $r_{m}s,a$ as the instant reward of the m-th stop scheme in the substate set referring to action a in current state $s$. The selected scheme is expressed as$$\begin{array}{}\text{(12)}& \max r_{m}s,a,\hspace{1em}m\in 1,\dots ,\text{M},\end{array}$$where M is the maximum stop scheme order in the substate set of action a. The stop scheme with the maximum instant reward is selected corresponding to action a. The entire process is shown in Figure 3. The algorithm of reward (instant reward or assigned reward) is introduced later. After the filter process, the adaptive state set for the next epoch is prepared.

[figure omitted; refer to PDF]

Comparing the solution with the original stop plan shown in Table 5, the optimal plan generated by the RMDP model is scheduled to stop at 2% lower than the original plan. Considering that train stops result in operational expense, the proposed optimal method is capable of reducing the total operation cost.

Table 5

Stop plan comparison.

No.	OD	Number of stop schemes		Total number of stops
		Original	Optimal	Original	Optimal
1	BJS-SHHQ	56	52	576	567
2	BJS-XZE	2	2	21	20
3	BJS-JNW	3	4	21	20
4	BJS-NJS	5	5	42	48
5	BJS-ZZ	1	1	9	9
6	TJW-SHHQ	7	7	66	66
7	JNW-SHHQ	4	4	48	41
	Total	78	75	785	771

The equilibrium index distributions for all trains in the two stop plans are shown in Figure 8. For simplicity, the average equilibrium indices of the two stop plans were also plotted. It is observed that the trains in the optimal strategy are in a higher region than those in the original plan. Thus, the trains in the optimal strategy with a greater average equilibrium index correspond to better service frequency for each station. This is also an improvement in passenger travel convenience.

[figure omitted; refer to PDF]

With the given passenger flow demand, the equilibrium index of passenger flow can be obtained for both stop plans shown in Figure 9. As shown in Figure 9(a), the change rate of the curve of the original plan is considerably sharper than that of the optimal strategy. It can be estimated by the variance in the passenger flow for both results shown in Figure 9(b). With the new approach, the train capacities are utilised more efficiently in each section. It is beneficial to reduce wasted train capacity and overcrowding. Reducing the wasted train capacity could increase the passenger load factor; reducing overcrowding could improve the sense of comfort. This suggests that the optimal stop plan could provide much higher revenue and a higher quality of service for passengers.

[figures omitted; refer to PDF]

To further analyse the relationship between the number of stops (ST) under the proposed approach and its related features (including population, passenger demand, and GDP), the standard distributions of the features in each station are plotted in Figure 10(a). Because of the fixed value of the city administrative level, the effect of the change in number of stops can be ignored. Hence, we only consider the other features. Figure 10(a) shows that the trend of these features is similar to the trend of the number of stops. However, the passenger demand is closer to the number of stops, which can be verified by Figure 10(b). It is observed that the variance is a minimum between the passenger demand and the number of stops. This result indicates that the optimal strategy is more adaptable to the passenger demand that is beneficial to facilitate revenue from increased efficiency.

[figures omitted; refer to PDF]

5. Conclusion

This study applied clustering analysis and MDP machine learning techniques to analyse the significant features related to the stop plan and proposed a data-driven optimal framework for a train stop plan based on real-world train operational data. Service-node features are adopted as important characteristic station elements. To make the qualitative features more effective, a clustering analysis technique was used to develop a quantitative analysis that can be applied directly to the optimal model. Different average feature values of clusters correspond to different station levels. Accordingly, the stop plan was optimised by continuing epochs that were described with an RMDP model that considered some constraints related to stop planning with the known passenger demand and the per-obtained total number of trains for each OD. A restrained MDP-based stop plan model was proposed to improve the stop plan using the relative value iteration algorithm. A case study was performed on the Beijing-Shanghai high-speed railway line. The computational results revealed that the optimal train stop plan solution is better than the original plan in terms of operation cost control, service quality improvement, and passenger demand adaptiveness. Furthermore, the proposed approach can efficiently solve the stop plan problem with a simpler solution algorithm.

In future research, we will use this approach as the foundation to adjust the stop plan and combine the stop schedule to explore the interaction relationship and the train time tabling problem. We also intend to investigate different machine learning methods, to achieve solution improvements and faster computation.

Acknowledgments

This work was supported by the National Key Research and Development Plan (grant no. 2017YFB1200701) and the National Natural Science Foundation of China (grant no. U1834209).

References

[1] A. A. Assad, "Modelling of rail networks: toward a routing/makeup model," Transportation Research Part B: Methodological, vol. 14 no. 1-2, pp. 101-114, DOI: 10.1016/0191-2615(80)90036-3, 1980.

[2] A. Patz, "Die richtige auswahl von verkehrslinien bei großen strassen bahnnetze," Verkehrstechnik, vol. 1925, pp. 50-51, 1925.

[3] F. Shi, S. Zhao, Z. Zhou, P. Wang, M. G. H. Bell, "Optimizing train operational plan in an urban rail corridor based on the maximum headway function," Transportation Research Part C: Emerging Technologies, vol. 74, pp. 51-80, DOI: 10.1016/j.trc.2016.11.007, 2017.

[4] J. Qi, V. Cacchiani, L. Yang, "Robust train timetabling and stop planning with uncertain passenger demand," Electronic Notes in Discrete Mathematics, vol. 69, pp. 213-220, DOI: 10.1016/j.endm.2018.07.028, 2018.

[5] M. R. Bussieck, T. Winter, U. T. Zimmermann, "Discrete optimization in public rail transport.," Mathematical Programming, vol. 79 no. 1-3, pp. 415-444, DOI: 10.1287/trsc.1030.0051, 1997.

[6] M. T. Claessens, N. M. Vandijk, P. J. Zwaneveld, "Cost optimal allocation of rail passenger lines," European Journal of Operational Research, vol. 110 no. 3, pp. 474-489, DOI: 10.1016/j.ejor.2004.04.036, 1998.

[7] J.-W. Goossens, S. P. M. van Hoesel, L. G. Kroon, "A branch-and-cut approach for solving railway line-planning problems," Transportation Science, vol. 38 no. 3, pp. 379-393, 2004.

[8] J. W. Goossens, S. V. Hoesel, L. Kroon, "On solving multitype railway line planning problems," European Journal of Operational Research, vol. 168 no. 2, pp. 403-424, 2005.

[9] H. Niu, X. Zhou, R. Gao, "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, DOI: 10.1016/j.trb.2015.03.004, 2015.

[10] L. Yang, J. Qi, S. Li, Y. Gao, "Collaborative optimization for train scheduling and train stop planning on high-speed railways," Omega, vol. 64, pp. 57-76, DOI: 10.1016/j.omega.2015.11.003, 2016.

[11] E. Altazin, S. Dauzère-Pérès, F. Ramond, S. Tréfond, "Rescheduling through stop-skipping in dense railway systems," Transportation Research Part C: Emerging Technologies, vol. 79, pp. 73-84, DOI: 10.1016/j.trc.2017.03.012, 2017.

[12] Y. Wang, A. D’Ariano, J. Yin, L. Meng, T. Tang, B. Ning, "Passenger demand oriented train scheduling and rolling stock circulation planning for an urban rail transit line," Transportation Research Part B: Methodological, vol. 118, pp. 193-227, DOI: 10.1016/j.trb.2018.10.006, 2018.

[13] Y. Zhu, R. M. P. Goverde, "Railway timetable rescheduling with flexible stopping and flexible short-turning during disruptions," Transportation Research Part B: Methodological, vol. 123, pp. 149-181, DOI: 10.1016/j.trb.2019.02.015, 2019.

[14] D. W. Li, B. H. Han, X. J. Li, H. J. Zhang, "High-speed railway stopping schedule optimization model based on node service," Journal of the China Railway Society, vol. 35 no. 6,DOI: 10.3969/j.issn.1001-8360.2013.06.001, 2013.

[15] F. Niu, J. G. Qi, J. Qin, "Optimization model for train stopping plan on high-speed railway corridor with uncertain passenger demands," Journal of the China Railway Society, vol. 38 no. 7,DOI: 10.3969/j.issn.1001-8360.2016.07.001, 2016.

[16] R. X. Xu, L. Nie, H. L. Fu, "Train stop plan optimization of high-speed rail for improving passenger travel efficiency," Journal of Transportation Systems Engineering and Information Technology, vol. 20 no. 2, pp. 174-180, 2020.

[17] Z. Shou, X. Di, J. Ye, H. Zhu, H. Zhang, R. Hampshire, "Optimal passenger-seeking policies on E-hailing platforms using Markov decision process and imitation learning," Transportation Research Part C: Emerging Technologies, vol. 111, pp. 91-113, DOI: 10.1016/j.trc.2019.12.005, 2020.

[18] X. Yu, S. Gao, X. Hu, H. Park, "A Markov decision process approach to vacant taxi routing with e-hailing," Transportation Research Part B: Methodological, vol. 121, pp. 114-134, DOI: 10.1016/j.trb.2018.12.013, 2019.

[19] M. Kamrani, A. R. Srinivasan, S. Chakraborty, A. J. Khattak, "Applying Markov decision process to understand driving decisions using basic safety messages data," Transportation Research Part C: Emerging Technologies, vol. 115,DOI: 10.1016/j.trc.2020.102642, 2020.

[20] J. C. Dunn, "A fuzzy relative of the ISODATA process and its use in detecting compact well-separated clusters," Journal of Cybernetics, vol. 3 no. 3, pp. 32-57, DOI: 10.1080/01969727308546046, 1973.

[21] C. W. Wang, J. H. Jeng, "Image compression using PCA with clustering," International Symposium on Intelligent Signal Processing & Communications Systems, vol. 41 no. 11, pp. 458-462, DOI: 10.1109/ispacs.2012.6473533, 2012.

[22] X. L. Xie, G. Beni, "A validity measure for fuzzy clustering," IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 13 no. 8, pp. 841-847, DOI: 10.1109/34.85677, 1991.

[23] N. Zahid, M. Limouri, A. Essaid, "A new cluster-validity for fuzzy clustering," Pattern Recognition, vol. 32 no. 7, pp. 1089-1097, DOI: 10.1016/s0031-3203(98)00157-5, 1999.

[24] S. Dimopoulou, A. Oppermann, E. Boggasch, A. Rausch, "A Markov decision process for managing a hybrid energy storage system," Journal of Energy Storage, vol. 19, pp. 160-169, DOI: 10.1016/j.est.2018.07.013, 2018.

[25] K. P. Murphy, T. Dietrich, Machine Learning: A Probabilistic Perspective, 2012.

[26] M. L. Puterman, Markov Decision Processes: Discrete Stochastic Dynamic Programming, 1994.