A Lagrangian Method for Calculation of Passing Capacity on a Railway Hub Station

Abstract

This research paper proposes a Lagrangian method to address the passing capacity of the calculation problem (PCCP) for a hub station in a high-speed railway (HSR) system. The passing capacity of a hub station is critical for determining the train timetable and maximizing the number of trains that can operate on different lines. The objective of this study is to determine the maximum number of trains that can pass through, start at, or end at a hub station. To achieve this objective, a mathematical model was introduced to solve the PCCP. The model was decomposed into two parts using a Lagrangian relaxation algorithm. The first part of the model was a simple train arrival problem (TAP) that reflected the timing of trains at the hub station with simultaneous arrival and departure time constraints. The second part of the model was a train spatio-temporal routing problem (TSRP) that aimed to solve the shortest spatio-temporal path of trains with free conflict with the train’s trajectory. A real instance was provided to demonstrate the feasibility of the proposed approach and the effectiveness of the Lagrangian method. The results showed that the proposed method can efficiently solve the PCCP and maximize the passing capacity of a hub station in an HSR system.

1. Introduction

1.1. Background

The passing capacity calculation problem (PCCP) is a common issue encountered in the operation of high-speed railway (HSR) hub stations. The UIC code 406, proposed in [1], defines the PCCP as the maximum amount of traffic (number of trains or train pairs) that can be passed by various fixed equipment in a railway section per unit of time. Similar descriptions were present in [2,3,4]. Previous studies have typically calculated the station passing capacity after the facility and equipment conditions and transportation organization methods have been determined. However, in the operation of HSR, transportation organization techniques are not always fixed, and the PCCP of hub stations may fluctuate depending on the transportation organization strategies applied. Therefore, it is necessary to develop a method to calculate the passing capacity of a hub station that takes into account the varying transportation organization strategies. The proposed Lagrangian method in this study addressed this issue by decomposing the PCCP into two parts: the train arrival problem (TAP) and the train spatio-temporal routing problem (TSRP). The proposed method provided a valuable tool for railway planners and operators to optimize the passing capacity of hub stations in HSR systems. The ability to account for changing transportation organization strategies enhanced the practical application of the method and supported the efficient and safe operation of HSR systems.

1.2. Literature Review

Currently, the train station passing capacity problem (TSPR) is derived from the train routing problem (TRP) with a spatio-temporal arc. The PCCP of a station was based on TRP; various optimization goals for determining a station’s passing capacity, including total trains and total travel time, have been illustrated in [5]. Other models considering train speed and line conflicts at a given time were proposed in [6,7]. They developed a model for solving the problem with an objective function set to maximize the weighted total number of trains. Li et al. [8,9] investigated PCCP by redividing the throat area and establishing a PCCP optimization model based on zoning division with the objective of minimizing the number of total trains deducted on the parallel operation diagram.

Along this line, linear programming models have also been applied to solve the PCCP. Qi et al. [10] developed a single-level linear mixed-integer planning model based on a spatio-temporal network. Petering et al. [11] used a mixed-integer linear programming model to minimize the cycle length and the total travel time of all trains. Liu [12] set the objective function to minimize the penalty value for canceling the opening trains, which was solved with a mixed-integer linear programming model.

Fixed facilities such as arrival and departure lines, as well as throat areas, have been the subject of mathematical research. Wu [13] developed an operation control algorithm for these fixed facilities and established a simulation system for the PCCP at the hub station of HSR. In [14], a comprehensive optimization model was solved using the Lagrangian relaxation algorithm, which considered the facilities at the station. Li [15] utilized the VMD-BP neural network model to address the PCCP of the station, with the objective function set to minimize the number of arrival and departure lines. These studies demonstrated the various approaches that have been employed to address the PCCP, which has become an important issue in the transportation industry.

The capacity of a station to accommodate train traffic was influenced by both the fixed facilities and the operating plans in place. The operating plans determine the usage time window and state of these facilities. The problem of train approach selection has been characterized as a weighted node packing problem in prior studies [16,17]. This model was based on the node-boxing problem (NPP) and can be solved using a branch-and-bound algorithm. Kroon et al. [18] conducted research on the issue of train approach selection within a station, which was classified as an NP problem.

Several studies have expanded the scope of the facility to include a spatio-temporal perspective. The train timetable problem (TTP), which involved determining the timing and order plans for all trains on assigned routes, was addressed in [19]. They proposed an abstract model and a mixed-integer linear program to solve this problem. Similarly, the train routing problem (TRP) at a HSR station was formulated as a multi-objective mixed integer nonlinear programming model in [20], which aimed to minimize departure time deviations and the total occupation time of all tracks while ensuring balanced utilization of arrival-departure lines. Zhang et al. [21] constructed a mixed-integer programming model to solve the stock assignment plan and minimize the total occupation time of the neck region.

