Train timetable and stopping plan generation based on cross-line passenger flow in high-speed railway network

Abstract

Considering the real scenario in China, in order to decrease passenger transfer, cross-line trains are scheduled extensively for the large number of cross-line passenger flow. Therefore, in this paper, we propose a more practical approach aiming to schedule more trains within a limit time horizon by both main-line train and cross-line train scheduling optimization (train timetable and stopping plan optimization). We find that the train scheduling and passenger assignment problems are multi-commodity flow problems. The trains (as the users) share the railway capacities (as the resource) in a high-speed railway network, and the passengers (as the users) share the train carrying capacities (as the resource). Thus, based on this, we formulate two space–time networks—train and passenger space–time networks—to present the train operation and the passenger flow, respectively. In addition, we regard train disturbances in different directions as different train headways at cross-line stations to optimize train scheduling practically. Sequentially, a mixed-integer linear programing model with headway and coupling constraints is formulated. To solve the model efficiently for a large-scale application, we decompose the problem into two space–time path-searching sub-problems based on the passenger and train space–time networks by the Lagrangian relaxation and alternating direction method of multipliers decomposition methods. Finally, we adopt the Taiyuan–Dezhou and Zhengzhou–Beijing high-speed railway networks in a practical experiment, and an experiment without cross-line operation is designed to test the effect of cross-line operation. The results show the proposed approach can obtain a no-conflict timetable and all the passenger demand can be satisfied, meanwhile, the capacity can improve 20.7% when the cross-line operation is not considered.

Introduction

Motivation

Compared to other transportation modes, high-speed railway has become more well-known over the past 10 years owing to the advantages of security, speed, convenience, comfort, and punctuality. Besides, with the rapid development of high-speed railways, efficiently and effectively operating the high-speed railway becomes more important for the railway operators, and capacity reasonable utilization is an urgent problem to be solved. Therefore, in this paper, train timetable and stopping plan generation method is designed to optimize the use of space-time resources for high-speed railway.

In the railway operation procedure, line plan (including the train origin and destination (OD), train type, train stopping plan, and train operation frequency) and timetable formulation are two important steps. Line plan is done based on the passenger demand, and the timetable is generated based on the line plan Yan et al. ¹ Figure 1 shows the relationship among passenger demand, train line plan, and train timetable considered in this study. Because of the characteristics of high-speed railway, trains cannot operate during the maintenance time window (5–6 h); therefore, they operate in a limited time and have insufficient high-speed railway capacity. Moreover, with the development of technology and economy, passengers have numerous travel demands; consequently all the trains determined by the line plan may not be operated. Furthermore, considering that the train stopping plan has a significant effect on the high-speed railway capacity, in our study, we removed the generated stopping plan from the line plan. Therefore, we proposed a method to schedule trains reasonably and maximize the number of scheduling trains by (1) train timetable optimization introduced in Barrena et al. ² and Jensen et al.2 ³ (2) improving the stopping plan introduced in Parbo et al. ⁴ and Lee et al. ⁵ under the oversaturation condition. In detail, when the trains determined by the line plan cannot be scheduled completely, train timetable and stopping plan optimizations are adopted for operating more trains to carry increased number of passengers.

Figure 1.

Relationship among passenger demand, train line plan, and train timetable.

In general, for a railway, the train timetable determines the train arrival, departure, and stopping times for every visited station, and the train stopping plan determines whether a train stops at a specific station. Therefore, the train timetable and the stopping plan have a strong relation Yang et al. ⁶ First, a train stopping plan is generated, and subsequently, the train timetable is formulated according to the previously generated stopping plan. However, a feasible train stopping plan may generate an infeasible train timetable, which could, in turn, have an effect on the stopping plan; therefore, a collaborative optimization of train timetables and stopping plans is necessary and must be efficient. Some studies, such as Dong et al., ⁷ Cacchiani et al., ⁸ and Qi et al., ⁹ integrated the optimizations of a train timetable and a stopping plan. In comparison, some cases, such as Wang et al., ¹⁰ optimized the problem as a bi-level solution, in which the stopping plan is obtained by a high-level optimization and the timetable by a low-level optimization using the results of the high-level one. Figure 2 shows the effect of a timetable and a stopping plan on train scheduling. In Figure 2(a), only three trains can be scheduled in a limited period. Figure 2(b) shows an improved stopping plan and timetable, five trains can be scheduled in a same period. Therefore, the train stopping plan of a railway plays an important role in train scheduling and subsequently affects the railway capacity.

Figure 2.

Scheduling trains with different train timetables and stopping plans: (a) Timetable with initial stopping plan and (b) Timetable with optimized stopping plan.

It is known that the high-speed railway in China has a network structure in which many lines are arranged in a crisscross pattern; interested readers can refer to Wang ¹¹ for the high-speed railway scenarios in China and the effect of cross-line trains. Operators prefer scheduling more trains for passengers to arrive at their destinations without transfer; therefore, many trains may have a cross-line operation at a specific station to carry more cross-line passenger flow. For example, the trains traveling from Beijing to Taiyuan have a cross-line operation at the Shijiazhuang station. The cross-line trains may crosscut the station throat and disturb other trains when departure or arrive the cross-line station. However, studies with regard to cross-line trains are almost in urban railway transit, such as Yang et al., ¹² and only few researchers are studying train scheduling problems considering cross-line trains in high-speed railway. To obtain precise and realistic optimization results, we consider cross-line trains in this study. For the proposed problem, we introduce the following definitions:

• (1) Line: High-speed railway in the railway planning period.

• (2) Main-line trains: Trains that always operate in one line.

• (3) Cross-line trains: Trains that have cross-line operations from one line to another line. For example, line 1 is composed of station A, station B, and station C, line 2 is composed of station D, station B, and station E, the trains operate from station A to station D or from station A to station E are cross-line trains.

• (4) Cross-line passengers: Passengers that travel from one line to another line. For example, line 1 is composed of station A, station B, and station C, line 2 is composed of station D, station B, and station E, the passengers travel from station A to station D or from station A to station E are cross-line passengers.

Figure 3 shows the flowchart of the proposed problem of this study. First, the train OD, passenger demand, basic parameters, and physical network are provided as the input of the model. Specifically, the basic parameters are the train travel time and the train headway, etc. Second, the passenger and train space–time networks are formulated to present the problems, and a mixed-integer linear programing (MILP) model is also built to maximize the number of scheduling trains. Subsequently, Lagrangian relaxation-based and alternating direction method of multipliers (ADMM)-based solution frameworks are utilized to decompose the original problem into several shortest path-searching problems. Finally, the train timetable, train stopping plan, and passenger assignment results are obtained.

Figure 3.

Flowchart of proposed problem.

Literature review

The train stopping plan of a railway, which is the input of the train timetable, is very important to determine whether a train stopping at a station is satisfying the passenger demand. There are many studies on the train stopping plan problem. Altazin et al., ¹³ Zheng et al., ¹⁴ Shang et al., ¹⁵ Jamili and Pourseyed Aghaee ¹⁶ presented a skip–stop strategy to generate the stopping plan. Chang et al. ¹⁷ formulated a multi-objective programing model to optimize train service by adjusting the stopping plan and frequency.

The train timetable of a railway determines the arrival, departure, and stopping times of each train at each station. A quality timetable can provide better service to passengers and generate more profits for the operators. Different researchers focused on different objective, Higgins et al. ¹⁸ optimized the train timetable for minimizing the consumption cost, Cacchiani et al. ¹⁹ aim to yield a regular, efficient, and robust timetable, Cacchiani et al. ¹⁹ proposed an integer linear programing model for a timetable problem to maximize the profits. In order to increase the efficiency of the algorithm, some methods, like Lagrangian relaxation and ADMM decomposition method were adopted. Meng and Zhou ²⁰ and Liao et al. ²¹ conducted train timetable optimization based on the cumulative flow, and the Lagrangian relaxation-based decomposition and solution framework algorithm was designed to solve the problem efficiently. Zhang et al. ²² formulated an extended space–time network to solve a cyclic timetable, and subsequently presented a multi-commodity network flow model with two coupled schedule networks and side track capacity constraints. For efficient solving, the Lagrangian relaxation and ADMM decomposition methods were adopted to dualize the side track capacity constraints into several train-specific subproblems, which could be solved by forward dynamic programing to determine the time-dependent least-cost path. Brännlund et al. ²³ presented a novel timetable optimization approach, which was a very large integer programing problem. The Lagrangian relaxation algorithm was used to solve this problem efficiently, and the method was tested on a real-world case of the Swedish National Railway Administration. Lamorgese et al. ²⁴ designed an approach to produce a timetable in a short time, based on which the proposed problem was solved by decomposing it into line and station problems. Caprara et al. ²⁵ proposed a graph–theoretic formulation for a train timetable problem, which was used to establish an integer linear programing model. Subsequently, the Lagrangian relaxation algorithm was used to solve the problem efficiently, and the variables in the relaxed constraints were associated only with nodes.

