Assessing the Compatibility of Railway Station Layouts and Mixed Heterogeneous Traffic Patterns by Optimization-Based Capacity Estimation

Abstract

The operations performance of a railway station depends on the compatibility of its layout and the traffic pattern. It is necessary to determining an adaptable station layout for a railway station in accordance with its complex traffic pattern during the design phase. This paper assesses the railway station layout from a capacity perspective. In particular, this paper addresses an optimization-based capacity estimation approach for the layout variants of a railway station (i.e., the number of siding tracks and the structure of the connections in between) considering the traffic pattern variants. A mixed integer programming model for microscopic timetable compression is applied to calculate the occupation rate of the given traffic pattern with flexible route choices and train orders. A novel “schedule-and-fix” heuristic algorithm is proposed to solve large-scale instances efficiently. In the case study, we evaluate the performance of the schedule-and-fix method compared with the benchmark solvers Gurobi and CP-SAT. Applying the proposed method, we compare the capacity performances of the two station design schemes, i.e., one with a flyover and the other without. The result shows that, for the given instance, building a flyover gains capacity benefits as it reduces the potential conflict in the throat area. However, the level of benefit depends on the combination of trains. It is necessary to build the flyover when the proportion of turn-around trains is more than 70% from the perspective of station capacity.

1. Introduction

1.1. The Compatibility of Station Layouts and Traffic Patterns

The continuous growth of infrastructure investment in developing countries plays a significant role in their economic growth. Railway is a rapid, sustainable, and long-distance transportation system, attracting much attention in the field of infrastructure investment. Similar to typical infrastructure investments, railway infrastructure investments are costly and require extensive research on the designs in the planning phases. Railway stations have sophisticated layouts for operating complex and time-consuming train movements; thus the layout have significant impacts on the performance of the station, e.g., the number of tracks next to passenger platforms, the connection between station tracks, the length of the track used, and the connectivity between the tracks and the adjacent segments.

For improving the operation efficiency of stations, the layouts should be properly designed according to the traffic patterns (i.e., the combinations of various types of trains). This task is particularly challenging when the traffic pattern in the station is complex. For stations connecting more than one railway line, trains running towards different directions are scheduled within the same time slot. These trains might have temporal and spatial conflicts which prevent them being operated simultaneously and reduce the operation performance. An optimized layout design of the station can resolve the conflicts to a large extent by setting up flexible connection between the siding tracks and the open track sections to increase the capacity of the station. Therefore, analyzing the compatibility of the station layout and the traffic pattern is the key step for evaluating the design of the station layout.

An essential evaluation metric of the station layout from the operation perspective is the station capacity. Station capacity, defined as the maximum number of trains that can arrive at/depart from the station in a specific time interval [1], is an essential performance index justifying if the design scheme satisfies the predicted traffic demand (i.e., the required number of trains operated in the station). Various factors determine station capacity, including the number of siding tracks and the signal system’s performance. Furthermore, the connection between siding tracks to open track segments significantly impacts the station capacity as well. However, the well-designed connections resolve the potential conflicts of train movements and therefore improve the capacity. For example, building a flyover at the throat area (i.e., the area with many switches connecting the open track segments and siding tracks) can resolve the conflict between the arrival and departure operation, therefore increasing the station capacity. As shown in Figure 1, the layout shown in Figure 1b with a flyover avoids the arrival and departure conflicts shown in Figure 1a. Therefore, a higher capacity can be achieved.

However, the construction of a flyover is a costly project. The land acquisition and demolition for land utilization require a considerable budget. The design, building, and maintenance of the flyover also need a long-term financial outlay from the railway infrastructure manager. Furthermore, many issues concerning land use planning, such as environmental impact assessment (EIA) and public welfare evaluation, should be carefully investigated to maximize the profit of constructing the railway station. For example, it would be uneconomical to use the layout of Figure 1b instead of Figure 1a if the potential conflicts were infrequent, since the capacity improvement from flyover construction is not fully utilized in practice. Therefore, capacity estimation of stations is necessary to determine the station performance applying particular layouts. The compatibility of the station layout design and its traffic pattern, which impacts the efficiency of the infrastructure investment, is determined by the performance under specific traffic patterns.

The accuracy of the capacity estimation is determined by the infrastructure and train movement modeling, the applied operation parameters, and the solution algorithm. In this paper, we apply a timetable compression method for estimating the station capacity. Specifically, based on the initially designed timetable with specific traffic patterns, we apply a mathematical model to compress the timetable and calculate the makespan (i.e., the shortest time for finishing all train operations), which implicitly tells the maximum number of scheduled trains with such traffic patterns in a certain period. The capacity estimation method proposed in this paper helps estimate the station performance under complicated mixed train traffic and decide the best capacity improvement measures. The level of the station capacity improvement from building a flyover can be quantitively estimated by this proposed method. The result can be used to determine if a station layout is worth building from the aspect of train traffic management.

The remainder of the paper is organized as follows. Section 1.2 summarizes the literature associated with the railway station capacity estimation, followed by the contribution statements of this paper in Section 1.3. Section 2 describes the modeling of the railway station infrastructure, train movements, and the occupation rules of the resources. Based on the description of Section 2, Section 3 proposes a mixed integer programming model and corresponding solution method for timetable compression, considering the flexible route choices and train orders. One can compute the occupation rate of the derived compressed timetable to estimate the railway capacity under certain mixed traffic combinations. Section 4 provides the results and discussions of a series of case studies displaying the performance of the solution method and showing the variation of the station capacity applying different design schemes, train combinations, as well as operational parameters. The applied methodology and the central finding of this paper are concluded in Section 5.

1.2. Literature Review of Station Capacity Estimation

Railway infrastructure capacity is typically defined as the total number of possible paths in a defined time window, considering the actual path mix or known developments, respectively, and the IM (infrastructure manager)’s assumptions about nodes, individual lines, or parts of the network with respect to market-oriented quality [1]. As part of the railway infrastructure, the railway station inherits the capacity concept, which can be derived as the maximum number of scheduled trains operated in the station within a defined time window with given train combinations and other extra operation requirements. Khadem-Sameni et al. [2] introduce the problems and the current challenges of railway capacity in Britain.

Capacity Estimation Methods

Typical capacity estimation methods for railway stations include analytical, simulation, timetable compression, and optimization methods.

(1)

Analytical method

Analytical methods use mathematical formulations to calculate the station capacity with some input information directly. In general, the input of the analytical method is less than in the timetable-related method, which enables the method to be applied in the infrastructure design phase when detailed data is missing. However, the accuracy of the result derived from the analytical method depends on the parameters. Malavasi et al. [3] analyze three classical analytical methods for station capacity estimation, namely the Potthoff method, Probabilistic method, and Deutsche Bahn method, and compare the computational results of the three methods in two stations. Wang et al. [4] provide a capacity enhancement measurement by transforming the existing fixed train-approaching locking section into a variable mode. An analytical formulation for calculating the theoretical capacity is applied to estimate the level of capacity enhancement. Veselý [5] proposes an analytical method for calculating the railway station capacity.

Some research applies queueing theory for modeling the stochastic procedures of the operation within stations. Bychkov et al. [6] apply a queuing network to describe the operation of railway stations. The yards of a railway station are modeled as nodes of a queuing network, and the train operations are modeled as flows in the network. A simulation approach is applied to solve the model. Yuan and Hansen [7] estimate the knock-on delays of trains caused by route conflicts and late transfer connections by a stochastic analytical model. The model is applied for optimizing the station capacity utilization of The Hague Holland Spoor by setting an appropriately scheduled buffer time. Corriere et al. [8] investigate the impact of reliability on station capacity and propose a logic fuzzy model to estimate the theoretical station capacity considering the frequency of accidents.