In recent times, the optimization of transportation systems, including railway networks, has garnered significant research attention. Several techniques have been proposed to enhance the efficiency of these systems, with one such technique being the Lagrangian method, which has been utilized to address optimization problems in transportation systems. However, recent studies have suggested that heuristic algorithms and reinforcement learning techniques may provide better results in certain transportation optimization problems. For example, Liu et al. [22] proposed a single-agent deep reinforcement learning approach for the vehicle dispatching problem, where vacant vehicles were reallocated in advance to regions with significant demand gaps. The approach was designed based on industrial-scale real-world data, ensuring its practical value. Additionally, paper [23] proposed a novel approach for learning highly efficient allocation policies for fleet management using reinforcement learning, while paper [24] developed a novel deep learning framework to capture the complex nonstationary temporal dynamics and spatial correlations in multistep traffic condition prediction.

The study of PCCP at stations has received significant attention from numerous scholars. However, there are two main limitations to the previous studies. Firstly, the fixed time of train arrival may not be conducive to the resolution of realistic and complex situations. Secondly, the station operating plan and the time of train arrival are disconnected in a spatio-temporal view. To address these limitations, this paper proposes a new approach to simultaneously schedule the station operation scheme and the time of train arrival at a railway hub station. In this study, we aimed to investigate the capacity of a railway hub station using the Lagrangian method. An optimization model was developed that takes several factors into account, including train routing and arrival and departure times. Our results showed that the proposed method can effectively calculate the passing capacity of a railway hub station and that it outperforms existing methods in terms of accuracy and efficiency. Specifically, we found that the Lagrangian relaxation approach was a powerful tool for solving complex optimization problems and that it could be used to effectively balance the trade-off between capacity and cost. Overall, our study provided important insights into the design and operation of railway hub stations and can help improve the efficiency and reliability of railway systems.

The rest of this paper is structured as follows: Section 2 provides a description of the problem. Section 3 presents the optimization model and explains it in detail. Section 4 introduces a Lagrangian algorithm framework to solve the proposed model. In Section 5, we demonstrate the effectiveness of the proposed approach by solving a real-world case. Finally, Section 6 presents our conclusions.

2. Problem Description

A railroad station consists of throat areas as well as some arrival-departure lines. as a set $Q=\{q_1,q_2,\dots ,q_k\}$ of spatio-temporal nodes, the route set of it is $A=\{a_1,a_2,\dots ,a_k\}$. The railway hub station’s physical network comprises tracks where trains arrive and depart, with insulation joints separating track lines. In this study, we defined the turnout node and the arrival-departure line node as spatio-temporal nodes. Thus, the network of the railway hub station was considered a directed graph. where nodes represent vertices, and the actual connections of the lines represent arcs. The most significant issue to be addressed in the TSRP was the conflicting trajectories that trains take. It is essential to note that trains cannot occupy the same track simultaneously. Additionally, a conflict arose whenever trains traveled the same track without adhering to the minimum time interval constraint, potentially resulting in conflicts.

The decision variables in this study were the train routing selection and the time of train arrival. To calculate the time for trains passing the station tracks, the train timetable problem (TTP) was employed. The TTP was defined as the proper scheduling of the departure and arrival times for all trains at each station on a given high-speed rail (HSR) line to eliminate train conflicts. The frequencies and time windows for each train line are calculated in advance as part of the time of arrival planning (TAP). During train timetabling, the running time is fixed, and the dwell time can be optimized within a given range. The objective of optimization is to minimize the total dwell time. As the values of different headways were not identical, it was more accurate to consider different headways for pairs of train lines separately.

In practical applications of TSRP, TAP was often used as a basis for predesigning demand and service capability. Binary decision variables are used to represent whether a track is allocated to a train trajectory or not. Once a set of feasible decision variables was determined, the routing for each train could be specified concurrently. When the time of TAP was calculated as input information to TSRP, the global objective was to determine the set of routes that minimized the train trajectory at the station while calculating the arrival time of trains. All operational constraints will be referred to within the context of TRP and TTP, as described in Section 3.

This paper presents a novel methodology that utilizes a Lagrangian algorithm to consider both the operating process scheme and the time of arrival of trains simultaneously, with the goal of enhancing the capacity of the transportation system. The framework of the proposed methodology is depicted in Figure 1.

To facilitate the analysis, we divided the PCCP of the hub station into two stages. In the first stage, the time of arrival of trains at the station was determined based on the TTP. The headway of the station and the organizational state of station operations dictated the number of trains that could arrive at the station. In the second stage, the station operation procedure was planned based on the TAP generated in the first stage.

3. Optimization Model

In order to optimize the PCCP of a station and provide high-performance transportation service, we propose an optimization model that utilizes the Lagrangian algorithm. In this section, we present the station capacity calculation problem as a single-objective problem, disregarding the station’s capacity constraint for various connection lines. Our estimation of the station’s passing capacity was based solely on the maximum number of arrivals and departures of trains. The sets, indices, and parameters used in this paper are listed in

Table 1. Sets, indices, and parameters.