The stopping plan is the input of the train timetable of a railway; however, a series of trains with a given stoppling plan based on passenger demand might have overwhelmed capacity occupation and therefore impossible to be scheduled in a given time slot. Furthermore, the generated train timetable can, in turn, have an effect on the train stopping plan; therefore, they have a strong relation, and increasing number of studies are optimizing both simultaneously. Yang et al. ⁶ presented a new collaborative optimization method for both stopping planning and train scheduling problems to minimize the total dwell time and the total delay between the real and expected departure times from an origin station. These problems can be solved by CPLEX directly. Yue et al. ²⁶ formulated a space–time network and established an MILP model, which was decomposed by Lagrangian relaxation and solved by column generation, to maximize the profits of trains. Finally, they conducted a test on the Beijing–Shanghai high-speed railway. Gao et al. ²⁷ studied the problem of adding new trains to an existing timetable in a busy railway. A bi-level MILP model was presented to minimize the train travel time and the deviation between the original and new timetables. Subsequently, they used a three-stage method to solve the problem. Jiang et al. ²⁸ introduced a method by scheduling new trains and adjusting the dwelling time or a skip–stop strategy based on the current timetable to increase the number of scheduled trains. The established model was solved by a heuristic algorithm extended from a previous method. Meng and Zhou ²⁹ proposed an integrated team-based optimization model and solution algorithms with complex constraints for selecting the stop pattern for each train and for timetable optimization. The model was aimed at maximizing the transport profit and considered the effect of the service interval times on the passenger demand. Niu et al. ³⁰ proposed a train scheduling optimization model with given skip-stop pattern to minimize the total passenger waiting time under both minute- and hour-dependent demand volumes for different origin–destination pairs. Li et al. ³¹ studied train stop patterns and train schedules collaboratively, and formulated a mixed-integer nonlinear programing model with passenger route choices to minimize the passenger travel time in express/local mode. Cacchiani et al. ⁸ optimized the train timetable and stopping pattern with passenger demand uncertainty to obtain robust solutions. And several experiments were designed based on Wuhan-Guangzhou high-speed railway, which showed the proposed approach can reduce the number of unsatisfied passengers in more effective way. Dong et al. ⁷ presented a mixed integer nonlinear programing model to optimize both train timetable and stopping plan based on time-dependent passenger demand for commuter railways, and more realistic conditions like no predefined schedule, oversaturation, etc. are considered. The model can be solved by an extended adaptive large-scale neighborhood search algorithm efficiently. Boroun et al. ³² solved the joint timetable and stopping plan problem in a double-track railway with station capacity and time-dependent dwell time constraints to minimize the schedule makespan. Then a heuristic algorithm is adopted to obtain approximate solutions in the large-scale experiment.

Table 1 compares previous studies and the present one on stopping plan and timetable collaborative optimization. We find that there are few existing studies considering the effect of cross-line operations, and the headway is only determined between trains running on the same line. Therefore, the results may be impractical without introducing the cross-line operation and different headways at a cross-line station. Yang et al., ⁶ Yue et al., ²⁶ Cacchiani et al., ⁸ and Li et al. ³¹ solved the integration problem by considering passenger demand as a static value which neglects the dynamics of passenger demand and may obtain a unrealistic result. Jiang et al. ²⁸ optimized the problem by applying constraints on the maximum number of stops that can be canceled; however, they did not consider the passenger demand. Meng and Zhou, ²⁹ Niu et al., ³⁰ Boroun et al., ³² and Li et al. ³¹ predefined an alternative set of stopping plans, which simplified the problem and reduced the solution space significantly. Moreover, the objectives of most studies are minimizing the total travel time, total dwell time, and total delay or maximizing the operation profits. There are only few studies focused on the railway capacity. Therefore, in this study, our model maximizes the number of scheduling trains by train scheduling optimization while considering cross-line trains.

Table 1.

Comparison of previous studies and this study on stopping plan and timetable collaborative optimization.

Study	Objective function	PD	ASP	CL	SA
Yang et al. 6	Minimize total dwell time and total delay	Static	NO	NO	CPLEX
Yue et al. 26	Maximize profits of the trains	Static	NO	NO	LR and CG
Jiang et al. 28	Maximize scheduling trains	-	NO	NO	HA
Boroun et al. 32	Minimize schedule makespan	-	YES	NO	HA
Meng and Zhou 29	Maximize transport profit	SD	YES	NO	LR
Niu et al. 30	Minimize passenger waiting time	TD	YES	NO	GAMS
Li et al. 31	Minimize total passenger travel time	Static	YES	NO	CPLEX
Cacchiani et al. 8	Maximize robustness	Static	YES	NO	CPLEX
This paper	Maximize scheduling trains	TD	NO	YES	LR and ADMM

PD: passenger demand; ASP: alternative set of stopping plan; CL: cross-line operation; SA: solution algorithm; CG: column generation; HA: heuristic algorithm; LR: Lagrangian relaxation; TD: time-dependent; SD: service-dependent.

Contribution

Based on the abovementioned literature review, there are many studies on the train scheduling problem for a long time. Owing to the increasing passenger demands and the insufficient railway capacity, train timetable and stopping plan collaborative optimization must be considered to mitigate the railway capacity problem. In addition, the Chinese high-speed railway has a network structure, and cross-line operations, which have strong effects on train scheduling optimization, are inevitable; however, there is no study considering cross-line trains, which is impractical. Therefore, the contributions of this study can be summarized as follows:

1. We propose a solution to optimize train timetable and stopping plan collaboratively for increasing the railway capacity based on the current line plan. Concurrently, the proposed method considers cross-line operations, which has been rarely considered in the train scheduling problem research. In addition, trains from different directions may have disturbing depending on the station yard layout. Therefore, these problems are dealt with by introducing a headway and re-determining the headway between each pair of trains at cross-line stations. To input the passenger demand for the stopping plan generation and consider the passenger differences in time distribution, we also present a passenger assignment based on the train service.

2. We innovatively propose a Lagrangian relaxation-based and ADMM-based decomposition algorithm to solve the formulated MILP model efficiently with several operation constraints and a coupling constraint. Lagrangian relaxation-based decomposition methods are used to relax the coupling constraint. Consequently, the original problem is decomposed into two subproblems: train scheduling and passenger assignment. The passenger assignment problem can be divided into a series of least-cost path-searching problems in the passenger space–time network. Moreover, the train headway constraint of the trains can be relaxed by an ADMM-based decomposition method owing to the advantage of breaking the model symmetry. Therefore, the train scheduling subproblem is decomposed into a series of least-cost path-searching problems in the train space–time network.

The remainder of this paper is organized as follows. Section 2 presents the problem statement, construction of both the space–time networks, and notations of the model. Section 3 formulates the MILP model based on time-discretized time–space networks. Section 4 introduces the Lagrangian relaxation and ADMM-based decomposition methods. In Section 5, the proposed model and algorithm are demonstrated by a simple numerical experiment and a real-world numerical experiment based on the Taiyuan–Dezhou and Zhengzhou–Beijing high-speed railways. Section 6 presents the conclusions of this study.

Problem statement and notations

Notations

The notations used in this paper are listed in Table 2.

Table 2.

Indices, sets, parameters, and variables.

Notations	Definition
Indices
$i,j$	Indices of nodes in passenger service network, $i,j\in N$
$m,n$	Indices of nodes in train service network, $m,n\in N\prime$
$q$	Index of station in high-speed railway network, $q\in S$
$(i,j)$	Indices of links in passenger service network, $(i,j)\in L$
$(m,n)$	Indices of links in train service network, $(m,n)\in L\prime$
$t,s,t\prime ,s\prime$	Indices of time intervals, $t,s,t\prime ,s\prime \in T$
$(i,t)$	Indices of vertices in passenger space–time network, $(i,t)\in V$
$(m,t\prime )$	Indices of vertices in train space–time network,
$p$	Index of passenger group, $p\in P$
$k$	Index of train, $k\in K$
$(i,j,t,s)$	Indices of arcs in passenger space–time network, $(i,j,t,s)\in A^p$
$(m,n,t\prime ,s\prime )$	Indices of arcs in train space–time network, $(m,n,t\prime ,s\prime )\in A^k$
Sets
$N$	Set of nodes in passenger service network
$N\prime$	Set of nodes in train service network
$S$	Set of stations in high-speed railway network
$L$	Set of links in passenger service network
$L\prime$	Set of links in train service network
$T$	Set of time intervals in study time horizon
$P$	Set of passenger groups
$K$	Set of trains
$K^c$	Set of cross-line trains
$V$	Set of vertices in passenger space–time network
$V\prime$	Set of vertices in train space–time network
$A^p$	Set of arcs in passenger space–time network, $A^p=A_t^p\cup A_w^p\cup A_s^p\cup A_o^p\cup A_d^p$ , where $A_t^p$ , $A_w^p$ , $A_s^p$ , and $A_o^p$ denote sets of passenger travel, waiting, stopping, and unloading arcs, respectively, and $A_d^p$ is set of dummy arcs for passengers who cannot arrive at their destinations in space–time network
$A_{\mathrm{ava}}^p$	Set of available arcs of passenger $p$ in passenger–space–time network
$A^k$	Set of arcs in train space–time network, $A^k=A_t^k\cup A_w^k\cup A_s^k\cup A_c^k\cup A_a^k\cup A_g^k\cup A_d^k$ , where $A_t^k$ , $A_w^k$ , $A_s^k$ , $A_c^k$ , $A_a^k$ , and $A_g^k$ denote set of train travel, waiting, stopping, cross-line, arrival, and generating arcs, respectively, and $A_d^k$ is set of dummy arcs for trains who cannot arrive at their destinations in space–time network
$A_{\mathrm{ava}}^k$	Set of available arcs of train $k$ in train–space–time network
$\phi (m,n,t\prime ,s\prime )$	Set of train incompatible travel arcs when arc $(m,n,t\prime ,s\prime )$ is selected.
$\delta (m,n,t\prime ,s\prime )$	Set of passenger arcs that is attached to train arc $(m,n,t\prime ,s\prime )$ .
$\theta (i,j,t,s)$	Set of train arcs that connects with passenger arc $(i,j,t,s)$ .
Parameters
$o(p)$	Origin node of passenger group $p$
$d(p)$	Destination of passenger group $p$
$\mathrm{DT}\left(p\right)$	Departure time of passenger group $p$
$\mathrm{AT}\left(p\right)$	Arrival time of passenger group $p$
$o(k)$	Origin node of train $k$
$d(k)$	Destination of train $k$
$\mathrm{DT}\left(k\right)$	Scheduled departure time at origin node of train $k$
$\mathrm{AT}\left(k\right)$	Scheduled arrival time at destination of train $k$
$n^p$	Number of passengers in passenger group $p$
$n_{m,n,t\prime ,s\prime }$	Capacity of train arc $(m,n,t\prime ,s\prime )$
$c_{i,j,t,s}^p$	Arc cost in passenger space–time network
$c_{m,n,t^{″},s^{″}}^k$	Arc cost in train space–time network
$h_a,h_d,h_{\mathrm{ad}},h_{\mathrm{da}}$	Minimum train arrival, departure, arrival departure, and departure arrival headways, respectively
$h_a^c,h_d^c,h_{\mathrm{ad}}^c,h_{\mathrm{da}}^c$	Minimum train arrival, departure, arrival departure, and departure arrival headways, respectively, at cross-line station
Variables
$x_{i,j,t,s}^p$	= 1 if passenger $p$ selects passenger space–time arc $(i,j,t,s)$ , = 0 otherwise
$y_{m,n,t^{″},s^{″}}^k$	= 1 if train $k$ selects train space–time arc $(m,n,t^{″},s^{″})$ , = 0 otherwise