(2)

Simulation method

Microscopic simulation is commonly used for estimating the station capacity, especially when the uncertainty of train operation is considered. Han et al. [9] present a railway station Infrastructures Representing Model (IRM) for fixed equipment. An analytical method based on the occupation time of switch groups and tracks is applied to compute the overall station capacity. Furthermore, a microscopic simulation method is also applied to estimate the capacity of a passenger station. Zhong et al. [10] use a mesoscopic simulation method for analyzing and calculating the carrying capacity of railway passenger stations, where the arrival time distribution of trains is considered in the generation of train movements. Bulíček et al. [11] propose an idea to increase the station capacity by adding a switch point area. They use an analytical and a mesoscopic simultaneous stochastic simulation model to verify the effectiveness of the capacity increment measurement. Three infrastructure variants are evaluated. The microscopic simulation method can describe and perform the station operations in a very detailed manner, but it requires sophisticated input data (e.g., track layout, parameters of the signaling system, and train timetable), which limit its implementation in the infrastructure designing phase.

(3)

Data-driven approaches

The realistic historical operation data of stations can be used for analyzing the practical capacity utilization. The train delay and the occupation rate of track circuits and platforms can reveal the bottleneck of the station capacity. Armstrong and Preston [12] study the relationship between capacity provision (utilization) and service quality using a data-driven method. Historic timetables and delay data are used to investigate the relationships to determine an appropriate station capacity utilization level. Yuan and Hansen [13] conducted an empirical investigation based on historical data to estimate the station capacity utilization of the Hague HS station. They concluded that the buffer times between trains and their distribution affect the propagation of train delays.

(4)

Extended UIC Code 406 timetable compression method

The timetable compression method is a well-known capacity estimation method mentioned and recommended by the UIC code 406 leaflet. The station capacity is denoted by the capacity occupation rate of a compressed timetable, where the slack times between trains are removed as much as possible. The original UIC Code 406 timetable compression method is used to determine the capacity of railway sections on a macroscopic level. Necessary modifications, including the topology description of the station, the train movement description, and the resource occupation rules, are required when applying the method on stations (typically microscopic level). Landex [14] uses a series of capacity estimation methods, i.e., an adapted UIC 406 capacity method, an analytical method, and an optimization method for analyzing and improving the station capacity. These methods consider the probability of conflicts and train arrival delays. Johansson and Weik [15] proposed a UIC 406-based method at the station level for long-term infrastructure planning. The method is timetable-independent as the workflow consists of a pattern train generation and a timetable generation procedure. Zhong et al. [16] compare a combination–reconstruction (ComRec) method, a triangular-gap-problem method, and a max-plus algebra method for generating compressed timetables and show that these three methods are equivalent. Kavička et al. [17] apply the software tool MesoRail based on the UIC 406 method to calculate the occupation rate of railway stations. Lindner [18] analyzes the problem when applying the UIC 406 method and concludes that the UIC 406 compression method can only offer significant results if the user evaluates an infrastructure that ensures conflict-free station areas. Gašparík [19] developed a conceptual framework for an easier evaluation of occupation time in the train traffic diagram based on UIC 406.

Note that in the UIC Code 406 leaflet [1] and its updated version [20], the adaptability of the timetable compression method applied to the station is not discussed and verified. Many issues must be tackled when applying the timetable compression method at the station level, such as the train route choice, the train order determination, and the occupancy rules of track circuits.

(5)

Optimization approach

Optimization approaches build mathematical programming models to directly solve the station capacity, which can be categorized into timetable-independent and timetable-dependent methods based on the role of timetables.

Timetable-independent optimization approaches describe railway traffic in a macroscopic manner, neglecting details of traffic patterns on timetables. The capacity estimation results are regarded as “absolution capacity” or “theoretical capacity”. These methods are useful in the infrastructure planning phase when the traffic pattern of the station is not determined. Sameni et al. [21] apply a DEA method to investigate the technical efficiency and service effectiveness of railway stations. Various impact factors, including the number of platforms, the fraction of through lines, and the number of trains with scheduled stops, are ranked according to their contribution to the evaluation indices. Jovanović et al. [22] propose a two-stage optimization approach to estimate the theoretical capacity without predetermined timetables, where the first stage determines the compatible route sets, and the second stage determines the optimum sequence of the route sets. The conflicts of routes are described as a graph coloring problem, and the total follow-up time is minimized by a traveling salesman problem.

Timetable-dependent optimization approaches often conduct timetable saturation, i.e., schedule a fully saturated timetable using the trains from a given train pool. The station capacity is then regarded as the total number of scheduled trains in the saturated timetable. Ignatov and Naumov [23] apply an MIP model to insert additional trains to a basic timetable considering random delays for increasing railway station capacity. Sels et al. [24] propose an optimum track allocation problem for trains to estimate the station capacity. It considers the actual, current, as well as future train set scenarios with increasing traffic. The module is fully integrated with the software named Infrabel. Guo et al. [25] solve the station carrying capacity problem and consider train set utilization constraints. The minimum turn-around time of trains, the capacity of vehicle depots, as well as the entering and exiting procedure, are considered. Dollevoet et al. [26] include the capacities (i.e., the platform assignment) of the stations when developing a train delay management model. Javadian et al. [27] develop an optimization formulation and a simulated annealing algorithm to determine the capacity of rail yards.

The above methods are compared in

Table 1. Comparison of the solution methods of railway capacity estimation.

Publication	Problem	Model Category	Solution Method
Malavasi et al. [3]	Station capacity	Analytical	Calculation formulation and parameter calibration
Wang et al. [4]	Line capacity	Analytical	Calculation formulation and parameter calibration
Veselý [5]	Station capacity	Analytical	Calculation formulation and parameter calibration
Bychkov et al. [6]	Station capacity	Analytical	Queuing network
Yuan and Hansen [7]	Knock-on delay estimation	Analytical	Stochastic model
Corriere et al. [8]	Station capacity	Analytical	Logic fuzzy model
Han et al. [9]	Station capacity	Analytical + Simulation	Microscopic simulation
Zhong et al. [10]	Station capacity	Simulation	Mesoscopic simulation
Bulíček et al. [11]	Station structure improvement	Simulation	Mesoscopic simulation
Armstrong and Preston [12]	Station capacity	Data-driven	Statistical
Yuan and Hansen [13]	Station capacity	Data-driven	Statistical
Landex [14]	Station capacity	UIC 406	Timetable compression via simulation
Johansson and Weik [15]	Station capacity	UIC 406	Timetable compression via optimization
Zhong et al. [16]	Station capacity	UIC 406	ComRec + triangular-gap-problem + max-plus algebra
Kavička et al. [17]	Station capacity	UIC 406	MesoRail
Gašparík [19]	Station capacity	UIC 406	Conceptual framework
Sameni et al. [21]	Technical efficiency and service effectiveness estimation	Optimization	Data envelopment analysis
Jovanović et al. [22]	Station capacity	Optimization	Two-stage optimization method
Naumov [23]	Station capacity improvement	Optimization	MIP model
Sels et al. [24]	Station capacity	Optimization	MIP for track allocation
Guo et al. [25]	Station capacity	Optimization	MIP
Dollevoet et al. [26]	Station capacity	Optimization	Train delay management model
Javadian et al. [27]	Station capacity	Optimization	Simulated annealing