Symbol	Definition
$Q$	The set of spatio-temporal nodes of station
$Q_{in}$	The set of inbound nodes of station, $Q_{in}\in Q$
$Q_{out}$	The set of outbound nodes of station, $Q_{out}\in Q$
$T$	The set of time
$A$	The set of spatio-temporal arc
$A_{in}^d$	The set of spatio-temporal inbound arc, $A_{in}^d\in A$
$A_w$	The set of spatio-temporal arc of type $w$
$H$	The set of headway of arrival trains
$D$	The set of lines the hub station connects
$P$	The set of inbound headway arc
$B_{i,j,t,s}$	The set of another spatio-temporal arc rivalling with spatio-temporal arc $(i,j,t,s)$
$i$, $j$	The index of nodes in the station’s physical network
$t,s,p,q$	The index of time
$h$	The index headway of arrival trains
$d$	The index lines the hub station connects
$(i,j)$	The index arc in Station’s physical network
$(i,t)$, $(j,s)$	The index of spatio-temporal nodes
$(p,q)$	The set of headway arc of the arrival inbound trains
${\alpha }_h^d$	The minimum number limitation of arrival headway for train $h$ inside line $d$
${\beta }_w$	The minimum number of trains $w$
$T_{start}$	The start time of operation, $T_{start}\in T$
$T_{end}$	The end time of operation, $T_{end}\in T$

.

In the spatio-temporal network of operation at station, we set the binary variable $x_{i,j,t,s}$ as the choice of the spatio-temporal approach If the spatio-temporal approach arc $(i,j,t,s)$ was positioned on the spatio-temporal trajectory of the train at the station, then $x_{i,j,t,s}=1$, else $x_{i,j,t,s}=0$. Moreover, we defined a variable $y_{p,q}^{d,h}$ as the binary variable. If there were two adjacent trains arriving at the station sequentially at the same time $p$ and $q$ within the line $d$ that the station connected, then $y_{p,q}^{d,h}=1$, else $y_{p,q}^{d,h}=0$.

Table 2. Decision variables.

Symbol	Definition
$x_{i,j,t,s}$	binary variable of spatio-temporal approach selection
$y_{p,q}^{d,h}$	binary variable of arrival headway for train

lists the two types of decision variables used in the optimization model based on spatio-temporal approach selection.

• Problem statement

In this context, we needed to take into account the constraints related to the service capacity of the station, which were dependent on the different lines connected to it. However, in this study, we focused only on the maximum number of trains that could pass through the station within a given time interval. Therefore, the problem of optimizing the PCCP of the station can be formulated as a single objective problem. Specifically, the objective was to determine the maximum number of trains that could pass through the station per unit of time, given the physical network of the station and the arrival times of the trains obtained from the TAP.

2.

Objective function

The objective was to maximize the number of trains passing through the hub station. The number of trains can be determined by the sum of $x_{i,j,t,s}$.

$$\max z={\displaystyle \sum _{d\in D}{\displaystyle \sum _{(i,j,t,s)\in A_{in}^d}{x}_{i,j,t,s}}}$$

(1)

3.

Network flow balance constraint

In railway station operations, the flow of every spatio-temporal node was considered a continuous process, and it was necessary to maintain equilibrium in the station operation spatio-temporal network. Constraint (2) has been introduced to ensure that the spatio-temporal network flow balance constraint is satisfied.

$${\displaystyle \sum _{(j,s)\in Q:(i,j,t,s)\in A}{x}_{i,j,t,s}-{\displaystyle \sum _{(j,s)\in Q:(i,j,t,s)\in A}{x}_{j,i,s,t}}}=0,\forall (j,s)\in Q-Q_{in}-Q_{out}$$

(2)

The selection variable of time for arrival trains must satisfy the flow balance constraints; therefore, the decision variable $y_{p,q}^{d,h}$ satisfies constraint (3).