Problem statement

In a high-speed railway network, operators schedule trains based on the passenger demand. Figure 4(a) shows a simple case of the physical network of a high-speed railway, including physical stations and links. We construct a train service network, $(N\prime ,L\prime )$ , and a passenger service network, $(N,L)$ , to depict the train operation and passenger flow in detail. A station in the physical network can be split into several sections, which are called as virtual sections in this paper. A train link can be denoted as $(m,n)\in L\prime$ from the upstream node, $m\in N\prime$ , to the downstream node, $n\in N\prime$ , and a passenger link as $(i,j)\in L$ from the upstream node, $i\in N$ , to the downstream node, $j\in N$ . Figure 4(b) shows the train service network. We split the origin station (like station 1) into a train depot, train arrival node, and train departure node and the middle station (like station 2) into a train depot, train arrival node, train departure node, and train destination node. In addition, we divide the destination station (like stations 3 and 4) into train arrival, train departure, and train destination nodes. Train stopping, train travel, train cross-line, and train arrival links are defined to present the train stopping, train travel, train cross-line, and train arrival operations, respectively, as shown in Figure 4(b). Figure 4(c) shows the passenger service network. We split the origin station (like station 1) into passenger arrival and departure nodes and the middle station (like station 2) into passenger arrival, departure, and destination nodes. Moreover, we divide the destination station (like stations 3 and 4) into passenger arrival and destination nodes. Passenger stopping, passenger travel, and passenger unloading links are defined to present the passenger stopping at a station, passenger traveling between stations, and passenger unloading a train, respectively, as shown in Figure 4(c). In view of the characteristics of the Chinese high-speed railway, cross-line trains must be considered in train timetable and stopping plan optimizations for obtaining practical results. In the proposed simple case, the station sequence of the main-line train is 1-2-3, and the station sequence of the cross-line train is 1-2-4, and it must select the cross-line link traveling from station 2 to station 4, as shown in Figure 4(b). The inputs of this problem are the (1) physical network, (2) train OD and passenger demand, and (3) basic parameters, such as the train travel, train minimum and maximum stopping times, and train headway. The outputs of this problem are as follows: (1) train stopping plan, (2) train timetable, and (3) passenger assignment results.

Figure 4.

(a) Physical network of high-speed railway, (b) Train service network, and (c) Passenger service network.

Construction of space–time networks

Construction of train space–time network

Based on the train service network, we introduce the time dimension. The train space–time network, $(V\prime ,A^k)$ , is formulated to yield the train timetable and the stopping plan. Above, $V\prime$ is a set of vertices transformed from node $m$ to vertex $(m,t\prime ),t\prime \in 1,2,\dots ,T$ , and $A^k$ is a set of train arcs transformed from link $(m,n)$ to arc $(m,n,t\prime ,s\prime )$ denoting train travel from node $m$ at time $t\prime$ to node $n$ at time $s\prime$ , and the spending time is $s\prime -t\prime$ . To express train operations precisely, we set up seven types of arcs as described below and shown in Figure 5.

• (1) Train stopping arcs are built as $(m,n,t\prime ,s\prime )$ from arrival node $m$ of station $q$ to departure node of station $q$ , where $s\prime -t\prime$ is the stopping time of the trains. Moreover, different types of stopping arcs have different stopping times; therefore, the minimum and maximum stopping times of trains can be presented in the space–time network.

• (2) Cross-line arcs are built as $(m,n,t\prime ,s\prime )$ from arrival node $m$ of cross-line station $q$ to departure node $n$ of cross-line station $q$ , where $s\prime -t\prime$ is the the cross-line time of the trains, and the cross-line time is the stopping time of the cross-line train.

• (3) Train travel arcs are built as $(m,n,t\prime ,s\prime )$ from departure node $m$ of station $q$ to departure node $n$ of station $q+1$ , or from departure node $m$ of station $q$ to arrival node $n$ of station $q+1$ , where $s\prime -t\prime$ is the travel time between stations $q$ and $q+1$ . It should be noted that the travel arcs from departure node $m$ of station $q$ to departure node $n$ of station $q+1$ denote trains that directly pass station $q+1$ ; they are called as train passing travel arcs. The travel arcs from departure node $m$ of station $q$ to arrival node $n$ of station $q+1$ denote trains stopping at station $q+1$ ; they are called as train stopping travel arcs.

• (4) Train generating arcs are built as $(o\left(k\right),n,t\prime ,t\prime )$ from train depot $o\left(k\right)$ of station $q$ to train arrival node $n$ of station $q$ ; they represent trains departing from depot and arriving at a station.

• (5) Train waiting arcs are built as $(m,m,t\prime ,t\prime +1)$ for denoting trains waiting at a depot and a train destination node.

• (6) Trains arrival arcs are built as $(m,d(k),t\prime ,t\prime )$ from the arrival node $m$ of station $q$ to train destination node $d(k)$ of station $q$ .

• (7) Train dummy arcs are built as $(o(k),d(k),\mathrm{DT}\left(k\right),\mathrm{DT}\left(k\right)+1)$ from every train depot to the train destination nodes for the trains that fail to be operated.

Figure 5.

Train space–time network of simple case.

The total cost of the train stopping, train cross-line, and train travel arcs is set as the actual time spent in the real world, and the cost of the train dummy arcs is very high.

For a clear illustration, we adopt the simple case introduced in Section 2.2 to present the space–time networks. The passenger demand as listed in Table 3 comprises the passenger group OD, departure time, and number of passengers in each passenger group. The generated train timetable and the stopping plan are as shown in Table 4, and the corresponding train space–time network of lines 1 and 2 is displayed in Figure 5. The time interval of the network is set as one-time unit.

Table 3.

Passenger demand of simple example case.

Passenger group	OD	Departure time	Value
1	(1,3)	1	2
2	(1,3)	3	2
3	(2,3)	6	2
4	(1,4)	7	2
5	(1,2)	3	2

Table 4.

Train timetable and stopping plan of simple example case.

Train	OD	Stopping plan	Time sequence
1	(1,3)	(1,3)	(1,1) →(1,2)→(2,4)→(4,6)→(6,7) →(7,7)
2	(1,3)	(1,2,3)	(3,3) →(3,4)→(4,6) →(6,7) →(7,9) →(9,10) →(10,10)
3	(1,4)	(1,2,4)	(7,7) →(7,8)→(8,10) →(10,13) →(13,15) →(15,16) →(16,16)

Construction of passenger space–time network

Based on the passenger service network, we introduce the time dimension, and subsequently formulate the passenger space–time network, $(V,A^p)$ , to present the passenger flow. Above, $V$ is a set of vertices transformed from node $i$ to vertex $(i,t),\mathrm{where}t\in 1,2,\dots ,T$ . $A^p$ is a set of passenger arcs transformed from link $(i,j)$ to arc $(i,j,t,s)$ denoting passenger travel from node $i$ at time $t$ to node $j$ at time $s$ , and the spending time is $s-t$ . The train and passenger space–time networks are connected by a coupling constraint describing that the passenger flow is related to the corresponding train flow, as subsequently introduced in Section 3.5. To express the passenger flow precisely, we set up five types of arcs described below and shown in Figure 6.

• (1) Passenger travel arcs are built as $(i,j,t,s)$ from passenger departure node of station $q$ to passenger departure node of station $q+1$ (passenger passing travel arcs). Alternatively, they are from passenger departure node of station $q$ to passenger arrival node of station $q+1$ (passenger stopping travel arcs) based on the train flow. $s-t$ is the travel time of the passengers. Passenger passing travel arcs are related to the train passing travel arcs, and passenger stopping travel arcs to the train stopping travel arcs, which suggests that passengers must be in the train when they travel between two stations.

• (2) Passenger stopping arcs are built as $(i,j,t,s)$ related to the train stopping arcs and train cross-line arcs from passenger arrival node of station $q$ to passenger departure node of station $q$ , where $s-t$ is the stopping time of the passengers.

• (3) Unloading arcs are built as $(i,j,t,t)$ from passenger arrival node of station $q$ to passenger destination node of station $q$ . Each passenger can alight a train at station $q$ when a passenger stopping travel arc is selected at station $q-1$ .