.

In the above research, the capacity estimation in the stations with complex structures is considered difficult. The analytical method has unknown parameters for describing the capacity loss due to the traffic pattern, which is difficult to calibrate. These parameters also vary from station to station. The improved UIC 406 methods can only investigate the station capacity with a certain traffic pattern and are not able to explore the impact of different traffic patterns on the capacity variation. The timetable saturation methods have solution efficiency issues and are difficult to apply in large-scale problems, especially for those with heavy traffic. These drawbacks limit the application of the station capacity estimation method in realistic railway station design tasks.

1.3. Contribution Statements

To our knowledge, although many studies investigate the station capacity estimation problem differently, there is still a knowledge gap between the theory and the practice. In particular, train timetable compression methods considering flexible track assignments, route choices, and train operation orders are significantly less, as modeling the complex train movements with multiple stages (i.e., shunting, arrival, departure, and turn-around in between) and the corresponding resource occupations are difficult. Furthermore, the effective solution methods for solving the large-scale capacity estimation optimization model are still in shortage and need further development.

Therefore, we propose a mixed integer programming model and an associated solution algorithm to compress the given timetable while allowing flexible route choice and train order modification. The contributions of this paper are as follows.

• A mixed integer programming model is proposed for estimating the station capacity considering the heterogeneous traffic within the station for infrastructure construction decision-making purposes. The model considers flexible route choices and train orders of occupying track circuits at a microscopic level, where the train operations with the uncertain number of multiple movements can be described.
• A novel “schedule-and-fix” heuristic approach for solving large-scale problems is applied. Compared with MIP solver Gurobi and CP-SAT, the proposed heuristic can obtain feasible solutions very effectively with remarkable qualities.
• From a capacity perspective, this research investigates two typical station layouts (i.e., with or without flyover for departure trains). The flyover is considered necessary to build when the proportion of turn-around trains exceeds 70%. The capacity improvement difference of building a flyover by various train combinations and operation parameters is evaluated.

In general, our proposed timetable-based station capacity estimation method can overcome the drawback of the UIC 406 method to investigate the station capacity with flexible route choices and train sequences. The proposed heuristic method shows the potential of solving the large-scale problem in an acceptable short time, which enables the application of the method in the station design task.

2. Modeling the Microscopic Train Operation for Stations

2.1. Modeling the Station Layout and Signal Facilities

2.1.1. Rail Sections within a Station

A railway station consists of many branching rail sections, which allow trains to drive between the borders of the station and their dwelling tracks. In order to describe the routes that train traverses, we need to build the topological model of the rail sections within stations. Four types of equipment can split rails into sections, including home signals, departure signals, switches, and insulation joints. The splitting of the rail sections within a station can be referred to in Figure 2.

The entire layout of a station can be described as an undirected network $G(N,L)$, where $N$ is the node set, and $L$ is the link set. A rail section can be regarded as an undirected link of the network, denoted by $l\in L$. A splitter can be regarded as a node of the network, denoted by $n\in N$.

2.1.2. Cells within a Station

Rail sections are clustered into cells according to the track circuit design of the interlocking system. A cell is denoted by $c$, and the cell set of the entire station is $C$, where $c\in C$. The link set $L_c$ includes the rail sections that belong to cell $c$. For example, in Figure 2, the rail sections in the red dashed rectangle form a cell, as they belong to the same track circuit. Note that according to the principle of interlocking system design, a rail section can and can only belong to one cell, namely $\bigcap _{c\in C}{L}_c=\varnothing$.

According to the working mechanism of the interlocking system, a cell can be used by at most one train at a specific moment. Therefore, the concept of “cell” plays a critical role in detecting and resolving the conflict of train traffic in a station.

2.2. Heterogeneous Train Movement Modeling

We assume that a train cannot be separated in the station. A train can only enter from a border node and leave the station at the other border node. In between, the train can only stop at the siding track for a duration. In other words, a train cannot stop at any rail section except for the siding track.

2.2.1. Train Arrival, Departure, and Dwell Movements

Only three types of train movements can happen in stations, namely arrival, departure, and dwell movement, as shown in Figure 3. We use $e$ to denote a train movement and use three movement sets, namely $E_{\mathrm{A}}$, $E_{\mathrm{D}}$, and $E_{\mathrm{W}}$ to include all arrival, departure, and dwell movements separately. Each movement has its beginning and ending time, which can be represented by $a_m$ and $d_m$, respectively.

• Arrival movement: An arrival movement implies that the train enters from the corresponding arrival border of the station and runs towards a siding track.
• Departure movement: A departure movement implies that the train leaves from the siding track and runs towards the border node for its departure.
• Dwell movement: Although no displacement of the train happens when a train dwells at the siding track, we still propose a unique movement to describe the train dwelling for unification purposes. A dwell movement denotes the train stop at a siding track for a specific duration. Note that if the train passes through the station without stopping, the dwell movement can be regarded as a dummy movement with a 0-time duration.

The movement chain with multiple arrival, departure, and dwell movements can describe the heterogeneous train traffic within different directions and train types, as well as the route choice within the station.

2.2.2. Route Assignment of the Movements

Each movement must be assigned an associated train route to finish its physical displacement. For each movement $m$, we generate the possible train route set $R_m$ according to the starting and ending point matching, the operation facility requirements (e.g., the train with boarding and alighting operation must select a dwell route with a platform), and other conditions.

For train route set generation, we propose a tag-matching method. On the one hand, the route matching tag $𝓉$ is a descriptive string. For example, if a dwell route can only serve short coupling trains because of the length limitation, it would be marked “SHORT” as a tag. For train route $r$, we define a route-matching tag set ${\mathcal{T}}_r$ in which the descriptive pattern of the route is included. On the other hand, for train movement $m$, we define an allow route matching tag set ${\mathcal{T}}_m^{\mathrm{a}\mathrm{l}\mathrm{l}\mathrm{o}\mathrm{w}}$ and a deny route matching tag set ${\mathcal{T}}_m^{\mathrm{d}\mathrm{e}\mathrm{n}\mathrm{y}}$. The movement $m$ is possible to select the train route $r$ only when all allow matching tags in ${\mathcal{T}}_m^{\mathrm{a}\mathrm{l}\mathrm{l}\mathrm{o}\mathrm{w}}$ are in ${\mathcal{T}}_r$, and no deny matching tag in ${\mathcal{T}}_m^{\mathrm{d}\mathrm{e}\mathrm{n}\mathrm{y}}$ is in ${\mathcal{T}}_r$ at the same time. Therefore, we can generate the train candidate route set $R_m$ by the following formulation.

$$R_m=\left\{r\in R|\left({\mathcal{T}}_m^{\mathrm{allow}}\subseteq {\mathcal{T}}_r\right)\wedge \left({\mathcal{T}}_r\cap {\mathcal{T}}_m^{\mathrm{deny}}=\mathrm{\varnothing }\right)\right\}$$

(1)

2.3. Cell Occupation Rules of Movements

A train movement $m$ occupies a series of track circuits included in the cell set $C_m$ in a predetermined sequence. The cell set $C_m$ is generated by the following formulation.

$$C_m=\left\{c\in C_r|\forall r\in R_m\right\}$$

(2)

Note that only the cells on the selected route are occupied. The starting and ending occupation time of a cell by a movement is determined by the working principle and the performance of the interlocking system, as well as the train length and dynamic performance.

