Optimization study of station track utilization in high-speed railroad based on constraints of control in random origin and process

Abstract

Purpose

The purpose of this paper is to eliminate the fluctuations in train arrival and departure times caused by skewed distributions in interval operation times. These fluctuations arise from random origin and process factors during interval operations and can accumulate over multiple intervals. The aim is to enhance the robustness of high-speed rail station arrival and departure track utilization schemes.

Design/methodology/approach

To achieve this objective, the paper simulates actual train operations, incorporating the fluctuations in interval operation times into the utilization of arrival and departure tracks at the station. The Monte Carlo simulation method is adopted to solve this problem. This approach transforms a nonlinear model, which includes constraints from probability distribution functions and is difficult to solve directly, into a linear programming model that is easier to handle. The method then linearly weights two objectives to optimize the solution.

Findings

Through the application of Monte Carlo simulation, the study successfully converts the complex nonlinear model with probability distribution function constraints into a manageable linear programming model. By continuously adjusting the weighting coefficients of the linear objectives, the method is able to optimize the Pareto solution. Notably, this approach does not require extensive scene data to obtain a satisfactory Pareto solution set.

Originality/value

The paper contributes to the field by introducing a novel method for optimizing high-speed rail station arrival and departure track utilization in the presence of fluctuations in interval operation times. The use of Monte Carlo simulation to transform the problem into a tractable linear programming model represents a significant advancement. Furthermore, the method’s ability to produce satisfactory Pareto solutions without relying on extensive data sets adds to its practical value and applicability in real-world scenarios.

Citation

Zheng, Y. and Zhang, D. (2024), "Optimization study of station track utilization in high-speed railroad based on constraints of control in random origin and process", Railway Sciences, Vol. 3 No. 3, pp. 332-343. https://doi.org/10.1108/RS-04-2024-0010

1. Introduction

The operation plan for arrival and departure tracks is crucial for train operations at railway passenger stations. The plan specifies the track designation and occupation time of all arrival and departure trains in the arrival and departure yard at a station within a given period. There have already been studies in this field by researchers since the 1960s (Gulbrodsen, 1963). In the early stages, operation plans for arrival and departure tracks were studied based on fixed timetables (Billionnet, 2003; Xie & Li, 2004). However, subsequent research integrated the operation of arrival and departure tracks with arrival and departure routing (Shi, Chen, QIN, & Zhou, 2009), EMU circulation (Wang, Huang, Zheng, & Zheng, 2018) and train operation adjustment (Wang, Zha, & Wang, 2022). Furthermore, considerations were also given to the impact of random factors in actual operation (Jánošíková & Krempl, 2014; Odijk, 1999; Zeng, Zhang, & Lei, 2017), significantly expanding the applicability of the obtained results. However, in those studies, random factors were often materialized by assuming the scenario of the delay of one train and the consequent delay of the following trains. Such a simple interpretation of the random factors of the train’s deviation from the plan is different from the actual operation. While some studies (Briggs & Beck, 2007; Fischetti, Salvagnin, & Zanette, 2009; Gilg et al., 2018) have considered the randomness and robustness of arrival and departure times, they primarily focused on scenarios of train delays and neglected the scenario of early arrivals. Therefore, this paper studies deviations of arrival times from the plan in the form of early arrivals and delays in actual train operation. By simulating the nonpunctual arrival scenarios of each train at different stations, a more stable preparation method for the operation plan of arrival and departure tracks is proposed. Furthermore, a multi-objective optimization model is established and Pareto optimization solutions are derived.

2. Description and analysis of operation problem of arrival and departure tracks in high speed railway stations

2.1 Problem description

The operation of arrival and departure tracks in high-speed railway (HSR) stations refers to the proper allocation of tracks to dwelling trains according to the platform types at the given arrival and departure times of trains. Generally, if the dwell times of two trains overlap (including the corresponding time for receiving and departure operations), there is a time conflict between the two trains in the operation of the arrival and departure tracks and one track cannot be allocated to both of them. Therefore, according to the actual situation of HSR stations, the operation of their arrival and departure tracks should comply with the following requirements:

1. Train shunting operations are not conducted at the station. Namely, only one arrival and departure track is occupied when the train arrives at the station from one direction, stops (or passes) and then departs in the other direction;

2. One arrival and departure track allows only one train dwelling at the same time and

3. If one arrival and departure track serves two trains, there must be a certain time interval between the dwell times of the two trains.

To facilitate modeling, the interval mentioned in Condition (3) above can be split into two parts according to the sources. The first part is the minimum required time from when a train leaves the station to when the track is clear. The second part is the minimum required time from when the route of station entry is set for the following train to when the train fully stops at the station. The split time interval as described above is combined with the dwell time of the corresponding train and collectively referred to as “occupancy time,” as shown in Figure 1.

In this case, the three requirements above can be summarized as follows: One train corresponds to one “occupancy time” and two trains with overlapping “occupancy times” cannot occupy the same arrival and departure track at the same time.

2.2 Influence of train’s control in random origin and control in random process on the occupancy of arrival and departure tracks by trains

The train operation system is a “complex system involving synthetical action of both control in random origin and control in random process (Zhang & Hu, 1995)”. The control at random origin is mainly caused by the fact that trains must operate as per the scheduled times whenever possible and the crew will minimize early arrivals and delays. Control in a random process mainly exists in the operation adjustment stage after a train delay when the crew uses technical means such as expediting at stations, expediting in sections or unplanned stops for waiting for the train to pass. It is a random phenomenon that is affected by external factors.

Trains are subject to the synthetic action of control in random origin and control in random process during operation. In addition, it is easier for the crew to avoid early arrivals than delays. As a result, times of train operation in sections are in a skewed distribution (Xu et al., 2022; Zhang & Hu, 1996) instead of a completely random normal distribution. The combination of the effects of control in random origin and control in random process in multiple sections on the line leads to more complex situations of early arrivals and delays of trains at stations. However, early arrivals and delays of trains at stations inevitably affect the operation of arrival and departure tracks in stations. Therefore, this study simulates the actual operation and takes into account the fluctuation of train operation time in sections in the operation of arrival and departure tracks in stations, thus enhancing the applicability and practicability of the study results of the operation of arrival and departure tracks.

2.3 Calculation of conflicts in occupancy of arrival and departure tracks by trains

To examine the conflict in occupancy of arrival and departure tracks by trains G1 and G2, suppose s1 and d1 represent the start and end moments of train G1’s “occupancy time,” respectively, and s2 and d2 represent the start and end moments of train G2’s “occupancy time.” There are two cases of conflict in the occupancy of arrival and departure tracks by trains G1 and G2. One case is when the “occupancy times” of two trains partially overlap, as shown in Figure 2. The other case is when the “occupancy time” of one train is completely included by the “occupancy time” of the other train, as shown in Figure 3.

The necessary and sufficient condition for the time overlap shown in Figure 2 is s2<s1<d2<d1 or s1<s2<d1<d2.

The necessary and sufficient condition for the time overlap shown in Figure 3 is s2<s1<d1<d2 or s1<s2<d2<d1.

Figure 4 illustrates the case where the “occupancy times” of trains G1 and G2 do not overlap, with the necessary and sufficient condition of s1<d1<s2<d2 or s2<d2<s1<d1.

Since s1<d1 and s2<d2 hold good under all circumstances, based on the cases in Figures 2–4, the necessary and sufficient condition for overlap of “occupancy times” of trains G1 and G2 can be generalized as max{s1,s2}<min{d1,d2}, while the necessary and sufficient condition for non-overlap of “occupancy times” of trains G1 and G2 can be generalized as max{s1,s2}≥min{d1,d2}.

3. Modeling for operation of arrival and departure tracks in HSR stations

3.1 Description of variables and symbols