• (4) Passenger waiting arcs are built as $(i,i,t,t+1)$ for passengers waiting at the passenger arrival and passenger destination nodes. Moreover, a passenger can only board a train when the train stops at a station.

• (5) Passenger dummy arcs are built as $(o(p),d(p),\mathrm{DT}\left(p\right),\mathrm{DT}\left(p\right)+1)$ from a passenger arrival node to the destination node for passengers that fail to load on a train because of the insufficient train capacity.

Figure 6.

Passenger space–time network of simple example case.

In this study, we integrate the passengers who have the same ODs and departure times into a group. Moreover, the passenger transfer arcs are not set because the transfer passengers should also buy tickets for boarding the transfer train; we regard them as the original passengers at the transfer stations.

Table 5 summarizes the travel time of each passenger group in the simple example case.

Table 5.

Travel time of each passenger group.

Passenger group	OD	Departure time	Value	Travel time
1	(1,3)	1	2	5
2	(1,3)	3	2	5
3	(2,3)	6	2	3
4	(1,4)	7	2	8
5	(1,2)	3	2	3

Model formulation

In this study, we aim to optimize the train timetable and stopping plan for mitigating the capacity of a high-speed railway. Therefore, based on the train and passenger space–time networks proposed above, an MILP model, is formulated.

Objective function

The objective of model M ₁ is to minimize the travel cost in the train and passenger space–time network shown in equation (1).

$$\begin{array}{c}\multicolumn{1}{c}{O_1=min\sum _{(m,n,t\prime ,s\prime )\in A^k}\sum _k{c}_{m,n,t\prime ,s\prime }^k{y}_{m,n,t\prime ,s\prime }^k}\\ \multicolumn{1}{c}{+\sum _{(i,j,t,s)\in A^p}\sum _p{c}_{i,j,t,s}^p{x}_{i,j,t,s}^p}\end{array}$$

(1)

Cross-line train constraint

In our proposed model, cross-line trains are considered to improve its practicality and universality. Actually, a cross-line train has a cross-line operation at a cross-line station; therefore, in response to the model, cross-line train $k\in K^c$ must select cross-line arc $(m,n,t\prime ,s\prime )\in A_c^k$ at the cross-line station, as expressed in equation (2).

$$\sum _{t\prime ,s\prime }{y}_{m,n,t\prime ,s\prime }^k=1\forall k\in K^c,(m,n,t\prime ,s\prime )\in A_c^k$$

(2)

Passenger group flow balance constraint

We introduce the available arc set, $A_{\mathrm{ava}}^p$ , for passenger group $p$ to reduce the solution space. Each passenger group $p$ should be generated from its origin $(o\left(p\right),\mathrm{DT}\left(p\right))\in A_{\mathrm{ava}}^p$ and end the trip at its destination $(d\left(p\right),\mathrm{AT}(p))\in A_{\mathrm{ava}}^p$ . In addition, the number of entering passenger groups must be equal to the number of departing passenger groups at an intermediate vertex, $(i,t)\in A_{\mathrm{ava}}^p$ . Accordingly, the passenger group flow balance constraint is expressed in equation (3).