In this paper, we assume the station applies a so-called “route-lock-section-release” interlocking mechanism (Lu et al. [28]). Under this principle, all corresponding cells begin to be occupied simultaneously once the route is established. However, the cells are released (occupation ends) once the train leaves. In other words, the cells occupied by a movement are released one after another by a specific sequence. The detailed parameter estimation method can be referred to in Hansen and Pachl [29]. Based on the working principle of the interlocking system, the preoccupation and release time of the track circuit can be calculated according to the operation procedure of interlocking systems, the length of tracks, the breaking distance, and the velocity of trains. The concrete preoccupation and release time of different movements can be calculated. In this paper, we assume that the length and the arrival and departure velocity of trains are known, which means that we can calculate the relative time of the starting and ending time of cell occupation with the beginning and ending time of the movement. Therefore, analytical or simulation methods can estimate the cell occupation time.

Note that the passing through (without stopping) movement is regarded as a special dwell movement, i.e., the dwell movement with 0 dwell duration. A passing-through train’s arrival and departure speeds are significantly different from the train with stoppings. Furthermore, the station route establishment procedure is also different (For the train passing through without stopping, the arrival and departure routes are simultaneously established).

3. Timetable Compression Model for Station Capacity Estimation

3.1. Mathematical Model for Timetable Compression

We propose a combinatorial optimization model to compress a timetable for the capacity estimation purpose. Specifically, we build a mixed integer programming model minimizing the makespan of the timetable, subject to the train route selection, movement duration, cell occupancy constraints, as well as other side constraints. The notations used in the mathematical programming are listed in

Table 2. Notations.

Notations	Descriptions
Elements and sets
$Q$	A constant number that is big enough
$F$	Train set
$f$	Train element
$M_f$	Movement set of train $f$ at the station
$m$	Movement element
$R_m$	The possible route of movement $m$
$r$	Route element
$C_r$	The occupied cell set when the train is using route $r$
$C_m$	The possible cell set occupied by movement $m$
$c$	Cell element
Parameters (numbers)
${\delta }_m^{min}$, ${\delta }_m^{max}$	The minimum and maximum duration of movement $m$
$l_m^{dep}$, $h_m^{dep}$	Earliest and latest ending time of movement $m$
$l_m^{arr}$, $h_m^{arr}$	Earliest and latest beginning time of movement $m$
${\theta }_{r,c}$	The preoccupation time of cell $c$ when the movement is using route $r$
${\beta }_{r,c}$	The additional release time of cell $c$ when the movement is using route $r$
${\mathsf{\eta }}_{r_1,r_2}$	A binary parameter, 1 indicates route $r_1$ has a physical connection with route $r_2$, 0 otherwise
Projection
$g\left(m\right)$	A projection from one movement to the other. $m^{\prime }=g\left(m\right)$ indicates that, for the same train, the movement $m^{\prime }$ happens immediately following movement $m$. If the movement $m$ is the last movement of the train, $g\left(m\right)=m_{null}$

and

Table 3. Variables.

Variables	Descriptions
$a_m$	The beginning time of movement $m$
$d_m$	The ending time of movement $m$
$x_{m,r}$	Binary variable, 1 indicates movement $m$ applies route $r$ to operate, 0 otherwise.
$y_{c,m_1,m_2}$	Binary variable, 1 indicates that movement $m_1$ occupies cell $c$ earlier than movement $m_2$, 0 otherwise.
$s_{m,c}$	The starting time of movement $m$ occupying cell $c$
$e_{m,c}$	The ending time of movement $m$ occupying cell $c$

.

The objective function is to minimize the summation of the finishing time $d_m$ of all movements. This objective implies that the optimum solution ensures a “compressed” station train schedule with the minimum makespan.

Model 1

$$\min {\displaystyle \sum _{f\in F}^{}}{\displaystyle \sum _{m\in M_f}^{}}{d}_m$$

(3)

Subject to:

(1) Movement duration constraint

$$d_m-a_m\ge {\delta }_m^{min}\hspace{1em}\forall f\in F,m\in M_f$$

(4)

$$d_m-a_m\le {\delta }_m^{max}\hspace{1em}\forall f\in F,m\in M_f$$

(5)

(2) Train conservation constraint

$$d_m=a_{g\left(m\right)}\hspace{1em}\forall f\in F,m\in M_f,g\left(m\right)\ne m_{null}$$

(6)

(3) Train route connection constraint

$${\displaystyle \sum _{r_2\in R_{g\left(m\right)}}^{}}\left(1-{\mathsf{\eta }}_{r_1,r_2}\right)\times x_{g\left(m\right),r_2}+\left(1-x_{m,r_1}\right)\times Q\ge 0\hspace{1em}\forall f\in F,m\in M_f,g\left(m\right)\ne m_{null},r_1\in R_m$$

(7)

$${\displaystyle \sum _{r_2\in R_{g\left(m\right)}}^{}}\left(1-{\mathsf{\eta }}_{r_1,r_2}\right)\times x_{g\left(m\right),r_2}\le \left(1-x_{m,r_1}\right)\times Q\hspace{1em}\forall f\in F,m\in M_f,g\left(m\right)\ne m_{null},r_1\in R_m$$

(8)

(4) Movement time window constraint

$$\overline{d_m}-l_m^{dep}\le d_m\le \overline{d_m}+h_m^{dep}\hspace{1em}\forall f\in F,m\in M_f$$

(9)

$$\overline{a_m}-l_m^{arr}\le a_m\le \overline{a_m}+h_m^{arr}\hspace{1em}\forall f\in F,m\in M_f$$

(10)

(5) Route selection constraint

$${\displaystyle \sum _{r\in R_m}^{}}{x}_{m,r}=1\hspace{1em}\forall f\in F,m\in M_f$$

(11)

(6) Cell occupation time constraint

$$s_{m,c}+Q\times \left(1-x_{m,r}\right)\ge a_m+{\theta }_{r,c}\hspace{1em}\forall f\in F,m\in M_f,r\in R_m,c\in C_r$$

(12)

$$s_{m,c}\le a+{\theta }_{r,c}+Q\times \left(1-x_{m,r}\right)\hspace{1em}\forall f\in F,m\in M_f,r\in R_m,c\in C_r$$

(13)

$$e_{m,c}+Q\times \left(1-x_{m,r}\right)\ge d+{\beta }_{r,c}\hspace{1em}\forall f\in F,m\in M_f,r\in R_m,c\in C_r$$

(14)

$$e_{m,c}\le d+{\beta }_{r,c}+Q\times \left(1-x_{m,r}\right)\hspace{1em}\forall f\in F,m\in M_f,r\in R_m,c\in C_r$$

(15)

(7) Cell occupation conflict constraint

$$\left(1-y_{c,m_1,m_2}\right)\times Q+s_{m_2,c}\ge e_{m_1,c}\hspace{1em}\forall f_1\in F,f_2\in F-f_1,m_1\in M_{f_1},m_2\in M_{f_2},c\in C_{m_1}\cap C_{m_2}$$

(16)

$$y_{c,m_1,m_2}+y_{c,m_2,m_1}=1\hspace{1em}\forall f_1\in F,f_2\in F-f_1,m_1\in M_{f_1},m_2\in M_{f_2},c\in C_{m_1}\cap C_{m_2}$$

(17)

(8) Variable domain constraint

$$x_{m,r}\in \left\{0,1\right\}\hspace{1em}\forall f\in F,m\in M_f,r\in R_m$$

(18)