M represents the set of connecting directions of the target station and m represents the direction and m∈M; K represents the set of trains received by the target station in a period of time, Km represents the set of trains in connecting direction m, Km⊆K and i,j,k represents the train and i,j,k∈K; Z represents the set of stations involved in all connecting directions of the target station and Zm represents the set of stations in connecting direction m, Zm⊆Z, z represents the station, z∈Z, especially, the target station is denoted as z0; G represents the set of arrival and departure tracks in station z0 and g represents tracks and g∈G.

Parameters qk,zm and pk,zm are defined as the arrival and departure times of train k (k∈Km) at station z (z∈Zm) in the basic timetable, respectively. Variables q∼k,zm and p∼k,zm represent the arrival and departure times of train k (k∈Km) at station z (z∈Zm) in actual operation, respectively. Parameter ηk,z,z′m represents the operation time of train k (k∈Km) in the section from station z to station z′ (z,z′∈Zm) in the primary train diagram. Variable η∼k,z,z′m represents the operation time of train k (k∈Km) in the section from station z to station z′ (z,z′∈Zm, z is the adjacent station of z′) in actual operation. This variable is subject to the constraints of control in random processes and control in random origins mentioned above. In general, it can be described by the skewed distribution β(a,b)^[10–12], and parameters in these distributions can be obtained from the historical data of operation time in each section. Parameters I1 and I2 are defined as the two split parts of the minimum interval required for two trains to dwell on the same track.

Parameter tk,zm is defined as the dwell or turnaround time of train k (k∈Km) at station z (z∈Zm) in the basic train diagram; variable t∼k,zm represents the stop (turnaround) time of train k (k∈Km) at station z (z∈Zm) in actual operation;

Parameter Tk,zm is defined as the minimum dwell (turnaround) time of train k (k∈Km) at station z (z∈Zm);

Parameter H is defined as the minimum headway between adjacent trains;

Parameters sk,zm and dk,zm represent the start and end moments of the “occupancy time” of train k (k∈Km) at station z in the basic timetable, respectively. Variables s∼k,zm and d∼k,zm represent the start and end moments of the “occupancy time” of train k (k∈Km) at station z in actual operation;

The 0–1 parameter fi,mj,n represents whether the “occupancy times” of train i (i∈Km) and train j (j∈Kn) overlap in the basic timetable, with 1 indicating the presence of overlap and 0 indicating the absence of overlap. f∼i,mj,n represents whether the “occupancy times” of train i (i∈Km) and train j (j∈Kn) overlap in actual operation, with 1 indicating the presence of overlap and 0 indicating the absence of overlap; according to the analysis in Section 1.3, the values of fi,mj,n and f∼i,mj,n can be determined by the following formulas:

(1)fi,mj,n={0 max{si,z0m,sj,z0n}<min{di,z0m,dj,z0n}1 max{si,z0m,sj,z0n}≥min{di,z0m,dj,z0n}

(2)f∼i,mj,n={0 max{s∼i,z0m,s∼j,z0n}<min{d∼i,z0m,d∼j,z0n}1 max{s∼i,z0m,s∼j,z0n}≥min{d∼i,z0m,d∼j,z0n}

Parameter ck,mg represents the cost of occupying track g by train k (k∈Km) at station z0. The method used in this study does not require that it correspond to the connecting direction of the track and the station. Instead, the value of parameter ck,mg can be used for guidance. This value can be derived through comprehensive consideration of factors such as train class, number of boarding and alighting passengers, running distance between the platform corresponding to the track and the station limits of entry and departure and whether the train crosses the main line when entering or departing from the station;

The 0–1 variable xk,mg represents whether train k (k∈Km) occupies track g at station z0, with 1 indicating the presence of occupancy and 0 indicating the absence of occupancy;

The 0–1 variable yi,m,j,ng represents whether a conflict occurs if both train i (i∈Km) and train j (j∈Kn) occupy track g at station z0 during actual operation. If a conflict occurs, it is 1, and otherwise, it is 0.

3.2 Constraint conditions

Calculation formulas for time in sections:

(3)ηk,z,z′m=qk,z′m−pk,zm

(4)η∼k,z,z′m=q∼k,z′m−p∼k,zm

Calculation formulas for dwell time:

(5)tk,zm=pk,zm−qk,zm

(6)t∼k,zm=p∼k,zm−q∼k,zm

Time interval constraints:

(7)q∼i,zm−q∼j,zm≥H

(8)p∼i,z′m−p∼j,zm≥H

Calculation formulas for “occupancy time”:

(9)sk,zm=qk,zm−I2

(10)dk,zm=pk,zm+I1

(11)s∼k,zm=q∼k,zm−I2

(12)d∼k,zm=p∼k,zm+I1

Conflicting train sets cannot be placed on the same track:

(13)fi,mj,n⋅(xi,mg+xj,mg)≤fi,mj,n

One train set can only be placed on one track:

(14)∑gxk,mg=1

Logic constraints:

(15)yi,m,j,ng⋅f∼i,mj,n≤xi,mg⋅f∼i,mj,n

(16)yi,m,j,ng⋅f∼i,mj,n≤xj,ng⋅f∼i,mj,n

(17)yi,m,j,ng⋅f∼i,mj,n≥(xi,mg+xj,ng)⋅f∼i,mj,n

3.3 Objective function

Minimize the cost of the dwell scheme:

(18)min⁡z1=∑k∑m∑gck,mg⋅xk,mg

Minimize the adjustment of the dwell scheme by the station dispatcher in actual operation:

(19)min⁡z2=∑i∑m∑j∑n∑gPr{yi,m,j,ng=1}

4. Pareto optimization solution of model for operation of arrival and departure tracks in HSR station

4.1 Definition of “scenario” under Monte Carlo simulation

According to the analysis in Section 1.2, the operation time of HSR trains in sections is in a skewed distribution under control in random origin and control in random process conditions. Therefore, it is difficult to describe the arrival and departure times at the target station using analytical formulas after the accumulation of a skewed distribution of operation times in multiple sections. Accordingly, it is also difficult for the model in this study to obtain analytical results with conventional methods. As a result, this study employs Monte Carlo simulation to calculate train operation times in sections in actual operation. A single sampling of all trains is defined as a “scenario,” which is expressed by set W. w is one scenario, and w∈W.

Where, in scenario w, variables q∼k,zm, p∼k,zm, η∼k,z,z′m, s∼k,zm, d∼k,zm, f∼i,mj,n and t∼k,zm are denoted as q¯k,zm,w, p¯k,zm,w, η¯k,z,z′m,w, s¯k,zm,w, d¯k,zm,w, f¯i,mj,n,w and t∼k,zm,w, respectively.

The corresponding constraints are transformed as follows:

(20)η¯k,z,z′m,w=q¯k,z′m,w−p¯k,zm,w

(21)t¯k,zm,w=p¯k,zm,w−q¯k,zm,w

(22)q¯i,zm,w−q¯j,zm,w≥H

(23)p¯i,z′m,w−p¯j,zm,w≥H

(24)s¯k,zm,w=q¯k,zm,w−I2

(25)d¯k,zm,w=p¯k,zm,w+I1

(26)yi,m,j,ng,w⋅f¯i,mj,n,w≤xi,mg⋅f¯i,mj,n,w

(27)yi,m,j,ng,w⋅f¯i,mj,n,w≤xj,ng⋅f¯i,mj,n,w

(28)yi,m,j,ng,w⋅f¯i,mj,n≥(xi,mg+xj,ng)⋅f¯i,mj,n,w

Objective (19) can be transformed into:

(29)min⁡z3=∑i∑m∑j∑n∑g∑wyi,m,j,ng,w

The entire model is then transformed into a 0–1 linear multi-objective programming.

4.2 Calculation of sampling values of train arrival and departure times in different “scenarios”

Due to the constraints of control in random process and control in random origin on η∼k,z,z′m,w, when random parameter η¯k,z,z′m,w is generated in different “scenarios”w, it should be ensured that the distribution of η¯k,z,z′m,w conforms to a specific β(a,b) distribution (the expected value is qk,z′m−p¯k,zm, which represents that the crew expects trains to punctually arrive at the station in actual operation). β(a,b) is mapped to the interval [A,B]. The values of A and B can be calculated using the following formulas:

(30)A=max{β(a,b)+H,min{η∼k,z,z′m,w}}

(31)B=ba(qk,z′m−p¯k,zm)

The expected value of η¯k,z,z′m,w calculated by the above method may be less than, and it is impossible to map β(a,b) to the interval [A,B]. Therefore, considering the actual operation situation, η¯k,z,z′m,w=A is set in the case of mapping failure.

4.3 Pareto solution

Pareto solutions are also called non-inferior or efficient solutions. In general, for multi-objective optimization, different objective functions are usually contradictory to each other. That is to say, in the feasible region, if at least one objective function will deteriorate while improving any objective function, then this solution is non-dominated and the solution set composed of non-dominated solutions is a Pareto solution. This study has two objectives: z1 is the total cost of the dwell scheme; z3 is the number of times for which the station dispatcher needs to adjust the operation scheme of arrival and departure tracks, which can be deemed as the work cost that the station dispatcher needs to pay. Therefore, in theory, the dimensions of z1 and z3 can be normalized by randomly generating parameter θ within the interval (0,1) and weighting the two objectives as follows:

(32)min⁡z=θ⋅∑i∑m∑gci,mg⋅xi,mg+(1−θ)⋅∑i∑m∑j∑n∑g∑wy¯i,m,j,ng,w

In this case, the model is reduced to a simple 0–1 linear programming that can be quickly solved using commercial optimization software CPLEX. By continuously adjusting the value of parameter θ, on one hand, different considerations of decision-makers for z1 and z3 are reflected and on the other hand, a series of Pareto solutions of the model established in this study can be obtained.

5. Example

To validate the universality of the method proposed in this study, the HSR station E with multiple connecting directions (including one to the EMU depot) in the railway network shown in Figure 5 is selected as the target station. A total of nine arrival and departure tracks are set for its HSR yard, with the left throat connecting two directions (A-B-E direction and C-D-E direction) and the right throat connecting one direction (F-E direction), where A, B, C, D and E are all HSR passenger stations and F is the EMU depot.

The layout of target station E is shown in Figure 6.

A total of 29 train sets were received and departed from target station E from 5:00 to 11:00. The timetable for target station E is given in Table 1 below:

Values of parameter θ are randomly generated 1,000 times based on the number of scenarios |W|=200, and the dominant relationship between the obtained solutions is assessed. Finally, three Pareto solutions (z1=364,z3=58), (z1=355,z3=124) and (z1=340,z3=242) are obtained. The operation schemes of arrival and departure tracks corresponding to these three solutions are illustrated in Figures 7–9, respectively:

In the above three schemes, two indicators, i.e. the generalized cost and the number of conflicts, cannot be optimal at the same time. Scheme 3 has the lowest generalized cost. However, 242 stop conflicts occur in 200 “scenarios,” which means that the dispatcher needs to adjust scheme 242 times. Although the generalized cost of scheme one is the highest, only 58 stop conflicts occur, which means that the dispatcher only needs to adjust the scheme 58 times. The generalized cost and number of conflicts in Scheme 2 are at the average level. Decision-makers may choose from the above three schemes according to the actual situation. Since the value of θ has a significant impact on the solution, an analysis is conducted on its impact: when θ∈(0,0.8799], the solution is (z1=364,z3=58); when θ∈[0.8800,0.8872], the solution is (z1=355,z3=124); when θ,∈[0.8873,1), the solution is (z1=340,z3=242). This indicates that when the value of θ is randomly generated, the probability of obtaining the solution (z1=364,z3=58) is about 87.99%, that of obtaining the solution (z1=340,z3=242) is about 11.27%, and that of obtaining the solution (z1=355,z3=124) is only about 0.73%. This reveals the fact that randomly generating parameters the θ within interval (0,1) cannot guarantee complete Pareto solutions obtained. In addition, the weighted summation of multiple objectives can only approximate the convex Pareto front. If the Pareto front is non-convex, even if the number of generators generating the value of parameter θ is increased, complete Pareto solutions cannot be guaranteed. The completeness of Pareto solutions remains a problem in mathematics. However, it is necessary to further study how to more efficiently obtain Pareto solutions as complete as possible for the operation of arrival and departure tracks.

6. Summary

This study examines the influence of fluctuations in train operation time in sections under constraints of control in random origin and control in random process on the operation of arrival and departure tracks. Based on this analysis, an optimization model is formulated. To account for the probability distribution aspect within the model, Monte Carlo simulation is utilized to transform the model into a 0–1 linear multi-objective programming. The Pareto optimization solution is then employed by assigning weights to multiple objectives. This method is applied to the example, and the results demonstrate that it is challenging to achieve the optimal values for both the generalized cost of train set dwelling on track and the number of conflicts in the operation of arrival and departure tracks caused by fluctuations in train operation time in sections. After obtaining multiple Pareto solutions with the method presented in this study, decision-makers can evaluate and consider optimization objectives based on specific values to make more precise decisions. The results of this study can help enhance the robustness of the operation scheme of arrival and departure tracks in HSR stations and optimize the utilization of railway transport capacity in actual operation, providing guidance and application value for meticulous management of railway operations.

Figures

Figure 1

Schematic of “occupancy time”

Figure 2

Overlap of “occupancy time” of two trains (category I)

Figure 3

Overlap of “occupancy time” of two trains (category II)

Figure 4

Non-overlap of “occupancy time” of two trains (category III)

Figure 5

Schema of the railway network where the target HSR station is located

Figure 6

Schema of layout of arrival and departure tracks at the target HSR station E

Figure 7

Operation scheme of arrival and departure tracks corresponding to the first set of Pareto solutions

Figure 8

Operation scheme of arrival and departure tracks corresponding to the second set of Pareto solutions

Figure 9

Operation scheme of arrival and departure tracks corresponding to the third set of Pareto solutions

Table 1

Train timetable for station E

Train-set	Inbound direction	Entry time	Departure time	Outbound direction
1	A-B-E	5:03	6:22	E-B-A
2	A-B-E	5:10	5:50	E-B-A
3	A-B-E	5:12	6:05	E-B-A
4	A-B-E	5:35	7:00	E-F
5	A-B-E	5:44	6:15	E-B-A
6	F-E	5:55	7:15	E-B-A
7	C-D-E	6:16	6:45	E-B-A
8	F-E	6:30	6:50	E-B-A
9	A-B-E	6:35	7:50	E-F
10	A-B-E	6:47	8:00	E-D-C
11	A-B-E	7:00	8:41	E-B-A
12	A-B-E	7:23	8:15	E-D-C
13	A-B-E	7:50	9:10	E-B-A
14	C-D-E	7:42	10:55	E-F
15	A-B-E	8:12	9:06	E-F
16	A-B-E	8:36	9:44	E-B-A
17	A-B-E	9:15	9:52	E-B-A
18	A-B-E	9:23	10:25	E-B-A
19	A-B-E	9:45	10:08	E-B-A
20	C-D-E	5:25	5:40	E-F
21	A-B-E	6:38	7:30	E-B-A
22	A-B-E	6:55	7:45	E-F
23	C-D-E	9:55	10:29	E-B-A
24	C-D-E	6:08	6:20	E-B-A
25	A-B-E	8:23	8:49	E-B-A
26	A-B-E	8:57	9:26	E-B-A
27	A-B-E	8:04	8:30	E-B-A
28	A-B-E	8:46	9:15	E-B-A
29	A-B-E	9:34	10:00	E-B-A

Source(s): Authors’ own ship