$${\displaystyle \sum _{q\in T:(p,q)\in P}{y}_{p,q}^{d,h}}-{\displaystyle \sum _{q\in T:(q,p)\in P}{y}_{q,p}^{d,h}}=\{\begin{array}{l}1,q=T_{start}\\ -1,q=T_{end}\\ 0,\forall q\in T-T_{start}-T_{end}\end{array},\forall d\in D,\forall h\in H$$

(3)

4.

Rival operation constraints

It is imperative that any equipment within the station not be occupied by more than one train at any given time. The occurrence of such a situation would result in conflicts between the train operations within the station. Therefore, it follows that any spatio-temporal arc in the station operation spatio-temporal network with conflicting interference cannot be selected concurrently.

$${\displaystyle \sum _{(i^{\prime },j^{\prime },t^{\prime },s^{\prime })\in B_{i,j,t,s}}{x}_{i^{\prime },j^{\prime },t^{\prime },s^{\prime }}}\le 1,\forall (i,j,t,s)\in A$$

(4)

5.

Line capacity coordination constraint

The heterogeneity of trains is an essential factor that allows railway operations managers to provide diverse transportation services to society. Stopping the heterogeneity of trains implied that the headway of arrival and departure trains at each station could not be set as the minimum headway for all trains. Thus, to ensure that the stopping heterogeneity of trains running on the line is maintained, the train headway at the arrival station must comply with the distribution specified in constraint (5).

$${\displaystyle \sum _{(p,q)\in P}{y}_{p,q}^{d,h}}\ge {\alpha }_h^d,\forall d\in D,\forall h\in H$$

(5)

6.

Operating type constraints

To ensure the diversity of train stop services, a minimum number of trains must be required for each type of station operation.

$${\displaystyle \sum _{(i,j,t,s)\in A_w}{x}_{j,i,s,t}}\ge {\beta }_w,\forall w\in W$$

(6)

7.

Inbound and arrival headway association constraints

The arrival headway of a train can be represented by an arc that spans from the moment the preceding train enters the station to the moment the following train enters the station. The spatio-temporal nodes that are connected to this arc represent the source nodes of the train operation chain and must satisfy the constraint (7).

$${\displaystyle \sum _{h\in H}{y}_{t,q}^{d,h}={\displaystyle \sum _{(j,s)\in Q:(i,j,t,s)\in A_{in}^d}{x}_{i,j,t,s}}},\forall d\in D,\forall t\in T$$

(7)

8.

Decision variable constraint

Constraints (8) and (9) denote the decision variable $x_{i,j,t,s}$ and $y_{p,q}^{d,h}$ as binary variables, respectively.

$$x_{i,j,t,s}\in \{0,1\},\forall (i,j,t,s)\in A$$

(8)

$$y_{p,q}^{d,h}\in \{0,1\},\forall d\in D,\forall h\in H,\forall (p,q)\in P$$

(9)

9.

Model extension

The aforementioned model represents a TSRP in which the arrival times and numbers of incoming trains are uncertain. However, the model can be adapted to address general station operation planning problems in which the arrival and departure times of trains are already known. In this case, the number of arriving trains and their arrival times were fixed parameters denoted by $at\in Arr$. Consequently, the model was modified accordingly.

We Introduce the source point association parameter $a_{i,t}^d$, if $t=at(\forall at\in Arr)$, then $a_{i,t}^d=1$, else $a_{i,t}^d=0$. The objective function can be rewritten according to the actual requirements, such as the balanced utilization of station arrival and departure lines, the shortest total station operation time, and the optimization of station operating robustness. Canceling the arrival headway selection variable $y_{p,q}^{d,h}$, constraint (3), constraint (5), and constraint (9) in the original model. Simultaneously, modify the constraint (7) as shown in equation (10). Currently, the original model can be extended to the general issue of station operating schedule.

$$a_{i,t}^d={\displaystyle \sum _{(j,s)\in Q:(i,j,t,s)\in A_{in}^d}{x}_{i,j,t,s}},\forall d\in D,\forall t\in T$$

(10)

4. Lagrangian Relaxation Algorithm

In order to solve the PCCP for a railway hub station, we suggested utilizing a two-step solution approach. Firstly, we proposed using the commercial solver Gurobi to solve the TSRP model. Secondly, we suggested solving the model using a Lagrangian relaxation algorithm.

The Lagrangian relaxation technique was initially applied by Held and Karp to solve the traveling salesman problem (TSP) [22]. Since then, it has been successfully used to solve other classic problems such as the TRP [23], the location problem [24], the assignment problem [25], and the set covering problem [26]. Lagrangian relaxation is a common algorithm used to derive lower bounds for combinatorial optimization problems [27]. When applying the standard station’s PCCP model to a large-scale HSR hub station, the optimal solution was challenging to solve rapidly due to the problem’s great solution complexity. By analyzing the structure of the classic station PCCP model based on the spatio-temporal operation approach of alternative stations, we proposed utilizing the Lagrangian relaxation algorithm to relax the two constraints of the decision variables into the objective function to achieve the decomposition of the original problem. The Lagrangian multiplier was continuously updated by the subgradient method to approximate the optimal solution to the original problem.

In the following section, we provide a detailed description of the Lagrangian relaxation algorithm for solving the PCCP model of a railway hub station.

4.1. Lagrangian Decomposition

To enhance the model’s clarity, we transformed the original problem’s objective function into the objective function. This modification allowed for a more precise representation of the model and the incorporation of constraints into the objective function to relax them. We have used the negative version of the objective function to maintain consistency with the non-positive nature of the subsequent relaxation within the formula. By selecting a negative objective function, the constraint can be relaxed into the objective function, allowing for the Lagrangian decomposition of the constraint. $\mathrm{M}1$ represents the standard stations PCCP model based on the spatio-temporal operation approach of the alternative station, and the constraint’s formulation number is indicated when it first appears. The model $M1$ subjects to constraints (2–9).

$M1:$

$$\min z_{M1}=-{\displaystyle \sum _{d\in D}{\displaystyle \sum _{(i,j,t,s)\in A_{in}^d}{x}_{i,j,t,s}}}$$

(11)

From model $M1$, constraint (7) was the sole constraint that directly pertained to the decision variables $x_{i,j,t,s}$ and $y_{p,q}^{d,h}$. It is worth noting that constraints (2), (4), and (8) pertained solely to the decision variable $x_{i,j,t,s}$ while constraints (3), (5), and (9) were solely related to the decision variable $y_{p,q}^{d,h}$. By applying the Lagrangian multiplier ${\lambda }_{i,j,t,s}$, the coupling constraint (7) on the decision variables $x_{i,j,t,s}$ and $y_{p,q}^{d,h}$ was relaxed inside the objective function. The original model $M1$ can be transformed into the Lagrangian dual problem, $LRP1$. $LRP1$ was expressed as follows. The model $LRP1$ subjects to constraints (2,3,4,5,6,8,9).

$LRP1:$

$$\min zl=-{\displaystyle \sum _{d\in D}{\displaystyle \sum _{(i,j,t,s)\in A_{in}^d}{x}_{i,j,t,s}}}+{\displaystyle \sum _{d\in D}{\displaystyle \sum _{t\in T}{\lambda }_{d,t}\cdot ({\displaystyle \sum _{(j,s)\in Q:(i,j,t,s)\in A_{in}^d}{x}_{i,j,t,s}}-{\displaystyle \sum _{h\in H:(t,q)\in P}{y}_{t,q}^{d,h}})}}$$

(12)

The formula conversion of $LRP1$ yields two subproblems related to decision variables $x_{i,j,t,s}$ and $y_{p,q}^{d,h}$. The two subproblems are denoted by $M1x$ and $M1y$, respectively. $M1x$ is a TSRP that applies the spatial-temporal approach selection variable $x_{i,j,t,s}$ and is based on the selection of a station’s spatial-temporal operation. $M1y$ is a TAP associated with the train arrival time selection variable $y_{p,q}^{d,h}$. It is based on the time of arrival trains. $M1x$ and $M1y$ are shown below. The model $M1x$ subjects to constraints (2,4,6,8) and the model $M1y$ subjects to constraints (3,5,9).

$M1x:$

$$\min zlx={\displaystyle \sum _{d\in D}({\displaystyle \sum _{t\in T}{\lambda }_{d,t}-1)\cdot {\displaystyle \sum _{(i,j,t,s)\in A_{in}^d}{x}_{i,j,t,s}}}}$$

(13)

$M1y:$

$$\min zly=-{\displaystyle \sum _{d\in D}{\displaystyle \sum _{t\in T}{\lambda }_{d,t}\cdot {\displaystyle \sum _{h\in H:(t,q)\in P}{y}_{t,q}^{d,h}}}}$$

(14)

To facilitate solving the train arrival subproblem $M1y$, it can be divided by direction, and as a result, $M1y$ can be fully decomposed into several independent subproblems. The resulting subproblem set can be solved using a commercial solver. The form below illustrates how $M1y$ can be split into these independent subproblems.

$M1y:$

$$\min \left\{zly(d)=-{\displaystyle \sum _{t\in T}{\lambda }_{d,t}\cdot {\displaystyle \sum _{h\in H:(t,q)\in P}{y}_{t,q}^{d,h}}},\forall d\in D\right\}$$

(15)

4.2. Main Algorithm Framework Based on Subgradient Optimization

Any feasible solution to the original problem $M1$ yields an upper bound $Z_{UB}$ on the optimal solution to the original problem, while any feasible solution to its Lagrangian relaxation problem $LRP1$ provides a lower bound $Z_{LB}$ on the optimal solution to the original problem. This means that the sum of solutions to $M1x$ and $M1y$ represents a lower bound for the optimal solution to the original problem. The dual gap $Z_{UB}-Z_{LB}$ is difference between the upper and lower bounds, The dual gap can be used to evaluate the convergence effectiveness and solution quality of the algorithm. Ideally, a dual gap of 0 indicates that the optimal value of the original problem $M1$ is equal to the ideal value of its Lagrangian relaxation problem $LRP1$. When the optimal values $M1$ and $LRP1$ are unknown, it is possible to maximize the lower bound of $LRP1$ by continually updating the Lagrangian multipliers to approach the upper bound of $M1$. This paper employs the subgradient method to update the Lagrange multipliers during the iterative phase, and the algorithm framework is depicted in Figure 2.

The Lagrangian multiplier updating rule is illustrated in Formula (16).

$${\lambda }_{d,t}^{k+1}={\lambda }_{d,t}^k+{\theta }^k\cdot G_{d,t}^k,\forall d\in D,\forall t\in T$$

(16)

In Formula (16),

The Lagrange multiplier at the $k$ iteration is ${\lambda }_{d,t}^k$;

The subgradient of the $k$ iteration is $G_{d,t}^k$;

The step length of the $k$ iteration is ${\theta }^k$.

The formulas for subgradient $G_{d,t}^k$ and iteration step length ${\theta }^k$ are presented in Equations (17) and (18).

$$G_{d,t}^k={\displaystyle \sum _{(j,s)\in Q:(i,j,t,s)\in A_{in}^d}{x}_{i,j,t,s}}-{\displaystyle \sum _{h\in H:(t,q)\in P}{y}_{t,q}^{d,h}},\forall d\in D,\forall t\in T$$

(17)

$${\theta }^k=\frac{\pi \cdot (Z_{UB}-Z_{LB})}{{\displaystyle \sum _{d\in D}{\displaystyle \sum _{t\in T}{(G_{d,t})}^2}}}$$

(18)

$\pi$ is a custom parameter, $0<\pi \le 2$. According to the research of Beasley [28], $\pi$ should be halved if the dual gap stays unchanged after multiple iterations.

The main algorithm of the iterative process is illustrated in Algorithm 1:

Algorithm 1: Lagrangian relaxation

Step 1: Initialization   set $\pi =2$, Lagrangian multiplier ${\lambda }_{d,t}$, initial iteration $k=0$, maximum iterations $k=k_{\max }$, upper bound $Z_{UB}=0$, lower bound $Z_{LB}=-\infty$.   Step 2: Solve the Lagrangian dual problem.   Step 2.1: Solve the TAP $M1y$   Solve the subproblem $M1y$ with the solver Gurobi according to the current Lagrange multiplier ${\lambda }_{d,t}$. Obtain the train arrival station timetable, and $\{y_{t,q}^{d,h},\forall d\in D,\forall h\in H\}$, collection $\{y_{t,q}^{d,h},\forall d\in D,\forall h\in H\}$ represents the times of the arrival trains, then solve the objective value of the related relaxation subproblem and let $Z_{LBy}$ denote it.   Step 2.2: Solve the TSRP $M1x$   Invoke Algorithm 2 to solve the TSRP. Input the result $\{y_{t,q}^{d,h},\forall d\in D\}$ obtained from Step 2.1: into Algorithm 2; Deconflict the current station operation schedule in Algorithm 2, Return the collection $\{x_{i,j,t,s},\forall (i,j,t,s)\in A\}$ and the target value of the corresponding relaxation subproblem, and let $Z_{LBx}$ denote it;   Step 2.3: Solve the function value of the original problem and the dual gap.   Solve the objective function value of the original problem $M1$, let $R^k(M1)$ denote it. Update the upper bound $Z_{UB}=\min (R^k(M1),Z_{UB})$; solve the value $Z_{LBy}+Z_{LBx}$ of the objective function for the Lagrangian dual problem $LRP1$; Update the lower bound $Z_{LB}=\max (Z_{LBy}+Z_{LBx},Z_{LB})$; solve the dual gap $Z_{UB}-Z_{LB}$.   Step 3: Update Lagrangian multiplier   Update Lagrangian multipliers based on Formula (16).   If the value of $Z_{UB}-Z_{LB}$ decreases too much after more than 20 iterations, then $\pi =\pi$; else $\pi =\frac{1}{2}\pi$.   Step 4: Check the algorithm termination conditions.   If the number of iterations $k$ is more than the set maximum number of iterations $k_{\max }$ or the dual gap is satisfied, then the calculation is terminated; otherwise $k=k+1$, return to Step 2.

4.3. Subalgorithm for TSRP

In this section, we present Algorithm 2, which is designed to find an independent operation routing for conflicting trains and incorporate it into the current operating schedule of the station. The algorithm aims to improve the solution obtained from the subproblem by performing a neighborhood search on a set of conflicting trains. The model solved by the algorithm is shown below as $M1x$ which subjects to constraint (2,8).

$M1x:$

$$\min zlx={\displaystyle \sum _{d\in D}({\displaystyle \sum _{t\in T}{\lambda }_{d,t}-1)\cdot {\displaystyle \sum _{(i,j,t,s)\in A_{in}^d}{x}_{i,j,t,s}}}}$$

(19)

Algorithm 2 aims to find an independent operation routing for conflicting trains and obtain a feasible solution by incorporating the current operating schedule of the station and setting K. The algorithm begins by selecting a set of conflicting trains from the present solution of the $M1y$ subproblem. Then, a neighborhood search algorithm is performed on this set to obtain a new independent operation routing. The algorithm checks whether this new routing is feasible and satisfies all the constraints. If the new routing is feasible, it is accepted as the solution for the conflicting trains. If not, the algorithm performs another neighborhood search until a feasible solution is found. Finally, the algorithm updates the collection $\{x_{i,j,t,s},\forall (i,j,t,s)\in A\}$ and the solution for the $M1y$ subproblem by incorporating the new independent operation routing.

Algorithm 2: Shortest path problem

Step 1: Create a set $Tr=\{t{r}_1,t{r}_2,\dots \}$ for arrival trains based on the current solution of the subproblem $M1y$; create a set $\{(i_1,t_1),(i_2,t_2),\dots \}$ for spatio-temporal nodes of the arrival train, and let $I$ denote it. Create a set $K=\varnothing$ for operating trains; create $C=\varnothing$ for conflicting trains.   Step 2: For all the nodes $(i,t)$ of set $I$, set it as the beginning point of spatio-temporal operating routing, calculate the shortest path from the spatio-temporal trajectory network of station, let the operating chain $\phi =\{(i,j,t,s),(j,i^{\prime },s,t^{\prime }),\dots \}$ denote it, and generate the initial operating schedule of station.   Step 3: Find out all the conflicting statuses of set $Tr$. If there is an operating conflict of trains in $Tr$, then add it to $C$; else add it to $K$.   If $C=\varnothing$, turn to Step 5; else turn to Step 4.   Step 4: Find out the operating routing of trains in $K$. Create $C_w$, find the conflicting train pair in $C$, then add it to $C_w$.   Step 4.1: Delete all the spatio-temporal conflicting approach arcs in the spatio-temporal operating network of stations. Generate all feasible spatio-temporal operating routings for trains in $C_w$ within the present station operating spatio-temporal network, and then search for the maximum independent set of spatio-temporal operating routings for all trains in $C_w$.   Step 4.2: If there is a maximum independent set of spatio-temporal operating routings for all trains, add to $W$ and $K$; else add to $C$. Turn to Step 3.   Step 5: Output the current operating schedule of stations and set $K$. End.

5. Case Study

This section provides a numerical experiment on the proposed station TSRP in order to prove the effectiveness of our models and algorithms.

5.1. Introduction to the Jinanxi Railway Hub Station

Jinanxi station is a vital node in the high-speed rail operation network, serving as a physical intersection of several high-speed railway lines. To further evaluate the effectiveness of the proposed approach, we selected Jinanxi station as a case study. The station layout of Jinanxi railway hub station is presented in Figure 3. Jinanxi station is connected to the Beijing-Shanghai high-speed railway, the Shijiazhuang-Jinan passenger dedicated line, and the Beijing-Jinan railway. The station has 2 arrival and departure yards, 4 main lines, 13 arrival and departure lines, and 8 platforms.

Jinanxi station serves as a critical junction point in the high-speed rail network, connecting three lines and facilitating the arrival and departure of trains from multiple lines. In this case, there are 12 different train routes that pass through Jinanxi station, including routes: from Beijing downdirection to Shanghai direction; from Beijing downdirection to Jinan direction; from Shanghai updirection to Beijing direction; and from Shanghai updirection to Qihe direction; from Jinan updirection to Beijing direction; from Jinan updirection to Qihe direction; from Qihe downdirection to Shanghai direction; from Qihe downdirection to Jinan direction; and an immediate turn-back train from Beijing, Shanghai, and Qihe and Jinan direction.

5.2. Description of the Experimental Setting

The time of arrival trains is a crucial factor affecting the passing capacity of a hub station in a railway network [29]. In this section, we designed two experimental scenarios to investigate the difference in station passing capacity when receiving and dispatching trains from different lines. These simulations were constructed as follows.

Scenario 1: distribution of arrival times without restrictions

Assuming no constraints on the distribution of train arrival times, trains arrive at the station with the smallest possible headway, allowing the calculation of the ultimate carrying capacity of the railway hub station’s physical equipment without operational conflicts. These findings represent the upper limits of the hub station’s passing capacity as determined by various approaches [30] and can be helpful in guiding realistic operators.

Scenario 2: distribution of arrival times with restrictions

Station operation trains must meet certain arrival distribution conditions [31,32,33,34,35], with the input parameter being the minimum frequency of train arrival headway for a particular line.

The parameters associated with the model were set as follows:

• Train station operating time standards: the train stopping time is a minimum of 2 min and a maximum of 10 min; there is no immediate turnback train.
• Train headway standard: the minimum arrival headway and the minimum departure headway in scenarios 1 and 2 are set to 4 min. The train arrival distribution in scenario 2 needs to meet

  Table 3. Decision variables.

  Arrival Headway of Trains	The Frequency of Minimum Headway
  	Beijing	Shanghai	Jinan	Qihe
  8min	4	4	2	2
  12min	3	3	1	1
  15min	2	2	0	0

  .
• The calculation time range is 120 min.

5.3. Computational Results and Analysis of the Experiment

The experiment used Python programming to implement the above solution algorithm. The test computer processor had a 3.20 GHz main frequency and 32 GB of memory, and the maximum number of iterations was 80. The composition of station capacity for scenario 1 is illustrated in Figure 4, while scenario 2 is illustrated in Figure 5. The calculation results are shown in

Table 4. Result of scenario 1.

Direction	Type of Line	Number of Trains
downdirection	Beijing-Jinan	8
	Beijing-Shanghai	6
	Qihe-Jinan	6
	Qihe-Shanghai	7
updirection	Shanghai-Beijing	7
	Shanghai-Qihe	8
	Jinan-Beijing	5
	Jinan-Qihe	8
Totals		55

and

Table 5. Result of scenario 2.

Direction	Type of line	Number of trains
downdirection	Beijing-Jinan	3
	Beijing-Shanghai	12
	Qihe-Jinan	6
	Qihe-Shanghai	3
updirection	Shanghai-Beijing	15
	Shanghai-Qihe	4
	Jinan-Beijing	2
	Jinan-Qihe	2
Totals		47

.

There were 55 trains of operation accomplished at the station within 28 updirection trains and 27 downdirection trains in scenario 1; in scenario 2, the station realized 47 trains of operation, including 23 trains in the updirection and 24 trains in the downdirection.

As demonstrated in Figure 6 and Figure 7, the method was able to stabilize the values of the upper and lower bounds at approximately 80 iterations, and the gap value between the two bounds satisfied the requirement.

The comparison of the results from the two scenarios revealed that the passing capacity of Jinanxi Station in scenario 1 was higher than that in scenario 2. When the average train arrival headway is longer, it can limit the station’s passing capacity when certain arrival distribution conditions are met. This outcome was consistent with real-world operation scenarios where the railway network offered more stopping options for trains to cater to the diverse needs of passengers and a greater stopping heterogeneity existed. The higher the heterogeneity of train stops, the more challenging it became for station trains to arrive at minimum headway, preventing the station’s passing capacity. Whenever necessary, the station’s passing capacity can be temporarily increased by reducing the number of train stopping options and the heterogeneity of train stops.

Figure 8 and Figure 9 present histograms of the station turnouts and arrival and departure line utilization rates for Scenario 1 and Scenario 2, respectively. In terms of capacity utilization, both scenarios exhibit similar average utilization rates of turnouts at the left and right throats of Jinanxi Station, with the right throat showing slightly higher utilization on average. However, the right throat had fewer parallel approaches than the left throat, resulting in cross interference between trains approaching from Jinan and Shanghai and leading to a higher utilization rate of local turnouts in the throat.

The dotted lines in Figure 8 and Figure 9 divide the throat area and platforms. In scenario 1, the station turnout utilization was slightly higher than in scenario 2, and the overall utilization is more balanced, as evidenced by the turnout utilization histograms. This was due to the fact that in scenario 2, the longer average train arrival headway leads to more available approaches, causing trains to choose the shortest operating path as their station travel path, resulting in trains in the same direction using the same approach. In contrast, in scenario 1, with a smaller average train arrival headway, there were fewer available approaches, leading to more balanced turnout utilization.

In Lagrangian optimization techniques, it is common to generate a feasible solution for the “optimal” value of the Lagrangian multipliers, as noted in previous studies [36,37]. However, an alternative approach involving the generation of feasible solutions in all iterations of the subgradient algorithm has been found to be more computationally expensive yet potentially more effective [37]. For our study, we adopted this latter approach and generated feasible solutions at each iteration of the subgradient algorithm. To demonstrate the effectiveness of this approach, we present Figure 10 to illustrate how the original objective function changes from iteration to iteration of the subgradient method. This figure highlights that the best feasible solution may not necessarily correspond to the best Lagrangian bound. Additionally, it justifies the increased computational cost associated with the frequent generation of feasible solutions.

To evaluate the performance of our proposed Lagrangian heuristic algorithm, we compared the CPU time required to solve the problem instances using our approach versus the widely-used commercial solver, Gurobi. The experiments were run on a computer with an Intel Core i7 processor and 32GB of RAM.

Table 6. CPU time of approaches.

Number of Trains	The CPU Time of the Approach(s)
	Gurobi	Lagrangian Approach
47	1475	1215
55	2143	1824

presents the CPU time required to solve the test instances using our approach and Gurobi. As can be seen, Gurobi requires significantly more CPU time than our approach to solving the problems. This was expected, as our proposed approach was designed to provide good solutions with a reasonable level of computational effort, whereas Gurobi is a commercial solver that uses highly optimized algorithms and techniques to find exact solutions to optimization problems.

We have provided the CPU time required to solve the problem instances using our Lagrangian heuristic approach in Table 6. We compared our approach with that of the commercial solver Gurobi and found that our method required less CPU time for most problem instances. However, it should be noted that, in a few instances, Gurobi required less CPU time than our method. Overall, our approach showed promising results in terms of CPU time savings compared to the commercial solver.

6. Conclusions

This paper presents a novel method for evaluating the capacity of HSR hub stations that considers both the train arrival problem (TAP) and the train spatio-temporal routing pattern (TSRP), providing a more accurate assessment of the saturation capacity of hub stations.

The proposed optimization model, which incorporates both TAP and TSRP, was developed using the Lagrangian relaxation algorithm to determine the TAP based on the train timetable, resulting in the time distribution and the number of arriving trains. A spatio-temporal operation routing model was then created to compute a non-conflicting station operation schedule based on the data obtained through the TSRP model. Two scenarios were generated to test the model, and the results showed that the method provided improved accuracy and practicality, bringing the calculations closer to the theoretical saturation capacity. However, it revealed a trade-off between the heterogeneity of train stops in the railway network and the passing capacity of the hub station.

This paper assumes that each line connected to the hub station is operating at saturation capacity. However, the number of trains on the lines in each direction can vary enormously at different times. Additionally, the occupancy of the trains approaching within the station is more complex than in the model. Therefore, we should consider the fluctuations in the number of trains in each direction and the intricacies of the internal train occupancy within the station in future studies.

In this paper, we have proposed a Lagrangian-based method for the calculation of passing capacity at a railway hub station. While our method provided a promising solution for the passing capacity calculation problem, there are still areas for future research. One potential direction is to explore the use of heuristic algorithms, such as metaheuristics or evolutionary algorithms, to further improve the computational efficiency of our method. Additionally, as mentioned in the literature review section, the application of reinforcement learning algorithms, such as deep Q-learning or policy gradient, could be an interesting avenue to explore for solving similar optimization problems in the transportation domain. We believe that our work provides a strong foundation for future research in this area. Overall, our proposed method represents a significant step forward in the evaluation of HSR hub station capacity. By considering both the TAP and TSRP, we provide a more comprehensive and accurate assessment of saturation capacity. Our method can assist operators in making more informed scheduling decisions, ultimately improving the efficiency and reliability of railway operations. We believe that this research has important practical implications for the development and management of HSR systems and provides a strong foundation for future research in this area.