$$y_{c,m_1,m_2}\in \left\{0,1\right\}\hspace{1em}\forall f_1\in F,f_2\in F-f_1,m_1\in M_{f_1},m_2\in M_{f_2},c\in C_{m_1}\cap C_{m_2}$$

(19)

$$a_m,d_m\in \mathbb{R}\hspace{1em}\forall f\in F,m\in M_f$$

(20)

$$s_{m,c},e_{m,c}\in \mathbb{R}\hspace{1em}\forall f\in F,m\in M_f,c\in C_m$$

(21)

The objective function of Formulation (3) is to minimize the total finishing time of all movements of the given train, implying that the timetable is compressed. Constraints (4) and (5) are movement duration constraints, indicating that the duration of a movement should be between a given min–max range. Constraint (6) is the train movement conservation constraint between two consecutive movements, implying that a movement’s beginning time is identical to its previous movement’s ending time. Constraint (7) and (8) are train route connection constraints, ensuring that the starting position of a movement is identical to the ending position of its previous movement. Constraint (9) and (10) ensure that a movement happens within a given time window. Constraint (11) is the route selection constraint, implying any movement can and can only choose one route to operate. Constraints (12) to (15) are used for cell occupation time calculation, specifying the cells’ starting and ending occupation time for each movement. Constraints (16) and (17) are the conflict avoidance constraints, making sure that the occupancy times of a cell are without overlapping. Constraints (18) to (21) are variable domain constraints.

3.2. Solution Method

The model is a complex mixed-integer programming model. In this study, we apply two MIP solvers, namely Gurobi and CP-SAT from Google OR-Tools, to obtain the solution performance benchmarks. Gurobi is a MILP solver that applies exact algorithms, including branch-and-bound, cutting plane, etc., while CP-SAT is a constraint programming solver handling the MILP model with heuristic solution approaches. Note that the selection of the MIP solver is in accordance with the research habits of our research team. As the model is interpreted in a standard format, the researcher and developer can select any solvers that support MIP models. The detailed code of the model building and solution codes can be referred to in the git repository [30].

The station capacity estimation model is a large-scale combinatorial problem, and it is not easy to solve directly by MILP solvers. In order to solve the model efficiently, a fast heuristic strategy for decomposing the original problem into multiple phases of subproblems is necessary. Particularly, in this paper, we introduce a schedule-and-fix heuristic approach, which is a train-by-train iterative optimization method, to decompose the original problem into a multiple-phase optimization problem to eliminate the solution space. Only one train is scheduled in each iteration. After each iteration, the scheduled trains, as well as the binary variables, including the route choice variable $x_{m,r}$ and the movement variable $y_{c,m_1,m_2}$ are fixed. Thus, in the next iteration, a train can be ‘inserted’ into the timetable derived from the last iteration. Note that the time-related variables $a_m$, $d_m$, $s_{m,c}$, and $e_{m,c}$ remain flexible and can be changed during the iterations. The detailed algorithm of the schedule-and-fix approach is shown in Algorithm 1.

Algorithm 1: the schedule-and-fix solution approach
Input: The elements, sets, and parameters listed in Table 2.
Output: The optimized solution of Model 1 ($\mathit{X}$).
1:	Initialization. Let candidate train set $F_0^{\mathrm{cand}}$ to contain all trains and let the scheduling train set $F_0≔\varnothing$. Let the iteration index $i≔1$. Fixed variable set ${\mathcal{V}}_x$ and ${\mathcal{V}}_y$. Global solution $\mathit{X}$.
2:	While the candidate train set $F_{i-1}^c\ne \varnothing$
3:	Randomly select a train $f^{*}\in F^0$.
4:	Let $F_i^{\mathrm{cand}}≔F_{i-1}^{\mathrm{cand}}-f^{*}$, and $F_i≔F_{i-1}\cup \left\{f^{*}\right\}$.
5:	Build the Model 1(i) with $F≔F_i$.
6:	Add additional variable fixing constraints, according to   $x_{m,r}=x_{m,r}^{*}\hspace{1em}\forall f\in F,m\in M_f,r\in R_m,x_{m,r}^{*}\in {\mathcal{V}}_x$,   $y_{c,m_1,m_2}=y_{c,m_1,m_2}^{*}\hspace{1em}\forall f_1\in F,f_2\in F-f_1,m_1\in M_{f_1},m_2\in M_{f_2},c\in C_{m_1}\cap C_{m_2},y_{c,m_1,m_2}^{*}\in {\mathcal{V}}_y$.
7:	Solve Model 1(i) by an MIP solver and obtain the solution ${\mathit{X}}_{\mathit{i}}$.
8:	Update the global solution $\mathit{X}={\mathit{X}}_{\mathit{i}}$ with the solution of Model 1(i). Mark the solution value $x_{m,r}^{*}$ and $y_{c,m_1,m_2}^{*}$ to ${\mathcal{V}}_x$ and ${\mathcal{V}}_y$, respectively.
9:	Output solution $\mathit{X}$, and terminate the algorithm.

For variable $x_{m,r}$, the program adds additional variable fixing constraints directly. However, for variable $y_{c,m_1,m_2}$, adding the corresponding variable fixing constraints will result in an enormous model size, which makes building and solving the model time consuming. Therefore, we replace the “adding variable fixing constraint” strategy by a “redundant constraint removing” strategy. Specifically, we first check if the variable $y_{c,m_1,m_2}$ is fixed (i.e., $y_{c,m_1,m_2}^{*}\in {\mathcal{V}}_y$). If variable $y_{c,m_1,m_2}$ is fixed, the corresponding variable $y_{c,m_1,m_2}$ is skipped. Furthermore, we apply the following constraint to replace the corresponding Constraint (16) if $y_{c,m_1,m_2}^{*}=1$.

$$s_{m_2,c}\ge e_{m_1,c}\hspace{1em}\forall f_1\in F,f_2\in F-f_1,m_1\in M_{f_1},m_2\in M_{f_2},c\in C_{m_1}\cap C_{m_2}$$

(22)

Meanwhile, the corresponding Constraint (17) is also neglected. Therefore, the number of binary variables $y_{c,m_1,m_2}$ and associated constraints (16) and (17) can be remarkably reduced to accelerate the model-building and solving process.

4. Case Study

4.1. Numerical Experiments

The MILP model is composed in Python 3.9.6, applying the Google OR-Tools toolkit module (version 9.6). The MILP solver is set to be Gurobi (version 9.5.0) and CP-SAT embedded in Google OR-Tools, respectively. This program is run on a personal computer with Windows 11 running on AMD R9-5900 CPU and 64 GB internal memory.

The data applied in the case study is a newly designed station on a newly built high-speed railway. The names of lines and stations are anonymized here for confidentiality reasons. The station is equipped with nine tracks. In particular, seven tracks (namely 9G, 7G, 5G, 3G, 4G, 6G, and 8G) are located next to passenger platforms, allowing passengers to embark and alight. The other two tracks (IG and IIG) connect the mainlines outside the station and only serve the trains passing through without stopping. An EMU depot is connected to the station by two extended tracks as well at the left side of the station in Figure 4. The left and right side of the station connects to the direction of BD and HD, respectively.

In the design stage, there are two design schemes that are considered and should be further estimated in terms of investment and capacity, as shown in Figure 4. Scheme-1 (“S1” for short), shown in Figure 4a, is the simplified scheme without the flyover for a turn-around at the left side. The turn-around trains from BD to BD might have conflicts with the arrival trains from HD to BD. Scheme-2 (“S2” for short), shown in Figure 4b, on the contrary, designs a flyover for train turn-around on the left side. With this flyover, the turn-around trains can depart from the station from track 9G and 7G without interfering with the arrival trains from HD to BD. These trains would run towards the mainline at a block post (i.e., a signal control point) with a switch outside the station.