$$\begin{array}{c}\multicolumn{1}{c}{\sum _{i,t:(i,j,t,s)\in A_{\mathrm{ava}}^p}{x}_{i,j,t,s}^p-\sum _{i,t:(j,i,s,t)\in A_{\mathrm{ava}}^p}{x}_{j,i,s,t}^p=}\\ \multicolumn{1}{c}{\{\begin{array}{c}\multicolumn{1}{c}{-1j=o\left(p\right),s=\mathrm{DT}\left(p\right)}\\ \multicolumn{1}{c}{1j=d\left(p\right),s=\mathrm{AT}\left(p\right)}\\ \multicolumn{1}{c}{0\mathrm{otherwise}}\end{array}\forall p\in P}\end{array}$$

(3)

Train flow balance constraint

Similarly, we introduce the available arc set, $A_{\mathrm{ava}}^k$ , for train $k$ to reduce the solution space. Each train $k$ should be generated from its origin $(o\left(k\right),\mathrm{DT}\left(k\right))\in A_{\mathrm{ava}}^k$ and end the trip at its destination $(d\left(k\right),\mathrm{AT}\left(k\right))\in A_{\mathrm{ava}}^k$ . In addition, the number of entering trains must be equal to the number of departing trains at an intermediate vertex, $(m,t\prime )\in A_{\mathrm{ava}}^k$ . Accordingly, the train flow balance constraint is expressed in equation (4). Moreover, the cross-line train constraint (equation (2)) can be integrated into the train flow balance constraint by adding a cross-line arc into the available arc set, $A_{\mathrm{ava}}^k$ , of cross-line train $k$ and deleting other arcs at the cross-line station.

$$\begin{array}{c}\multicolumn{1}{c}{\sum _{m,t\prime :(m,n,t\prime ,s\prime )\in A_{\mathrm{ava}}^k}{y}_{m,n,t\prime ,s\prime }^k-\sum _{m,t\prime :(n,m,s\prime ,t\prime )\in A_{\mathrm{ava}}^k}{y}_{n,m,s\prime ,t\prime }^k=}\\ \multicolumn{1}{c}{\{\begin{array}{c}\multicolumn{1}{c}{-1n=o\left(k\right),s\prime =\mathrm{DT}(k)}\\ \multicolumn{1}{c}{1n=d\left(k\right),s\prime =\mathrm{AT}\left(k\right)}\\ \multicolumn{1}{c}{0\mathrm{otherwise}}\end{array}\forall k\in K}\end{array}$$

(4)

Passenger flow and train flow coupling constraint

Based on the two space–time networks, the passenger flow depends on the train flow, which suggests that passenger group $p$ can only be assigned to arc $(i,j,t,s)\in \delta (m,n,t\prime ,s\prime )$ when arc $(m,n,t\prime ,s\prime )$ has been selected, where arc set $\delta (m,n,t\prime ,s\prime )$ includes the passenger arcs connected to train arc $(m,n,t\prime ,s\prime )$ . Thus, the passenger flow and train flow coupling constraint is as expressed in equation (5). This constraint is also the train capacity constraint, which suggests that the number of passengers selecting passenger arc $(i,j,t,s)\in \delta (m,n,t\prime ,s\prime )$ cannot exceed the capacity of train arc $(m,n,t\prime ,s\prime )$ .

$$\begin{array}{c}\multicolumn{1}{c}{\sum _p{n}^p{x}_{i,j,t,s}^p\le \sum _k{y}_{m,n,t\prime ,s\prime }^k\times n_{m,n,t\prime ,s\prime }\forall (m,n,t\prime ,s\prime )\in A^k,}\\ \multicolumn{1}{c}{(i,j,t,s)\in \delta (m,n,t\prime ,s\prime )}\end{array}$$

(5)

It should be noted that there are approximation errors in constraint (equation (5)) when we divide the passengers into passenger groups. For example, if the number of passenger groups boarding train $k$ is $n$ and train capacity is $\mathrm{Cap}$ , then when the $a^{\mathrm{th}}$ passenger group boarding the train causes the number of passengers, $\sum _1^{a^{\mathrm{th}}}{n}^p$ , to exceed $\mathrm{Cap}$ , the model prevents them from boarding the train. Therefore, the approximation error is $\mathrm{Cap}-\sum _{p=1}^{p=a^{\mathrm{th}}-1}{n}^p$ . However, a passenger group compared to a single passenger can help reduce the number of constraints (equation (5)). Therefore, operators should find a balance between the approximation errors and the complexity of the model due to their emphasis.

Train headway constraint

To ensure train operation security, the minimum headway between two adjacent trains should be introduced. In this paper, we introduce four types of headway, which are shown in Figure 7. Figure 7(a) to (d) display the minimum headways between two arrival trains, two departure trains, an arrival train and a departure train, and a departure train and an arrival train, respectively.

Figure 7.

Minimum headways between (a) two arrival trains, (b) two departure trains, (c) arrival and departure trains, (d) departure and arrival trains.

Accordingly, incompatible arc set $\phi ″(m,n,t\prime ,s\prime )$ of arc $(m,n,t\prime ,s\prime )$ at the general station is obtained as $\phi ″(m,n,t\prime ,s\prime )=\{(m,n,\tau ,\tau \prime ):|t\prime -\tau |\le h_d{\cup }^{|s\prime -\tau \prime |}\le h_a\}$ . In this study, cross-line train is considered, and the determination of the headway is dependent on the yard layout at the cross-line station of trains in different directions. The incompatible arc set can be expressed as $\phi ″(m,n,t\prime ,s\prime )=\{(m\prime ,n\prime ,\tau ,\tau \prime ):|t\prime -\tau |\le h_d^c{\cup }^{|s\prime -\tau \prime |}\le h_a^c{\cup }^{|t\prime -\tau \prime |}\le h_{\mathrm{da}}^c{\cup }^{|s\prime -\tau |}\le h_{\mathrm{ad}}^c\}$ , where $h_d^c$ , $h_a^c$ , $h_{\mathrm{da}}^c$ , and $h_{\mathrm{ad}}^c$ are the minimum departure, arrival, departure arrival, and arrival departure headways at the cross-line station, respectively. To clearly describe the headway at the cross-line station, we design a simple case, which is shown in Figure 8, including the cross-line station yard layout and different train routes. Table 6 lists the headways between each pair of trains based on the current station yard layout. We see that the headways of trains 1 and 2 are $h_a^c=h_a$ and $h_d^c=h_d$ and of trains 1 and 3 are $h_a^c=0$ and $h_d^c=h_d$ . Contrastingly there is no conflict between trains 1 and 4.

Figure 8.

Different train routes at cross-line station yard.

Table 6.

Headways of different trains at cross-line station.

Train	Train 1	Train 2	Train 3	Train 4
Train 1	$h_a,h_d$	$h_a,h_d$	$h_d$	0
Train 2	$h_a,h_d$	$h_a,h_d$	0	$h_{\mathrm{da}}$
Train 3	$h_d$	0	$h_a,h_d$	$h_{\mathrm{ad}},h_{\mathrm{da}}$
Train 4	0	$h_{\mathrm{ad}}$	$h_{\mathrm{ad}},h_{\mathrm{da}}$	$h_a,h_d$

Therefore, the global incompatible arc set is $\phi (m,n,t\prime ,s\prime )=\phi ″(m,n,t\prime ,s\prime )\cup \phi ″(m,n,t\prime ,s\prime )$ . Specifically, if train $k$ selects travel arc $(m,n,t\prime ,s\prime )$ , then other trains cannot select the arcs in incompatible arc set $\phi (m,n,t\prime ,s\prime )$ , as expressed in equation (6).

$$\sum _k\sum _{(m,n,t\prime ,s\prime )\in \phi (m,n,t\prime ,s\prime )}{y}_{m,n,t\prime ,s\prime }^k\le 1\forall (m,n,t\prime ,s\prime )\in A_t^k$$

(6)

Binary variable constraint

The passenger group binary variable constraint is expressed in equation (7); specifically, if passenger group $p$ selects arc $(i,j,t,s)$ , then $x_{i,j,t,s}^p=1$ , otherwise, $x_{i,j,t,s}^p=0$ . The train binary variable constraint is written in equation (8); if train $k$ selects arc $(m,n,t\prime ,s\prime )$ , then $y_{m,n,t\prime ,s\prime }^k=1$ , and otherwise, $y_{m,n,t\prime ,s\prime }^k=0$ .

$$x_{i,j,t,s}^p\in \{0,1\}$$

(7)

$$y_{m,n,t\prime ,s\prime }^k\in \{0,1\}$$

(8)

Solution methods

In this section, two decomposition methods—the Lagrangian relaxation and ADMM decomposition methods—are introduced to solve the proposed MILP model. For easy description of our model, we use $a$ instead of $(i,j,t,s)$ in the passenger space–time network and $b$ instead of $(m,n,t\prime ,s\prime )$ in the train space–time network.

Lagrangian relaxation-based decomposition method

Lagrangian relaxation, which was introduced by Shang et al. ³³ and Wang et al. ³⁴ is extensively used to solve large-scale optimization problems by relaxing the complex constraints into an objective function. Subsequently, the original problem can be decomposed into several sub-problems.

In the proposed model, M ₁ , constraints in equations (3) and (7) are concerned with the passenger assignment problem caused by the decision variables, $x_a^p$ . Constraints in equations (4), (6), and (8) are concerning the train scheduling problem due to the decision variables, $y_b^k$ . Moreover, constraint in equation (5) is a coupling constraint combining the two problems. Therefore, we relax the complex constraint in equation (5) into the objective function (equation (1)) by introducing a coupling Lagrangian multiplier, ${\lambda }_a\ge 0$ , and accordingly, we formulate a new model, M ₂ . If the solution violates the constraints (equation (5)), the new objective function (equation (9)) will be punished.

Objective function of model M ₂

$$\begin{array}{c}\multicolumn{1}{c}{O_2=\min \sum _{a\in A^p}\sum _p{c}_a^p{x}_a^p+\sum _{b\in A^k}\sum _k{c}_b^k{y}_b^k}\\ \multicolumn{1}{c}{+\sum _b\sum _{a\in \delta \left(b\right)}{\lambda }_a(\sum _p{n}^p{x}_a^p-\sum _k{y}_b^k{n}_b)}\end{array}$$

(9)

Subject to

Constraints (3), (4), (6), (7), and (8).

Model M ₂ can be decomposed into two sub-problems—train scheduling and passenger assignment problems–due to the decision variables $y_b^k$ and $x_a^p$ . Moreover, the train scheduling problem consists of a series of least-cost path-searching problems shown in model M ₃ for trains with a headway constraint (equation (6)). The objective function is expressed in equation (10), with the train space—time arc cost expressed in equation (11). Similarly, the passenger assignment problem consists of a series of least-cost path-searching problems, as depicted in model M ₄ for each passenger. The objective function is expressed in equation (12), with the passenger space–time arc cost expressed in equation (13). Model M ₄ can be solved by well-designed dynamic programing. The updating of the Lagrangian multiplier is expressed in equation (14), for which the classical subgradient method is adopted.

Sub-problem model M ₃

Objective function:

$$O_3=\min \sum _{k\in K}\sum _{b\in A^k}c{″}_b^k{y}_b^k$$

(10)

$$c{″}_b^k=\{\begin{array}{c}\multicolumn{1}{c}{c_b^k-n_b{\lambda }_{a}b\in A_t^k+A_s^k+A_c^k,a\in \delta \left(b\right)}\\ \multicolumn{1}{c}{c_b^k\mathrm{otherwise}}\end{array}$$

(11)

Subject to:

Constraints (4), (6), and (8)

Sub-problem M ₄ :

Objective function:

$$O_4^p=min\sum _{a\in A^p}c{″}_a^p{n}^p{x}_a^p$$

(12)

$$c{″}_a^p=\{\begin{array}{c}\multicolumn{1}{c}{c_a^p+n^p{\lambda }_{a}a\in A_t^p+A_s^p}\\ \multicolumn{1}{c}{c_a^p\mathrm{otherwise}}\end{array}$$

(13)

$${\lambda }_a^{g+1}=\max \{0,{\lambda }_a^g+{\theta }^g(\sum _p{n}^p{x}_a^p-\sum _k{y}_b^k{n}_b)\},b\in \theta \left(a\right)$$

$${\theta }^g=1/(1+g)$$

(14)

Subject to

Constraints (3) and (7).

ADMM-based decomposition method

The ADMM, which has the advantages of breaking the symmetry and strong convexity, is a combination of augmented Lagrangian relaxation and the block coordinate descent method Yao et al. ³⁵ Augmented Lagrangian relaxation adds a quadratic penalty term to the objective function based on the Lagrangian relaxation described in Section 4.1. Compared to Lagrangian relaxation, augmented Lagrangian relaxation can improve the robustness and functional convexity Zhang et al. ²² However, the quadratic penalty term leads to nonlinearity of the model; therefore, it is difficult to decompose the model into several independent subproblems. Subsequently, the block coordinate descent method is introduced to update the variables sequentially in a block-by-block manner and make the quadratic penalty term linear.

The proposed train scheduling model, M₃ , described in Section 4.1 also has a complex constraint, which is the headway constraint (equation (6)). Each train finds the least path in the train space–time network interconnectedly, leading to inefficient solving of large-scale experiments. Therefore, in this section, we decompose the model, M ₃ , using an ADMM-based decomposition method. First, the constraint in Eq. (6) is relaxed into the objective function of model M ₃ by the augmented Lagrangian relaxation, and the objective function of the new relaxed model, M₅ , is as expressed in equation (15). The Lagrangian multipliers ${\mu }_b\ge 0$ and the quadratic penalty multipliers $\rho$ are introduced to punish the objective when the headway constraint is violated, and the updating of the Lagrangian multipliers is presented in equation (16), which also adopts the classical subgradient method.

Model M ₅ :

Objective function:

$$\begin{array}{c}\multicolumn{1}{c}{O_5=\min \sum _{k\in K}\sum _{b\in A^k}c{″}_b^k{y}_b^k+\sum _b{\mu }_b(\sum _k\sum _{b\in \phi \left(b\right)}{y}_b^k-1)}\\ \multicolumn{1}{c}{+\frac{\rho }{2}\sum _b(\sum _k\sum _{b\in \phi \left(b\right)}{y}_b^k-1{)}^2,}\end{array}$$

(15)

$${\mu }_b^{g+1}=\max \{0,{\mu }_b^g+{\theta }^g(\sum _k\sum _{b\in \phi \left(b\right)}{y}_b^k-1)\}.$$

(16)

We can find headway constraint (equation (6)) is an inequality equation. Considering the ADMM decomposition method can only be applied on equality equation, a slack variable $s_q$ is introduced to transfer inequality constraint (equation (6)) to equality constraint, which is $\sum _k\sum _{b\in \phi \left(b\right)}{y}_b^k+s_q=1$ , and the $s_q$ can be defined as equation (17).

$$s_q=\{\begin{array}{c}\multicolumn{1}{c}{0\sum _k\sum _{b\in \phi \left(b\right)}{y}_b^k>1}\\ \multicolumn{1}{c}{1-\sum _k\sum _{b\in \phi \left(b\right)}{y}_b^k\sum _k\sum _{b\in \phi \left(b\right)}{y}_b^k\le 1}\end{array}$$

(17)

For easy solving, the quadratic term needs to be linearized; interested readers can refer to Yao et al. ³⁵ and Zhang et al. ²² for the linearization in ADMM. In this study we introduce ${\omega }_k=\sum _{k\prime \in K/\left\{k\right\}}\sum _{b\in \phi (b)}{y}_b^{k\prime }$ to denote the number of trains excluding train $k$ , selecting the arcs in incompatible travel arc set $\phi \left(b\right)$ . And the $s_q$ is transformed as equation (18).

$$s_q=\{\begin{array}{c}\multicolumn{1}{c}{0{\omega }_k\ge 1}\\ \multicolumn{1}{c}{1-\sum _k\sum _{b\in \phi \left(b\right)}{y}_b^k{\omega }_k=0}\end{array}$$

(18)

Then the quadratic term is transformed as equation (19).

$${(\sum _k\sum _{b\in \phi \left(b\right)}{y}_b^k-1+s_q)}^2=\{\begin{array}{c}\multicolumn{1}{c}{{(\sum _k\sum _{b\in \phi \left(b\right)}{y}_b^k-1)}^2{\omega }_k\ge 1}\\ \multicolumn{1}{c}{0{\omega }_k=0}\end{array}$$

(19)

When ${\omega }_k\ge 1$ , the quadratic term, $\sum _b{(\sum _k\sum _{b\in \phi \left(b\right)}{y}_b^k-1)}^2$ , can be transformed into $y_b^k(2{\omega }_k-1)+{({\omega }_k-1)}^2$ as expressed in equation (20).

$$\begin{array}{c}\multicolumn{1}{c}{{(\sum _k\sum _{b\in \phi \left(b\right)}{y}_b^k-1)}^2={(y_b^k+{\omega }_k-1)}^2=y_b^k}\\ \multicolumn{1}{c}{+2y_b^k({\omega }_k-1)+{({\omega }_k-1)}^2}\\ \multicolumn{1}{c}{=(y_b^k{)}^2+2y_b^k({\omega }_k-1)+({\omega }_k-1{)}^2}\\ \multicolumn{1}{c}{=y_b^k+2y_b^k({\omega }_k-1)+({\omega }_k-1{)}^2}\\ \multicolumn{1}{c}{=y_b^k(2{\omega }_k-1)+({\omega }_k-1{)}^2}\end{array}$$

(20)

Then, we can find that constraints (4) and (8) are independent of each train, the model is decomposed into several shortest-path searching problems for each train. Finally, model M ₅ is reformulated as expressed in equation (21) by combining the like terms, where $Q″\prime$ is a constant, and the calculation of the train arc cost is as expressed in equation (22). At this moment, all the constraints are independent, and the new model is a standard shortest-path searching problem for each train, which can be solved by well-designed dynamic programing.

Subject to:

Constraints in equations (5) and (9).

$$\begin{array}{l}{O}_5^k=\min \sum _{b\in A^k}{c^{\prime }}_b^k{y}_b^k+\sum _b{\mu }_b\left(\sum _{b\in \phi \left(b\right)}{y}_b^k-1\right)\\ +\frac{\rho }{2}\sum _b{y}_b^k\left(2{\omega }_k-1\right)+\frac{\rho }{2}{\left({\omega }_k-1\right)}^2\\ =\min \sum _{b\in A^k}{c^{″}}_b^k{y}_b^k+\frac{\rho }{2}{\left({\omega }_k-1\right)}^2-\sum _b{\mu }_b\end{array}$$

(21)

$$c{″}_b^k=\{\begin{array}{c}\multicolumn{1}{c}{c{″}_b^k+{\mu }_b+\frac{\rho }{2}(2{\omega }_k-1)b\in A_t^k}\\ \multicolumn{1}{c}{c{″}_b^k\mathrm{otherwise}}\end{array}$$

(22)

In model M ₅ , ${\omega }_k=\sum _{k\prime \in K/\left\{k\right\}}\sum _{b\in \phi (b)}{y}_b^{k\prime }$ is introduced to present the number of trains excluding train $k$ , selecting the arcs in incompatible travel arcs set $\phi \left(b\right)$ . Therefore, we design the rolling update scheme, as depicted in Figure 9, to solve the train scheduling subproblem. When scheduling train $k$ , other trains $k\prime \in K/\left\{k\right\}$ are fixed, and train $k$ is scheduled to find the shortest path based on the updating cost, ${c^{″}}_b^k$ . A train within the circle represents the current optimizing train $k$ , and the trains within the rectangle represent the fixed trains, $\begin{array}{c}k\prime \in K/\left\{k\right\}\hfill \end{array}$ .

Figure 9.

Rolling update scheme of ADMM for solving train scheduling problem.

Algorithm 1 presents the details of the Lagrangian relaxation- and ADMM-based decomposition methods to solve the train scheduling problem (model M ₅ ) and the passenger assignment problem (model M ₄ ). Considering the ADMM-based decomposition method is highly superior for dealing with the headway constraint and only a few iterations have conflict trains, we examine the number of conflict trains, indicate them in each iteration, and adopt the feasible solution as the train scheduling upper bound solution. Algorithm 2 is designed to yield a feasible passenger assignment solution based on the train scheduling results. Figure 10 shows the iterative structure of the approach based on the Lagrangian relaxation-based and ADMM-based decomposition methods.

Algorithm 1. Lagrangian relaxation- and ADMM-based decomposition methods

Input: Passenger space–time network $(N,A^p)$ and train space–time network $(N\prime ,A^k)$ , number of service trains, OD of service trains, passenger time–dependent OD matrix, planning horizon, and several basic parameters Output: Train timetable and stopping plan for each train and passenger assignment results for each passenger group Step 1: Initialization   Set current iteration number $g=0$ , Lagrangian multipliers ${\lambda }_a=0$ and ${\mu }_b=0$ , and penalty multiplier $\rho$ ; initialize passenger lower bound solution $\left\{x_0^{\mathrm{lower}}\right\}$ and train lower bound solution $\left\{y_0^{\mathrm{lower}}\right\}$ , initialize passenger upper bound solution $\left\{x_0^{\mathrm{upper}}\right\}$ ; set best lower bound $L{B}^{*}=-\infty$ , best upper bound $U{B}^{*}=+\infty$ , and maximum iteration number Step 2: Solve train scheduling problem M 5 by ADMM Step 2.1: Scheduling train For each train $k\in K$ do    Update arc cost ${c^{″}}_b^k$ by equation (22)    Use dynamic programming to find time-dependent least cost paths for train $k$ in train space–time network    Obtain train timetable and stopping plan results, and add results into train lower bound solution $\left\{y_g^{\mathrm{lower}}\right\}$ End for each train $k\in K$ Step 2.2 Train re-assignment For inner iteration do  For each train $k\in K$ do    Reset lower bound solution $\left\{y_g^{\mathrm{lower}}\right\}$ of train $k$ to 0 Update arc cost ${c^{″}}_b^k$ by equation (22) Use dynamic programing to find time-dependent least cost paths for train $k$ in train space–time network Obtain train timetable and stopping plan results, and add results to train lower bound solution $\left\{y_g^{\mathrm{lower}}\right\}$ ; obtain the objective function value End for each train $k\in K$ End for inner iteration Step 3: Solve passenger assignment problem M 4 by Lagrangian relaxation  For each passenger group $p\in P$ do    Update arc cost $c{\prime }_a^p$ by equation (13)    Use dynamic programming to find time-dependent least cost paths for passenger group $p$ in passenger space–time network    Obtain passenger assignment results, and add results into passenger lower bound solution $\left\{x_g^{\mathrm{lower}}\right\}$ ; obtain the objective function value  End for each passenger group $p\in P$ Step 4: Obtaining best lower bound Lower bound $L{B}^g$ at iteration $g$ is sum of two objective function values; then best lower bound can be calculated as $L{B}^{*}=\max \{L{B}^{*},L{B}^g\}$ Step 5: Obtaining best upper bound   Obtain feasible solution and add results into passenger assignment upper bound solution $\left\{x_g^{\mathrm{upper}}\right\}$ by algorithm 2. Calculate upper bound $U{B}^g$ at iteration $g$ , then best upper bound can be updated as $U{B}^{*}=\min \{U{B}^{*},U{B}^g\}$ Step 6: Updating Lagrangian multipliers Updating coupling constraint Lagrangian multiplier:   ${\lambda }_a^{g+1}=\max \{0,{\lambda }_a^g+{\theta }^g(\sum _p{n}^p{x}_a^p-\sum _k{y}_b^k{n}_b)\},b\in \theta \left(a\right)$ Updating headway constraint Lagrangian multiplier:   ${\mu }_b^{g+1}=\max \{0,{\mu }_b^g+{\theta }^g(\sum _k\sum _{b\in \phi \left(b\right)}{y}_b^k-1)\}$   ${\theta }^g=1/(1+g)$ Values of quadratic penalty multipliers $\rho$ are fixed in this study Step 7: Termination conditions   If current iteration $g$ reaches maximum iteration number presented before, terminate algorithm; otherwise, go to Step 2.

Algorithm 2. Finding upper bound solution for passenger assignment problem

Input: Passenger space–time network $(N,A^p)$ ; passenger group set $P$ ; passenger space–time network arc cost $c_{i,j,t,s}^p$ , train carrying capacity $\mathrm{Cap}$ ; train stopping plan and timetable results $\left\{y_g^{\mathrm{lower}}\right\}$ Output: Passenger assignment upper bound solution $\left\{x_g^{\mathrm{upper}}\right\}$ Initialize all capacity indicators $v(m,n,t\prime ,s\prime )=1$ , all the binary variables $x_{i,j,t,s}^p=0$ in $\left\{x_g^{\mathrm{upper}}\right\}$ For each passenger group $p$ Step 1: Initialization   Set label cost of passenger space–time network vertex $\sigma (i,t)=+\infty$ , space–time predecessor $\mathrm{pred}(i,t)=(-1,-1)$ , $\mathrm{pred}(o\left(p\right),\mathrm{DT}\left(p\right))=(0,0)$ , label cost $\sigma (o(p),\mathrm{DT}(p))=0$ Step 2: Label updating in dynamic programing  For each time $t$ do   For each vertex $(i,t)\in V$ do   For each arc $(i,j,t,s)\in A^p$ do    If $v(m,n,t\prime ,s\prime )=0,(m,n,t\prime ,s\prime )\in \theta (i,j,t,s)$     Break    End if    If $\sum _k{y}_{m,n,t\prime ,s\prime }^k=0,(m,n,t\prime ,s\prime )\in \theta (i,j,t,s)$     Break   End if     If $\sigma (i,t)+c_{i,j,t,s}^p\le \sigma (j,s)$     $\sigma (j,s)=\sigma (i,t)+c_{i,j,t,s}^p$     $\mathrm{pred}(j,s)=(i,t)$    End if   End for each arc $(i,j,t,s)\in A^p$   End for each vertex $(i,t)\in V$  End for each time $t$   Back-trace shortest space-time path for passenger group $p$ and add upper bound solution into $\left\{x_g^{\mathrm{upper}}\right\}$   Set $v(m,n,t\prime ,s\prime )=0,(m,n,t\prime ,s\prime )\in \theta (i,j,t,s)$ , if $\sum _p{n}^p{x}_{i,j,t,s}^p\ge \mathrm{Cap}$ End for each passenger group $p$

Figure 10.

Iterative structure of proposed approach based on Lagrangian relaxation and ADMM decomposition methods.

Numerical experiments

Simple experiment

Description

In this section, we present a simple case with nine stations, as shown in Figure 11(a). The station sequences of the main-line and cross-line trains are (1,2,3,4,5,6) and (1,2,3,4,7,8,9), respectively, and station 4 is the cross-line station. We only consider one direction to test the proposed approach, and perform sensitivity analysis for this simple case. The layout of cross-line station 4 is displayed in Figure 11(b), and accordingly we can determine the train headway, which is described in Section 3.6. We set the travel time between each station pair as 4, the minimum and maximum train stopping times as 2 and 3, respectively, at each station, and the cross-line time as 4. The time horizon of the simple case is set as 45; therefore, the time interval can be set as 1 in the space–time network. Train departure headway $h_d$ and train arrival headway $h_a$ are set as 2 each. The initial Lagrangian multiplier is set to 0.01, and penalty multiplier $\rho$ is set as 30. The capacity of each train is set as 15, and at most 15 passengers can be carried in each train. The passenger demands are listed in Table 7, including the OD, departure time, and value of each passenger group. The total number of passengers is 90, and we plan to schedule 6 trains to satisfy the passenger groups listed in Table 8, including the OD and departure time of each train.

Figure 11.

(a) Physical network of simple case and (b) Layout of cross-line station 4.

Table 7.

OD, departure time, and value of each passenger group.

Passenger group	OD	Departure time	Value	Passenger group	OD	Departure time	Value
1	(1,6)	5	5	2	(2,6)	5	5
3	(3,6)	5	5	4	(1,5)	5	5
5	(1,4)	5	5	6	(1,5)	10	5
7	(1,4)	10	5	8	(2,6)	10	5
9	(2,6)	10	5	10	(2,6)	10	5
11	(2,5)	10	5	12	(1,6)	15	10
13	(1,9)	1	5	14	(1,9)	1	5
15	(3,9)	1	5	16	(1,8)	1	5
17	(1,7)	1	5

Table 8.

OD and departure time of each train.

Train	OD	Departure time	Train	OD	Departure time
1	(1,6)	5	2	(1,6)	5
3	(1,6)	10	4	(1,6)	15
5	(1,9)	1	6	(1,9)	1

Results of simple case

Using the input introduced, we ran the experiment on a PC (CPU: i7-7700HQ 2.80 GHZ with 8 threads, 16 GB RAM) based on the proposed model and the decomposition algorithms. The best upper bound solution was obtained within 20 iterations, and the objective value is shown in Figure 12. Subsequently, to prove the efficiency and feasibility of the proposed approach, we solved the simple case by CPLEX to obtain the optimal results. The objective value is also shown in Figure 12. The gap between the upper bound objective value and the optimal value obtained by CPLEX is 1.6%. Figure 13 displays the train timetable and stopping plan results. It can be found that some trains dwell in a station that has no loading and unloading passengers. This is because if these trains pass this station, the headway constraint will not be satisfied within a limited time horizon in the subsequent stations.

Figure 12.

Upper bound and optimal objective values.

Figure 13.

Timetable and stopping plan of simple case solved by proposed approach.

Parameter analysis between train dummy arc cost and penalty multiplier $\rho$

In this study, we optimize the train timetable and stopping plan in a high-speed railway to maximize the number of scheduling trains, and the objective of the proposed model is to minimize the total travel cost. As the number of operating trains increases, some trains cannot be scheduled because of the headway constraint, and the departure and arrival times of two adjacent trains must maintain the corresponding headway. The non-operating trains should select the train dummy arcs to arrive at their destinations. Therefore, the train dummy arc cost, $c_{o(k),d(k),\mathrm{DT}\left(k\right),\mathrm{DT}\left(k\right)+1}^k$ , and the penalty multiplier, $\rho$ , affect the number of operating trains, number of unloading passengers, and number of conflict arcs. In this section, we analyze the effects of the parameters, the train dummy arc cost and penalty multiplier $\rho$ , which are shown in Figures 14 and 15, respectively.

Figure 14.

Effect of train dummy arc cost on (a) number of operating trains, (b) number of unloading passengers, and (c) number of conflict arcs.

Figure 15.

Effect of $\rho$ on (a) number of operating trains, (b) number of unloading passengers, and (c) number of conflict arcs.

In the first experiment, we fix the multiplier penalty as $\rho =35$ .

• (1) If $c_{o(k),d(k),\mathrm{DT}\left(k\right),\mathrm{DT}\left(k\right)+1}\le 40$ , the trains prefer to select the train dummy arcs, and the number of operating trains is 5, as shown in Figure 14(a), leading to 15 unloading passengers, as shown in Figure 14(b), and the number of conflict arcs is 0, as displayed in Figure 14(c).

• (2) If $41\le c_{o(k),d(k),\mathrm{DT}\left(k\right),\mathrm{DT}\left(k\right)+1}\le 45$ , the best upper bound solution is obtained. All the passenger groups can be carried, and the headway constraint is strictly complied.

• (3) If $c_{o(k),d(k),\mathrm{DT}\left(k\right),\mathrm{DT}\left(k\right)+1}\ge 46$ , the trains do not select the train dummy arcs, and 7 trains can be scheduled, as shown in Figure 14(a), there are 10 and 5 unloading passengers when $46\le c_{o(k),d(k),\mathrm{DT}\left(k\right),\mathrm{DT}\left(k\right)+1}\le 48$ and $c_{o(k),d(k),\mathrm{DT}\left(k\right),\mathrm{DT}\left(k\right)+1}=49$ , respectively, as shown in Figure 14(b). This is because seven trains are scheduled, and some trains cannot stop at some stations owing to the headway constraint, and passengers who want to board the train cannot be carried. Moreover, as the number of trains increases, the number of conflict arcs increases to six, as shown in Figure 14(c).

In the second experiment, we fix the train dummy arc cost as $c_{o(k),d(k),\mathrm{DT}\left(k\right),\mathrm{DT}\left(k\right)+1}=41$ .

• (1) If $\rho \le 30$ , the trains will violate the headway constraint, and seven trains are scheduled, as shown in Figure 15(a), leading to five unloading passengers, as depicted in Figure 15(b). Moreover, the conflict arcs increase to four, as shown in Figure 15(c).

• (2) If $31\le \rho \le 40$ , the best upper bound solution is obtained. All the passenger groups can be carried, and the headway constraint is strictly complied.

• (3) If $\rho \ge 41$ , the penalty is extremely large, and the adjustment space of the algorithm is compressed. Thus, the results may be trapped in the local solution, and some trains select the train dummy arcs for a large multiplier penalty. Therefore, 5 trains are scheduled, as shown in Figure 15(a), leading to 15 unloading passengers, as shown in Figure 15(b), and there are no conflicting train arcs, as displayed in Figure 15(c).

By analyzing the above experimental results, these conclusions can be summarized: (1) the passenger capacity of the train is not directly proportional to the number of trains, when the number of running trains is large enough and the penalty coefficient is large, the train will skip the predetermined stop station for meeting the train headway constraints, resulting in some passengers unable to complete the boarding and landing operation and reducing the passenger capacity of the train; (2) by setting reasonable parameters, the model and algorithm proposed in this paper can generate the train timetable and stopping plan collaboratively with time-dependent passenger flow, so as to carry more passengers with reasonable train operation quantity.

Real-world experiment based on Taiyuan–Dezhou and Zhengzhou–Beijing high-speed railways

Description

In this section, we present the results of the test of the proposed approach and analysis of the effect of cross-line operation in real-world scenarios based on the Taiyuan–Dezhou and Zhengzhou–Beijing high-speed railways, including 23 stations. The physical network of the high-speed railways is shown in Figure 16(a). The trains traveling from the Taiyuan–Dezhou railway to the Zhengzhou–Beijing railway or from the Zhengzhou–Beijing railway to the Taiyuan–Dezhou railway have a cross-line operation at the Shijiazhuang station. The layout of the Shijiazhuang station is displayed in Figure 16(b), which also presents all the train routes in each direction. The headways accordingly determined at the Shijiazhuang station are listed in Table 9. Some parameters are determined before the experiment. We only consider high-speed trains with speeds of 300 and 350 km/h, which are called as “G” trains. Therefore, we assume the travel time between two stations to be constant, which can be calculated by dividing the distance by the average speed, as listed in Table 10. The capacity of each train is set as 500. Considering that trains are easy to be scheduled in the off-peak period, we prefer to optimize the trains in the busiest period. The time horizon is set as 500 min (i.e. the time horizon of both space–time networks is 500 min) from 10:00 to 18:20, which is the busiest period, and the time interval in both space–time networks is set as 1 min. The sums of the stopping, acceleration, and deceleration times at each station are set as 4, 5, 6, 7, and 8 min, and the cross-line time is set as 8 min. The minimum headways are set as $h_a=3\min$ , $h_d=3\min$ , $h_{\mathrm{ad}}=2\min$ , and $h_{\mathrm{da}}=2\min$ . The penalty multiplier, $\rho$ , is set as 35, and the train dummy arc cost is set as 45.

Figure 16.

(a) Physical network of Taiyuan–Dezhou and Zhengzhou–Beijing high-speed railways and (b) Layout of Shijiazhuang station yard.

Table 9.

Headways between two trains in different directions.

Train	T–D	T–B	T–Z	B–T	B–Z	D–T	D–Z	Z–B	Z–T	Z–D
T–D	$h_a,h_d$	$h_a$	$h_a$	0	0	0	$h_{\mathrm{da}}$	0	−	$h_d$
T–B	$h_a$	$h_a,h_d$	$h_a$	0	0	0	0	$h_d$	0	0
T–Z	$h_a$	$h_a$	$h_a,h_d$	0	$h_d$	0	$h_d$	$h_{\mathrm{da}}$	0	$h_{\mathrm{da}}$
B–T	0	0	0	$h_a,h_d$	$h_a$	$h_d$	$h_d$	0	$h_d$	$h_{\mathrm{da}}$
B–Z	0	0	$h_d$	$h_a$	$h_a,h_d$	0	$h_d$	0	$h_d$	$h_{\mathrm{da}}$
D–T	0	0	0	$h_d$	0	$h_a,h_d$	$h_a$	0	$h_d$	0
D–Z	$h_{\mathrm{ad}}$	0	$h_d$	$h_d$	$h_d$	$h_a$	$h_a,h_d$	0	$h_d$	$h_{\mathrm{da}}$
Z–B	0	$h_d$	$h_{\mathrm{ad}}$	0	0	0	0	$h_a,h_d$	$h_a$	$h_a$
Z–T	−	0	0	$h_d$	$h_d$	$h_d$	$h_d$	$h_a$	$h_a,h_d$	$h_a,h_{\mathrm{da}}$
Z–D	$h_d$	0	$h_{\mathrm{ad}}$	$h_{\mathrm{ad}}$	$h_{\mathrm{ad}}$	0	$h_{\mathrm{ad}}$	$h_a$	$h_a,h_{\mathrm{ad}}$	$h_a,h_d$

T: Taiyuan; D: Dezhou; B: Beijing; Z: Zhengzhou.

Table 10.

Travel times between two stations.

Segment	Travel time	Segment	Travel time
Taiyuan–Donglingjing	18 min	Donglingjing–Yangquan	32 min
Yangquan–Jingxing	15 min	Jingxing–Shijiazhuang	25 min
Shijiazhuang–Gaocheng	15 min	Gaocheng–Xinji	15 min
Xinji–Hengshui	15 min	Hengshui–Jingzhou	10 min
Jingzhou–Dezhou	20 min	Zhengzhou–Xinxiang	20 min
Xinxiang–Hebi	16 min	Hebi–Anyang	15 min
Anyang–Handan	17 min	Handan–Xingtai	28 min
Xingtai–Gaoyi	22 min	Gaoyi–Shijiazhuang	5 min
Shijiazhuang–Zhengding Airport	14 min	Zhengding Airport–Dingzhou	14 min
Dingzhou–Baoding	17 min	Baoding–Gaobeidian	17 min
Gaobeidian–Zhuozhou	9 min	Zhuozhou–Beijing	27 min

In the real-world experiment, we consider all the train traveling directions. The inputs of the trains are 12 trains each from Taiyuan to Dezhou, from Dezhou to Taiyuan, from Zhengzhou to Beijing, from Beijing to Zhengzhou, from Taiyuan to Beijing, from Beijing to Taiyuan, from Taiyuan to Zhengzhou, from Zhengzhou to Taiyuan, from Zhengzhou to Dezhou, and from Dezhou to Zhengzhou. Moreover, we assume that all the trains depart from the physical origin station and arrive at the physical destination station. This is because almost trains are operated as this, and because trains can be scheduled from a physical origin station to a physical destination station, they can be scheduled to depart from or finally arrive at a middle station. Accordingly, this approach can improve the universality of the results.

Results of real-world experiment

Based on the abovementioned input proposed, we test the model and algorithm on the Taiyuan–Dezhou and Zhengzhou–Beijing railways. The best and current upper bound objective values of 20 iterations are shown in Figure 17. The solving time is 6720 s. The number of conflict trains in each iteration is depicted by a dotted circle in the figure, and there are four infeasible solutions in the results. We can see that the current upper bound is stable after iteration 7, and the best upper bound is obtained at iterations 11, 16, and 18, whereas the solution at iteration 16 is infeasible. Therefore, we select the solution of iteration 11 or 18 as the final result. To evaluate the quality of the results obtained at iteration 11 or 18, the lower bound objective value of 100 iterations is shown in Figure 18. The gap between the objective value we adopted and best lower objective value is 9.12%. Therefore, it can prove that we obtain a good feasible solution.

Figure 17.

Current and best upper bound objective values within 20 iterations.

Figure 18.

Lower bound objective value.

Figure 19(a) and (b) show the train timetable and stopping plan for the Taiyuan–Dezhou and Zhengzhou–Beijing high-speed railways, respectively. All the trains have no conflict with each other and all the passenger demands can be satisfied, which illustrate that the proposed approach can be used to maximize the scheduling trains and generate a high-quality train scheduling result. We find that three trains cannot be operated because of the train conflict: one train each from Taiyuan to Zhengzhou, from Zhengzhou to Dezhou, and from Zhengzhou to Taiyuan. Therefore, the trains traveling from Zhengzhou or to Zhengzhou have more disturbances by the trains in other directions. The proposed model can also evaluate the yard layout, and some disturbing points are marked as circles in Figure 19(a) and (b). The train from Taiyuan to Dezhou, which has headway $h_{\mathrm{da}}$ with train from Dezhou to Zhengzhou, cannot be operated within the solid circle shown in Figure 19(a). Similarly, the train from Zhengzhou to Beijing, which has headway $h_a$ with train from Zhengzhou to Taiyuan, cannot be operated within the dotted circle shown in Figure 19(b).

Figure 19.

Train timetable and stopping plan for (a) Taiyuan–Dezhou and (b) Zhengzhou–Beijing high-speed railways.

Effect analysis of cross-line operation

In this section, we discuss the test conducted for the effect of the cross-line operation on the optimization results. For this purposed, an experiment without considering the cross-line operation is designed. We only consider the minimum headways between two trains arriving at and departing from the same station. The number of input trains is set as 150 (the number of trains increases from 12 to 15 in each direction), and the input of the passenger demand is the same as in the experiment described in Section 5.2.1. The upper bound objective value without considering the cross-line operation is shown in Figure 20, and the timetable and the stopping plan are displayed in Figure 21. Finally, we find that 31 more trains are scheduled when the cross-line train is not considered compared to the experiment described in Section 5.2.2, which means the capacity can improve 20.7%.

Figure 20.

Upper bound objective value without considering cross-line operation within 20 iterations.

Figure 21.

Train timetable and stopping plan for (a) Taiyuan–Dezhou and (b) Zhengzhou–Beijing high-speed railways without cross-line operation.

In conclusion, the cross-line operation has a significant effect on the high-speed railway capacity. As the number of cross-line trains increases, more disturbances occur at the cross-line station, leading to a decrease in the number of scheduling trains. Therefore, the number of carrying passengers decreases, and the service quality cannot be guaranteed. Accordingly, this paper provides a more practical approach to optimize the train timetable and stopping plan for carrying more passengers.

Conclusion

In this study, we optimize the train timetable and stopping plan of a high-speed railway to maximize the number of scheduling trains for mitigating the railway capacity. Cross-line operation is also considered to improve the feasibility of the result in our study. Two space–time networks, train and passenger space–time networks, are built to allow train scheduling and passenger assignment based on a physical railway network. Subsequently, an MILP model is generated to optimize the proposed problem. The objective function is reformulated to minimize the total travel cost of the trains and the passengers. To solve the model efficiently, Lagrangian relaxation-based and ADMM-based decomposition methods are adopted to relax the coupling and headway constraints, respectively. Following this, the original problem is decomposed into several shortest-path searching problems of each passenger group and train, which can be easily solved by dynamic programing.

To prove the effect and efficiency of the proposed approach, first, we test the model and the algorithm for a simple case with nine stations. The best upper bound solution is obtained within 20 iterations, and there is only a 1.6% gap relative to the optimal solution obtained by CPLEX. Furthermore, the sensitivity analyses of the train dummy arc cost and the penalty multiplier are also conducted, and the results show that the number of operating trains, number of unloading passengers, and number of conflict arcs are affected by them. Finally, we optimize the train scheduling and the passenger assignment in a real-world experiment based on the Taiyuan–Dezhou and Zhengzhou–Beijing high-speed railways. An experiment without considering the cross-line operation is designed to depict the effect of the cross-line train, and it is found that 31 trains are scheduled additionally in this case. The results show that the cross-line operation has a significant effect on the train scheduling and the passenger assignment.

In future studies, more details, such as station capacity, different train speed, and track occupation, will also be considered to improve the practicality of the model. More efficient dynamic programing will also be designed, and the ADMM-based decomposition method will be improved to relax the coupling constraint.