Intuitively, in Scheme-2, the flyover for turn-around trains can avoid the conflict between the arrival trains from BD so as to increase the station capacity. In the numerical experiment, we will estimate the capacity variation by applying the turn-around flyover quantitatively.

We apply a default heterogeneous train composition, as shown in Figure 5. There are ten types of trains with different running directions. The trains granted “HDex” and “BDex” are the departure trains leaving the depot and bound for the HD and BD directions, respectively. The trains granted “HDen” and “BDen” are the termination trains from the HD and BD directions, respectively, going back to the depot. The trains granted “BDtr” and “HDtr” are the turn-around trains. They change the running direction in the current station. The trains granted “X” and “S” are trains passing through without stopping, while the trains granted “XT” and “ST” are trains passing through with intermediate stops in the current station.

The interlocking system of the station applies a “route-lock-section-release” mechanism. Particularly, the track circuits on a route might release asynchronously. The track circuits of the arrival route located on the outer side might release earlier than the inner side, and the track circuits of the departure route located on the outer side might also release later than the inner side. In the case study, we apply realistic technical data, including the minimum preoccupation and release time, the turn-around time, and the stop time with regard to the existing railway lines using the same signal system. The brief arrival and departure headway aggregated from the cell occupation time is shown in

Table 4. Default track circuit occupation time parameters (in seconds).

Train Movement	Min Preoccupation Time		Min Release Time
	Stop	Non-Stop	Stop	Non-Stop
Arrival	240	300	0	0
Departure	60	300	180	60

. The detailed preoccupation and release time of the routes can be referred to in Appendix B. The minimum and maximum required dwell time is shown in

Table 5. Required dwell time parameters (in seconds).

Train Type	Minimum Dwell Time	Maximum Dwell Time
Before entering depot	900	1800
After exiting from depot	900	1800
Turn-around	720	1200
Passing through with stop	120	900

.

4.1.1. Computational Performance Comparison

We first conduct a series of numerical experiments concerning the solution quality and efficiency of the model applied. Specifically, we compare the computational performance (i.e., solution times, objective values, and convergence procedure) of the Gurobi solver, CP-SAT solver, and the schedule-and-fix applying the Gurobi solver (namely Gurobi-fixing) with regard to different numbers of scheduled trains.

(1)

Solution quality analysis

A series of train combination instances of the model with different numbers of trains (from 2 to 20, the combination of trains can be referred to in Appendix A) for station design Scheme-1 and -2 are generated artificially to test the solution time and objective value using different solution methods. The computational time of the instances is reported in

Table 6. The computational times and objective values.

Instance	# Trains	Gurobi			CP-SAT			Gurobi Fixing
		Comp. Time (s)	Obj Value (Min)	Gap (%)	Comp. Time (s)	Obj Value (Min)	Gap (%)	Comp. Time (s)	Obj Value (Min)
Scheme-1	2	<0.1	1920	0.00%	0.1	1920	0.00%	0.0	1920
	4	0.1	8400	0.00%	0.1	8400	0.00%	0.1	8400
	6	1.5	11,940	0.00%	0.5	11,940	0.00%	0.3	11,940
	8	72.2	19,320	0.00%	4.2	19,320	0.00%	0.5	20,820
	10	1336.0	26,760	0.00%	484.7	26,760	0.00%	0.7	27,720
	12	3600.8	37,920	31.46%	3623.7	37,920	36.03%	1.0	40,980
	14	3605.1	47,580	26.26%	3606.7	47,160	35.84%	1.3	51,480
	16	3604.7	57,780	35.97%	3609.6	58,620	43.01%	1.8	61,500
	18	3604.8	74,940	43.58%	3627.1	71,340	46.04%	2.5	79,440
	20	3601.9	83,520	40.96%	3690.5	84,900	48.59%	2.9	94,620
Scheme-2	2	<0.1	1920	0.00%	<0.1	1920	0.00%	0.0	1920
	4	0.5	8400	0.00%	0.1	8400	0.00%	0.1	8400
	6	4.0	11,940	0.00%	0.7	11,940	0.00%	0.3	11,940
	8	64.6	19,320	0.00%	4.2	19,320	0.00%	0.5	20,700
	10	2387.5	26,760	0.00%	253.3	26,760	0.00%	0.6	28,080
	12	3601.2	37,560	30.14%	3606.4	37,440	39.55%	1.1	38,160
	14	3604.9	46,680	29.26%	3604.4	47,220	37.23%	1.4	55,020
	16	3604.5	57,480	37.72%	3610.9	57,240	42.88%	1.9	61,500
	18	3604.7	72,540	43.89%	3610.0	70,980	48.73%	2.6	77,400
	20	3604.0	84,960	43.17%	3607.9	82,200	50.46%	3.1	93,000

. In Table 6, the computational time is recorded in the solution program, including the data loading, model generation, model solution, and data output. The objective value is the true objective value derived from the solver. The MIP gap reported is defined as (Upper bound–Lower bound)/Lower bound.

From Table 6, we can conclude that the model is of computational difficulties as both the commercial solver Gurobi and the open-source solver CP-SAT cannot obtain optimal solutions within 3600 s even if the number of trains is less than 20. For the Gurobi solver, the MIP gaps of the instances of 20 trains are greater than 40% for both Scheme-1 and Scheme-2. On the contrary, the schedule-and-fix heuristic approach proposed in this paper is shown to be very outstanding in terms of computational efficiency compared to the solvers. It takes less than 4 s to obtain feasible solutions for the 20-trains cases. For the small instances (the number of the train is less than or equal to 6), the objective values remain the same as the Gurobi and CP-SAT solvers, which means the optimal solution is obtained by applying the schedule-and-fix approach. However, with the amount of train growth, the objective values are worse than the ones obtained from solvers, as the heuristic nature of the schedule-and-fix approach might be stuck in the local optima in each single-train scheduling iteration. Despite this, the superior computational efficiency of the schedule-and-fix heuristic helps to accelerate the practical-scale experiments. In the following experiments, unless otherwise stated, the reported solution results are derived from the algorithm applying the schedule-and-fix heuristic approach.

From the comparison between Scheme-1 and Scheme-2, the computational times and MIP gaps of Scheme-1 usually perform better than the ones of Scheme-2, as Scheme-1 is without a flyover, and the number of candidate routes is less than Scheme-2. This phenomenon shows that the computational efficiency and quality are influenced by the number of trains and the complexity of the station layout.

(2)

Convergence procedures of the applied methods

The convergence of the instances with 4, 10, and 20 trains from Gurobi, CP-SAT, and schedule-and-fix heuristics are displayed in Figure 6. Among them, the red and green curve shows the upper and lower bound obtained from Gurobi, respectively, while the blue curve shows the current best feasible solution obtained from CP-SAT. The final solutions obtained from the schedule-and-fix heuristic (“S&F Heur.” for short) are displayed using a black dot.

From the convergence process, we can investigate the solution procedure using different methods in-depth. The corresponding instances of Scheme-1 and Scheme-2 generally show similar convergence trends. The optimal solutions are reported for 4-train and 10-train cases, as the Gurobi and CP-SAT can obtain optimal solutions within 3600 s. Gurobi and CP-SAT obtain good quality feasible solutions in very few seconds, while most of the time, the solvers update the lower bound to prove the optimality of the solutions. For the large-scale instances (40-train instances), the lower bounds are difficult to improve using the Gurobi solver.

4.1.2. Sensitivity of Parameters on Computation

(1)

Different objective functions

There are two objective functions for compressing the timetable: only minimizing the movement ending time and simultaneously minimizing the movement starting and ending time. We compare these two objective functions in terms of computational time and solution quality. The computational times, objective values, occupation rate, and the maximum number of trains of the solutions are reported in

Table 7. Solution comparison using different objective functions.

Instances (Scheme-#Trains)	Comp. Time (s)		Obj. Value (s)		Occupation Rate (%)		Capacity (Max #Trains)
	Min d	Min d+a	Min d	Min d + a	Min d	Min d + a	Min d	Min d + a
S1-2	0.0	0.0	1920	3600	0.83%	0.83%	240	240
S1-4	0.1	0.1	8400	14,940	2.04%	2.04%	196	196
S1-6	0.3	0.3	11,940	21,960	2.50%	2.50%	240	240
S1-8	0.5	0.5	20,820	37,800	3.15%	3.15%	254	254
S1-10	0.7	0.6	27,720	51,300	3.15%	3.52%	318	284
S1-12	1.0	1.0	40,980	77,760	4.26%	4.26%	282	282
S1-14	1.3	1.3	51,480	95,580	4.35%	4.35%	322	322
S1-16	1.8	1.9	61,500	115,380	4.35%	4.35%	368	368
S1-18	2.4	2.5	79,440	149,400	5.74%	5.28%	314	341
S1-20	2.9	2.9	94,620	178,740	5.92%	5.93%	338	338
S1-22	3.8	3.8	114,120	226,260	6.20%	6.57%	355	335
S1-24	4.8	4.7	136,320	276,480	7.31%	7.31%	328	328
S1-26	6.0	5.7	164,400	309,600	7.59%	7.59%	342	342
S1-28	7.2	6.8	190,260	348,480	8.06%	8.61%	348	325
S1-30	7.4	7.4	195,480	399,240	7.96%	8.42%	377	356
S2-2	0.1	0.0	1920	3600	0.83%	0.83%	240	240
S2-4	0.1	0.1	8400	14,940	2.04%	2.04%	197	197
S2-6	0.3	0.3	11,940	21,960	2.04%	2.04%	295	295
S2-8	0.5	0.5	20,700	37,620	2.78%	2.78%	288	288
S2-10	0.6	0.7	28,080	52,200	2.69%	2.69%	372	372
S2-12	1.0	1.1	38,160	77,220	4.26%	4.26%	282	282
S2-14	1.4	1.4	55,020	102,240	4.54%	4.54%	309	309
S2-16	1.9	1.9	61,500	116,820	4.54%	4.63%	353	346
S2-18	2.5	2.6	77,400	146,160	5.28%	5.00%	341	360
S2-20	2.9	2.9	93,000	178,560	5.74%	5.74%	348	348
S2-22	4.0	3.8	116,520	217,440	6.94%	6.48%	317	339
S2-24	5.1	4.8	138,780	261,540	7.31%	7.31%	328	328
S2-26	6.2	5.9	146,760	301,320	6.94%	7.96%	374	327
S2-28	7.4	7.0	174,060	344,700	8.15%	8.43%	344	332
S2-30	8.1	7.7	195,900	380,700	8.43%	8.43%	356	356

.

In Table 7, “Min d” denotes the objective function of Formulation (3), while “Min d + a” denotes the following objective function. The computational time is recorded in the solution program, and the objective value is derived from the solver. The occupation rate and capacity are calculated based on the values of the decision variables.

$$\min {\displaystyle \sum _{f\in F}^{}}{\displaystyle \sum _{m\in M_f}^{}}{d}_m+a_m$$

(23)

From Table 7, the study found that, in general, there is no essential difference in the quality of the solutions obtained by the two objective functions. The difference of occupation rates of corresponding instances is less than 1% except for instance S2–26. We consider the solution error due to the non-optimality results in this difference. Therefore, we apply the objective function of minimizing the total ending time of the movements in the following experiments.

(2)

Number of available siding tracks

One major impact factor of station layout on station capacity is the number of available siding tracks, as the siding tracks provide room for train operation (i.e., passenger boarding and alighting, train turn-around, and making necessary technical inspections before going back to or after exiting from the depot). To evaluate the impact of the number of siding tracks on station capacity, we conduct three station layout variants with 9, 7, and 5 available siding tracks, and calculate the corresponding occupation rate with a different number of trains. The computational times and the occupation rates are reported in Figure 7.

Figure 7a shows that the computational time increases exponentially with the number of trains growing. With more siding tracks, the solution space of the instance would be larger, resulting in longer computational time even though the schedule-and-fix heuristic is applied. Specifically, the instance of Scheme-2 usually takes longer computational time than the corresponding instance (with the same trains and available siding tracks) of Scheme-1, as in Scheme-2, the trains departing from track 7G and 9G can choose to leave the station via the flyover or not. This flexibility of route choice enlarges the solution space, thus increasing the solution difficulties.

Concerning the occupation rate, it increases with the number of trains in general. However, the curves show a zig-zag pattern instead of a smooth linear one, as not only the number but the combination of trains influence the occupation rate. Moreover, for the instances that the number of trains is over 15, when the number of available tracks decreases from 9 to 7, the drop in the occupation rate is greater than the one when the number of available track decrease from 7 to 5. One reason for this phenomenon is that fewer available tracks might result in a severe capacity shortage, especially when more trains are scheduled.

(3)

The occupancy rate with the train number growth and the bottleneck

We analyze the growth in occupation rates of different station areas by train numbers. The growing trends of the occupation rates with the growth in train numbers are shown in Figure 8.

In Figure 8, when the train number is less than 10, the differences of occupation rate in the throat and siding track area are not noticeable, which proves that the station layout is designed reasonably in terms of capacity utilization to some extent. When the train number is greater than 20, the siding track area has a higher occupation rate than the throat areas, implying that the siding tracks are likely to be the bottleneck of the station capacity. For the throat areas, the occupation rate of the left throat is slightly higher than that of the right throat, as the left throat has a more complex structure for train arrival, departure, exiting from, and entering to depot. Therefore, the left throat might have more potential conflicts, especially when the number of turn-around trains and exiting/entering depot trains grows.

4.2. The Real-Life Case Study Analysis

In this section, we apply real-life instances with 198 trains operated in the station with the schedule-and-fix heuristic. The train combination is determined according to the operation plan design document. The capacity estimation result reported in this section can be regarded as a reference for flyover building decisions from the perspective of train operations.

4.2.1. Overall Solutions

(1)

Capacity estimation result

In this experiment, we compare two working mechanisms of the signal system, namely route-lock-route-release (RLRR for short) and route-lock-section-release (RLSR for short). Intuitively, the RLSR has less occupation time and thus can achieve higher station capacity. With a given station layout and certain train combinations, we quantitatively estimate the capacity increment of such signal system upgrades.

From

Table 8. Comparison between RLRR and RLSR working mechanisms.

Scheme	Route-Lock-Route-Release (RLRR)			Route-Lock-Section-Release (RLSR)			Capacity Improvement by Applying RLSR
	Occupation Rate	Obj. Value	Capacity	Occupation Rate	Obj. Value	Capacity
S1	48.61%	8,870,760	407	44.91%	8,448,780	441	8.25%
S2	46.67%	8,636,400	424	42.96%	7,597,260	461	8.62%

, we can observe that RLSR can gain 8.25% and 8.62% capacity enhancement for Scheme-1 and Scheme-2, respectively. The compressed timetables of Scheme-1 and Scheme-2 following the RLSR mechanism are displayed in Figure 9. The horizontal axis of the figures is the time horizon, while the vertical axis represents the cells of the station. Each colored rectangle indicates a train movement occupying the associated cell in a certain period. Remarkably, the blue, yellow, and green rectangles represent arrival, dwelling, and departure movement, respectively. The train names of the movements are displayed on the corresponding dwelling rectangles.

For Scheme-1, the cell 1DG, 3DG, 7DG, 13DG, 15DG, and 17DG serve both arrival and departure movement, while other cells in the throat areas only serve a single type of movement. Without the flyover, the turn-around trains granted “BDtr” can use siding tracks 9G, 7G, 5G, and 3G for stopping. However, the departure routes of these tracks toward the BD direction occupy 7DG, which might conflict with the arrival movement from the BD direction. For Scheme-2, with the flyover, the turn-around train granted “BDtr” can use siding tracks 9G and 7G. Therefore, the departure movements of these trains only occupy 1DG and are free from conflict with the arrival trains. This spatial conflict resolution measure reduces the signal’s waiting time, increasing the station capacity.

(2)

Occupation rates of track circuits

In order to display the difference of the occupation rate, we generate heat graphs displaying the occupation rate using the colors spectrum on the station layout, shown in Figure 10.

The bar charts comparing the occupation rate of different areas are displayed in Figure 11, Figure 12 and Figure 13.

From Figure 11, we can figure out that the occupation rate of the siding track area is higher than any throat area, reaching about 30%. Concerning the throat areas, the left throat has a higher occupation rate than the right throat. This characteristic of the occupation rate is identical to the small-scale instances displayed in Figure 8. Among the two station layout schemes, Scheme-2 has a lower occupation rate on the left throat, as the flyover resolves the conflicts between the arrival and departure trains. The turn-around trains granted “BDtr” stopping at siding tracks 7G and 9G only occupy one cell (1DG) instead of occupying 1DG, 17DG, 7DG, and 9DG for their departures. Specifically, we compare the occupation rate of each cell, and the results are displayed in Figure 12 and Figure 13.

For the throat areas, the occupation rates of the cells located at the right throat are identical between Scheme-1 and Scheme-2, as the flyover does not affect the movements on the right throat. However, by building the flyover, the occupation rates of the cells on the left throat varied between Scheme-1 and Scheme-2. Specifically, the occupation rate of cells 7DG and 9DG decrease dramatically by building the flyover, as the turn-around trains granted “BDtr” can depart through 1DG, instead of using 7DG and 9DG. Furthermore, the occupation rate of cell 17DG decreases slightly. On the contrary, the occupation rate of 1DG increases slightly due to the increased number of turn-around and departure trains running through the flyover.

Only the occupation rate of 7DG and 9DG for the siding tracks increases as the train running through the flyover has to stop at these two siding tracks. Benefiting from the flyover, the possibility of conflicts between arrival and departure trains on the left throat decreases so as to reduce the extra waiting time of the trains on the siding tracks. Therefore, the occupation rates of other siding tracks generally decrease.

4.2.2. Comparison of Parameter Sensitivity

(1)

Proportion of turn-around trains

The capacity performance of building such a flyover depends on the train combination. Therefore, we generate several instances with different train combinations. The instances both have 198 trains in the train set. However, the train running direction and operations are different. Detailed information on the train combinations can be referred to in Appendix A. The capacity of the proportion of variant instances is reported in Figure 14.

Figure 14 shows that Scheme-2 consistently outperforms Scheme-1 regarding the station capacity for any proportion of turn-around trains. In particular, when the proportion of turn-around trains is less than 70%, the absolute capacity value difference between Scheme-1 and Scheme-2 remains at the same level (between 10 and 30 trains, except for the case with 10% turn-around trains). However, when the proportion of turn-around trains is greater than 70%, Scheme-2 significantly benefits the capacity aspect. With the higher proportion of turn-around trains, the flyover significantly contributes to the station capacity improvement. The proportion of turn-around trains has consequences for the probability conflict between arrival and departure movements. Therefore, the effectiveness of building a flyover is determined to a great extent by the combination of trains.

(2)

Minimum turn-around time and headway

The operation parameters, such as minimum turn-around time and minimum headways, might impact the station capacity. We conduct a parameter sensitivity analysis for the two parameters mentioned above to investigate if it is possible to increase the station capacity by shortening these parameters. The relationship between station capacity and the various values of the parameters are displayed in Figure 15.

Figure 15a shows a linear trend between the minimum headway and station capacity, implying that minimum headway has a very obvious and direct effect on the station capacity. In other words, enhancing the station capacity by shortening the minimum headway is very useful. On the contrary, the minimum turn-around time performs a complex influence on station capacity, as shown in Figure 15b. Generally, there is a weak correlation between the minimum turn-around time and station capacity with the same layout scheme, i.e., the longer the minimum turn-around time, the smaller the capacity. This phenomenon can be further used to guide the capacity enhancement measurement; that is, increasing the capacity by compressing the turn-around time is very limited in general. When the turn-around time is shorter than 600 s, the difference between Scheme-1 and Scheme-2 becomes more significant, as the arrival and departure conflicts happen more frequently when the dwell times on the siding tracks are shorter.

5. Conclusions

This paper addresses a railway station capacity estimation problem for estimating the operation performance of the various design schemes. In particular, we first build a topology model to describe the layout and signal equipment of the railway station. The train operations within railway stations are described as “movement” with regard to facility occupation rules. Based on the train layout and train movement description, a mixed-integer programming model for train timetable compression is proposed to calculate the occupation rate of specific timetables, thus estimating the railway capacity of the specific layout design schemes. The schedule-and-fix heuristic algorithm is applied to solve the MIP model effectively. This method can be used to estimate the capacity utilization for stations with various layouts (i.e., different numbers of siding tracks, different connections between the siding tracks and the open track segments, and different operation parameters such as minimum headways and turn-around time limit).

Concerning the methodology used, the practical instance of the railway station capacity estimation problem is a large-scale combinatorial problem, as the existing MIP solvers find it difficult to obtain optimal solutions even if the number of trains is very low. The schedule-and-fix heuristic can accelerate the solution procedure sharply. Concerning the necessity of building a flyover to resolve the conflict of arrival and departure movements, the flyover provides capacity benefit to some extent for such a type of passenger railway station. However, only approximately 2% to 4% of the capacity improvement can be gained when the proportion of turn-around trains is less than 70%. Therefore, considering traffic combinations, building a flyover is beneficial only when the proportion of turn-around trains is significantly greater.

The station capacity result is significantly impacted by the arrival and departure headway. However, the impact of the turn-around time on station capacity is rather complicated. The result can provide hints for improving the station capacity while the infrastructure modification is not considered.

The proposed method can be applied in the real-life railway station design task, especially for the comparison and selection of the station layout design scheme. The solution algorithm can be embedded in a professional station computer-aided design program to calculate the capacity-related indices (i.e., the maximum number of trains, the occupation rate, and the bottleneck recognition result). This information can assist the engineers to better compare and trade-off the performance of the station layouts.

The limitations of this research are as follows. Cell occupation and release times are calculated by the formulations based on ideal situations, where the length and the dynamics of trains are not considered. Furthermore, the schedule-and-fix approach is not flexible enough during iteration procedures, limiting the solutions’ quality. Future research can focus on these limitations.