Track allocation optimization in high-speed railway stations from infrastructure management and service perspectives

Abstract

Background:

The high-speed railway has been developed rapidly, making track allocation optimization in high-speed railway stations one of the most important problems for traffic control.

Methods:

This paper proposes a 0-1 nonlinear integer programming model from both infrastructure management and service perspectives to solve this problem at the tactical level. The goal is to balance the track occupation time and at the same time to minimize the total walking distance between the entrance hall and the platforms for all passengers. A pre-calculation technique of time points considering the preparation of the route and a line group method are firstly studied. In order to solve the programming, the simulated annealing algorithm is applied.

Results:

A case of a China high-speed railway station is used to verify the effectiveness of this model. The optimized result is much better than the original plan in some key indicators. A comparison between the proposed algorithm and an accurate method, the branch-and-bound, is demonstrated. The simulated annealing algorithm obtains almost the same result as the accurate method in a much shorter time.

Conclusions:

The proposed model is practicable for the the high-speed railway stations.

Keywords

High-speed railway track allocation train control 0-1 integer programming pre-calculation technique line group method

Introduction

The high-speed railway transportation system is a huge and complex network system, which consists of two parts: stations and lines. In the last several years, the China Railway Corporation has developed the high-speed railway rapidly, making China one of the most advanced countries in the high-speed railway technology.

With the construction of the high-speed railway and the promotion of trains’ speed, the capacity of the open tracks between stations increases dramatically. As a result, the station capacity has been the bottleneck of improving the capacity of the high-speed railway network. Thus, it is necessary for the company to coordinate and match the capacity of stations and open tracks. For a railway company, it is not a wise choice to expand the station capacity by rebuilding or enlarging the yard blindly. Optimizing station operations is the best way to solve this problem. Clearly, the track allocation is an important part of station operations.

That how to schedule trains through a station automatically and optimally has attracted lots of researchers. There are four main methods used to solve this problem in current studies.

The first is known as graph-coloring approach. De Cardillo et al.¹ recommended a k L-List τ graph-coloring formulation solved by a backtracking heuristic algorithm. The same color could not be assigned to vertices indicating different trains with conflicting routes, which guaranteed the feasibility of the solution. They did these researches based on the assumption of the fixed time of trains and the determined routes of one arrival–departure track.

Another methodology is the node packing formulation. Zwaneveld and colleagues^2,3 proposed the node packing approach to settle this problem. Unlike graph-coloring approach which assigned different colors to trains with conflicting routes, this method was to select the trains with conflict-free routes. Routes of trains were divided into the inbound path Rⁱ, the platform path R^p and the outbound path R^o. For each train t ∈ T, its route R in a station was expressed as $R^{i} \cup R^{p} \cup R^{o}$ . Authors defined a conflict-free route set $F_{t t^{'}}$ where the routes of train t and train $t^{'}$ were conflict-free. By some pre-processing, the branch-and-bound (B&B) method was used. Compared with the conflict-free route set, however, it is possible to find a conflicting route set.

The most common method is called the integer programming approach. Carey⁴ used the mixed-integer programming model to describe what this problem was, but no solution was proposed for this model. Billionnet⁵ used two linear integer programs to depict the formulation of De Cardillo et al.¹ Some Chinese researchers, like Qiao,⁶ Liu et al.,⁷ Zhao et al.⁸ and Wu et al.,⁹ all used multi-objective functions to settle the problem. Wu et al.¹⁰ proposed a mean-variance model based on Markowitz’s portfolio theory. Qi et al.¹¹ and Meng and Zhou¹² proposed the mixed-integer programming models to solve the train control problem. But most of them constructed the models based on the conventional railway and paid more attention to the operational requirement rather than the service demand.

The last technique used to solve this problem is the simulation method. Carey and Carville¹³ stated the advantage of the manual method in this problem and put forward a scheduling algorithm which emulated how the train planer assigned a train to one track in practice. The solution solved by this method made itself more explainable and acceptable to train planers. However, with the expansion of the problem size, its computing time would increase dramatically.

Existing studies have the following issues that need to be improved. First, the capacity of a station is always limited by the use of resources in the station throat area other than the occupation of platforms. A few studies coordinate the use of arrival–departure tracks and station throats. However, a track allocation plan is feasible only and only if the planner considers the routes at the throat section and the receiving–departure tracks simultaneously. Second, most researchers ignore the fact that trains must claim station resources before their actual occupation. Thus, for some stations, especially multi-directional stations where more than two main lines connect multiple directions, the time points of trains’ routes cannot be calculated only by the arrival or departure time regulated by the train working diagram. Third, most studies construct the model just from basic infrastructure management perspective and ignore the service demand from passengers.

In the past studies, the track allocation problem can be classified into strategic, tactical and operational levels according to different focuses. The emphasis at the strategic level is estimating current infrastructures’ capacity to evaluate the feasibility of a possible train working diagram. At the tactical level, the studies focus on the allocation of different resources in stations with a fixed timetable. Lots of uncertainties leading to the occasional delay of trains in real-time railway operation are considered at the operational level. This paper solves the problem at the tactical level.

The contributions of this paper are summarized as follows. First, this paper focuses on the multi-directional intermediate stations and considers the routes at the throat section. Second, a pre-calculation technique is proposed to define different time points including the preparation time of the routes and to calculate the tracks’ occupation time and the routes’ duration properly. Third, a multi-objective model for the track allocation in high-speed railway stations is constructed from both infrastructure management and service perspectives. At the same time, the constraints describe station operations more realistic than most current researches to ensure the feasibility of the track allocation solution in China high-speed railway stations. After that, thanks to the soft constraint concept, this paper considers the service quality and can always return a feasible solution. Moreover, this paper first cites the line group method in passenger stations to facilitate the construction of the conflict route set and to make it easier to express the complicated conflict route constraint. Finally, this paper gives some indicators to evaluate the track allocation plan.

This paper is structured as follows. Section ‘Introduction’ introduces the background and provides a detailed review of the studies about this problem. Section ‘Problem description’ describes the problem solved by this paper. Section ‘Problem formulation’ constructs an integer nonlinear programming model. Then, this study presents a detailed algorithm. Section ‘Case study’ applies the model in a China high-speed railway station and analyzes the results. Finally, a conclusion is made and some future research directions in this field of the study are pointed.

Problem description

The railway company provides the train service with the scheduled plans. The planning process adopted by the high-speed railway is shown in Figure 1. As illustrated, the planning result above is an input to the subsequent step. Meanwhile, if the subtask cannot get a feasible solution, the former step or even more steps should be rescheduled during the planning process. This paper considers the problem of track planning in the station and assumes the former steps are completed. Thus, the fixed timetable where the arrival and departure time of trains cannot be changed and the EMU planning are given beforehand.

Figure 1.

Planning process of the high-speed railway.

The track allocation problem, which is also known as train platforming problem, is to schedule whole trains of the train working diagram reasonably to the arrival and departure tracks along with conflict-free routes in a station. Nowadays, most of these tasks are done by hand. For the China Railway Corporation, in order to meet changes of the demand in the high-speed railway transportation market, frequent adjustments of the train working diagram make the track allocation optimization more and more significant for high-speed railway stations.

Compared with freight stations and conventional railway passenger stations with lower speed trains, high-speed railway stations are different in both the technical and the service demand. Station operations are more frequent because of the raising train frequency. It is hard for planners to judge whether some routes are in conflict or not. In addition, the passengers expect better services since they should pay more for the high-speed railway than the conventional railway. Thus, how to allocate trains to the tracks in good quality is the heart of this problem. It needs to be solved not only from the infrastructure management perspective but also the service.

Station version

High-speed railway stations in China can be classified as intermediate and terminal. This paper focuses on the former version. If a high-speed railway intermediate station connects more than two directions, there are two main layouts for the station yard, as shown in Figure 2.

Figure 2.

Track layout of intermediate stations in China.

When different main tracks join together in a station, two kinds of station layouts will be used. As illustrated in Figure 2, Station A and Station B are divided into two yards, A1 and A2, B1 and B2, respectively. The main tracks of one line are separated into the different yards A1 and A2 in Station A according to the train’s arrival directions, while Station B is in contrast to Station A. All trains will always fit in all tracks in China high-speed railway stations. The length of a train is assumed to be a constant. This paper focuses on the left one which is common in China. Generally, the up and down trains are almost equal in amount in 1 day and the station yard is always symmetrical; thus, the planners stipulate that the two symmetrical parts of the yard are used for up trains and down trains, respectively.

If a station connects more than one direction, the number of the main tracks at one side of the station is set to be m, the other is set to be n. Then the number of the main tracks in the station should be max {m, n}. This is a design rule for high-speed railway stations in China.

Train routes

All trains in the high-speed railway intermediate stations fall into two categories: nonstop trains and stop trains. For a stop train, the receiving route is from the home signal to the starting signal and the departure route is from the starting signal to the reverse home signal (the home signal for opposite trains). For nonstop trains, the through route is from the home signal to the reverse home signal.

Based on Qiao,⁶ considering the continuity of train operations and that the train will never reach the starting signal when it stops, this paper assumes the train stop point where the middle of the train stops as the terminal point of the receiving route and the starting point of the departure route. Figure 3 illustrates the train routes clearly.

Figure 3.

Routes for trains in a station.

Problem formulation

Time points definition

When a train passes through a station, whether it stops or not, the time points of the train passing by different equipment can be calculated. Sels et al.¹⁴ explained the resources occupation time in detail. However, they ignored the fact that the resources of each route had been claimed by trains before their actual occupation. Based on Sels et al.,¹⁴ this paper describes time points of a stop train and a nonstop train through a station in increasing time and space dimensions in Figure 4. The vertical axis shows the significant positions and the horizontal axis shows the important time points.

Figure 4.

Time–space occupation of trains in a station.

The slope of the line between two vertices denotes the average speed between two positions. The top line describes the head of a train getting in and out of the station, while the bottom line represents the tail of the train. The vertical distance of each pair of lines indicates the length of the train. The left and right half of this figure show a stop train and a nonstop train crossing through a station, respectively.

As illustrated in Figure 4, the arrival and departure time of one train are the input data and other time points are the output data at the pre-processing stage. Using these time points as input, the track allocation plan is calculated by the proposed model and algorithm.

Arrival trains’ time points

This paper defines time points of a stop train entering a station as follows.

$T_{i}^{a}$ represents the time when the ith arriving train stops on a reception-departure track. This time point is given by the train working diagram.

Because of the interlocking system, the receiving route or departure route should be locked for a train in advance, which this paper mentioned as the claim of routes, before arriving at or departing from a station. When time condition or space condition is satisfied, the railway traffic control system will prepare the receiving route for the coming train. In this paper, the time condition is taken into consideration.

$T_{i}^{p a}$ denotes the time when the receiving route is prepared for the ith arriving train before its arrival. It also represents the starting time of occupying the arrival-departure track. An intermediate station may connect more than one line on one side. For a multi-directional high-speed railway intermediate station, although a switch at the station throat area cannot be claimed at the same time, more than two trains can move into the station simultaneously because of the parallel routes (conflict-free routes). Here, $T_{i}^{p a}$ can be pre-calculated as in Figure 5.

In Figure 5, t_a min and t_a min denote the criterion of the minimum and maximum time that the receiving route should be pre-set for a train before its arrival (i.e. the time span of $T_{i}^{p a}$ is between $T_{i}^{p a} - t_{a \max}$ and $T_{i}^{p a} - t_{a \min}$ ). l indicates the number of the directions connected on the corresponding side of the station. $t_{b u f}$ is the buffer time between two routes of two adjacent trains for the interlocking system to release the route and to guarantee the security. x represents the number of trains ahead of the ith arriving train and is always smaller than i. If the output is ‘wrong’, it means the trains in the given timetable cannot be scheduled in this station properly and the former step (i.e. the timetable planning) should be rescheduled.

Figure 5.

Pre-calculation procedure of the preparation time of the receiving route.

To clearly state the pre-calculation of the preparation time of the receiving route, we here give an illustration in Figure 6. If different lines merge outside Station M, like point P, they will share the same main tracks in the station, that is, C1 and C2 are the same direction C for Station M. Each line in Figure 6 is double-track. The layout of this station is similar to the left one in Figure 2. As illustrated, trains 1, 2, 3 and 4 are scheduled successively to enter Station M. Clearly, the number of the directions l is 2 for both sides. The maximum and minimum time t_a min and t_a min are 9 and 2 min. The buffer time $t_{b u f}$ is 1 min. Obviously, the preparation time of the receiving route for train 1 can be 9 min before its actual occupation. The time interval between the arrival time of trains 1 and 2 is smaller than t_a max but larger than $t_{a \min} + t_{b u f} .$ Meanwhile, the difference between two trains’ id is smaller than l. Thus, $T_{2}^{p a}$ is pre-calculated as $T_{1}^{a} + t_{b u f}$ . Because no train enters this station 9 min earlier than the third train, the corresponding arrival route is claimed by this train at the time of $T_{3}^{a} - t_{a \max}$ . The arrival time of the fourth train is so close to the third train’s that it cannot satisfy the two judging conditions in Figure 5 when x is 1. When x is 2, the fourth train’s arrival time will be compared with the second train’s. It is obvious that the fourth train arrives at this station more than 20 min later than the second train. Thus, the preparation time of the receiving route of train 4 can be set as $T_{4}^{a} - t_{a \max} .$ Given that the arrival time of train 2 is just 2 min earlier than train 4, the indicator x should be 3. As a result, the headway of trains 2 and 4 which come from the same direction cannot meet the safety condition, which means the given timetable must be wrong.

Figure 6.

An illustration of the preparation time of the arrival route.

$T_{i}^{a e}$ is the time when the tail of the ith arriving train passes by the reverse starting signal. It represents the receiving route of the train in the station left throat area is completely cleared and the station can prepare the routes for the next train after the buffer time. In this paper, $T_{a}$ is regarded as the time when the receiving route is released because the time interval between $T_{a e}$ and $T_{a}$ is much smaller than $t_{b u f}$ or $t_{a \min}$ .

Departure trains’ time points

This paper defines time points of a stop train leaving a station in a similar way.

$T_{i}^{d}$ is the time when the ith departing train stops on an arrival-departure track but the train is going to depart right now. It is also given by the train working diagram.

$T_{i}^{l e}$ denotes the time point when the tail of the ith departing train passes by the reverse home signal. It is the time when the train leaves this station and represents the release of the departure route. The duration time between $T_{i}^{d}$ and $T_{i}^{l e}$ is defined as $T_{i}^{d l e d u r}$ .

$T_{i}^{p d}$ is the time when the departure route is prepared for the ith departing train before it starts. It can be expressed as in Figure 7.

Figure 7.

Pre-calculation procedure of preparation time of departure route.

In Figure 7, $t_{d m i n}$ denotes the minimum interval between $T_{i}^{p d}$ and the departure time under normal circumstances. $t_{d w o r}$ represents the worst minimum interval during busy period, such as peak hours. It is stipulated that the time $T_{i}^{p d}$ cannot be earlier than $T_{i}^{a}$ .

$T_{i}^{e}$ is the time point when the tail of the train passes by the departure signal. It is also the end of one train occupying an arrival–departure track. The time interval between $T_{i}^{d}$ and $T_{i}^{e}$ is defined as $T_{i}^{d e d u r}$ .

For clarity, the time points of four departure trains are shown in Figure 8. The minimum interval $t_{d m i n}$ and worst interval $t_{a m i n}$ are 3 and 0.5 min, respectively. We set the durations $T_{i}^{d l e d u r}$ and $T_{i}^{d e d u r}$ as 1.5 and 0.5 min. As illustrated, the dwelling time of the first train is more than 3 min. Thus, the preparation time of its departure route is $T_{1}^{d} - t_{d \min}$ . However, train 2 dwells at this station less than 3 min, and the departure route cannot be prepared for a train which has not arrived yet. Thus, the departure route is claimed by train 2 as soon as it arrives at this station. The third train’s dwelling time is more than 3 min. Moreover, $T_{2}^{l e} + t_{b u f}$ is larger than $T_{3}^{d} - t_{d \min}$ but smaller than $T_{3}^{d} - t_{d w o r}$ . Then, the preparation time of the third train’s route should be calculated as $T_{2}^{l e} + t_{b u f}$ . Train 4 has the same dwelling time with train 3. However, compared with train 3, that is, when the value of x is 1, train 4 cannot satisfy the two requirements. Because two lines merge in Station M, two trains can leave from this station to A and B simultaneously as long as we assign two parallel routes for them, which means we can compare the time $T_{4}^{d}$ with the time $T_{2}^{l e}$ . It is obvious that the value of $T_{4}^{d} - t_{d \min}$ is larger than $T_{2}^{l e} + t_{b u f}$ , so we can prepare the departure route for train 4 at the time of $T_{4}^{d} - t_{d \min}$ . Similarly, if the headway between trains 2 and 4 cannot guarantee the safety, the given timetable must be wrong.

Figure 8.

An illustration of the time points of the departure train.

Nonstop trains’ time point

The difference between a nonstop train and a stop train is the simultaneity of the time $T_{i}^{p a}$ and $T_{i}^{p d}$ as well as zero dwelling time because the nonstop train crosses through a station via though route. The time points of a nonstop train are calculated as follows.

Superscript no is used to stand for a nonstop train. The through route is separated into the receiving route and the departure route. $T_{i}^{p a n o}$ and $T_{i}^{p d n o}$ of a nonstop train can be pre-calculated by the same way as the stop train does, and then this paper sets $\max {T_{i}^{p a n o}, T_{i}^{p d n o}}$ as $T_{i}^{p a n o}$ .

The arrival time $T_{i}^{a n o}$ and the departure time $T_{i}^{d n o}$ of the nonstop trains are all given by the train diagram. The time points $T_{i}^{e n o}$ and $T_{i}^{l e n o}$ denote the same meaning as the stop trains.

Table 1 illustrates the time points of a nonstop train traversing a station. After calculating the nonstop train’s time points as a stop train, the time point $T_{2}^{p a n o}$ should be 8:11:00. As mentioned before, a nonstop train should claim the receiving and departure routes at the same time. The value of $\max {T_{2}^{p a n o}, T_{2}^{p d n o}}$ is $T_{2}^{p d n o}$ . Thus, the time point $T_{2}^{p a n o}$ is updated to 8:17:00 which is also the time point for the preparation of departure route.

Table 1.

An illustration of time points of a nonstop train.

ID	Direction	Type	$T_{i}^{p a / p a n o}$	$T_{i}^{a / a n o}$	$T_{i}^{p d / p d n o}$	$T_{i}^{d / d n o}$	$T_{i}^{e / e n o}$	$T_{i}^{l e / l e n o}$
1	A-C	Stop	8:01:00	8:10:00	8:11:30	8:14:30	8:15:00	8:16:00
2	A-C	Nonstop	8:17:00	8:20:00	8:17:00	8:20:00	8:20:30	8:21:30

Resource occupation time

Resources in the station yard consist of the bottlenecks (i.e. throat area) and the arrival–departure tracks. As shown in the ‘Train routes’ section, the resources can be classified as receiving routes and departure routes for stop trains and through routes for nonstop trains, respectively. When the time points above are pre-calculated, the occupation time of different resources can be computed as in Table 2.

Table 2.

Occupation time of different resources.

Type	Starting time	Ending time
Receiving route duration, T_adur	$T_{i}^{p a}$	$T_{i}^{a}$
Departure route duration, T_ddur	$T_{i}^{p d}$	$T_{i}^{l e}$
Arrival–departure track occupation time, T_occ	$T_{i}^{p a}$	$T_{i}^{e}$
Through route duration, T_tdur	$T_{i}^{p a n o}$	$T_{i}^{l e n o}$

Note that the durations $T_{a d u r}$ and $T_{d d u r}$ depend on the choice of the track for a train. We later forbid any potential conflict routes overlap each other. To allow this, this paper sets the length of receiving routes and departure routes as two constants by the worst situation, which means the longest routes in the station, to simplify the problem and ensure any trains can satisfy the safety requirements. Meanwhile, the routing sections of siding tracks often have a speed limit of 40 km/h, which means the stop trains have a similar speed in the station. Thus, these durations can be pre-calculated reasonably.

When this paper calculates the occupation time of the arrival–departure track, the duration $T_{i}^{d e d u r}$ is slightly dependent on the track where the train stops. But as Qiao⁶ said, it is reasonable and recommendable to consider it as a constant in one station.

Also, the resource durations of a nonstop train are much smaller than a stop train because of the speed differences between them in the station.

Conflicting route set definition

Route-conflict happens when more than two trains occupy the same resource of the receiving–departure tracks or the throat areas at the same time. For a station connecting one direction on each side, the time intervals between tracing trains (depart–depart headway) and between adjacent trains at the station (arrive–arrive headway) guarantee that there is no route-conflict. Also, for a high-speed railway multi-directional station, the route-conflict will not happen for trains from the same direction. However, conflicts exist for trains from different directions in the multi-directional station. To prevent the route-conflict from happening, the structure of a multi-directional station must allow the existence of parallel routes to resolve conflicts. This paper classifies the receiving–departure tracks which cannot be occupied by different trains at the same time through parallel routes, considering each side of the station, respectively, into a line group.

To illustrate this problem, the structure of a station is given in Figure 9. Considering the left side, track 1 is sorted into group I, while tracks 2 and 3 are classified into group II, according to the parallel routes R-1 and R-2; tracks 8 and 9 fall into group III, while track 10 is in group IV, according to the parallel routes R-3 and R-4. If only the right side is taken into account, tracks are sorted like the left side. Main lines (tracks IV, V, VI and VII) are divided into four different groups.

Figure 9.

Layout of a simple railway station.

Pre-calculating the time points and grouping lines as mentioned above facilitate the construction of the conflicting route set. The set $R = {i, j, k, s}$ represents the ith and kth arriving or departing trains are assigned to tracks j and s, respectively. The conflicting route set $R_{c t}$ is constructed when the time intervals $T_{a d u r}$ , $T_{d d u r}$ or $T_{t d u r}$ of two trains in the set R overlap and the tracks j and s are in the same line group.

Basic constants

Basic constants can be divided into two aspects: the train properties and the track properties. The train properties include time points as mentioned above, the number and the direction of the trains, the number of the passengers and so on. The primary track properties involve the quantity of the tracks, the layout of the yard, the operations that can be provided for trains and so on.

Train properties constants

I denotes the set of trains in a station. $i, k \in I$ , $I = {i | i = 1, 2, \dots, n}$ , where n is the total number of trains. The trains are sequenced by the arrival time;

$p_{i}$ = average number of passengers getting on the ith train in this station;

$d_{i}$ = average number of passengers getting off the ith train in this station;

$h_{i}^{o p} = {\begin{cases} 1, \begin{matrix} \begin{array}{l} if a certain operation o p should be \\ arranged to the i th train in this station; \end{array} \end{matrix} \\ 0, \begin{matrix} otherwise . \end{matrix} \end{cases}$

The index op stands for a certain operation, such as the water supplying and the sewage suction;

$h_{i}^{M} = {\begin{cases} 1, \begin{matrix} if the i th train is a nonstop train \end{matrix} \\ 0, \begin{matrix} othewise \end{matrix} \end{cases}$

$h_{i}^{o r i} = {\begin{cases} 1, \begin{matrix} if the i th train originates from this station \end{matrix} \\ 0, \begin{matrix} otherwise \end{matrix} \end{cases}$

$h_{i}^{t e r} = {\begin{cases} 1, \begin{matrix} if the i th train terminates at this station \end{matrix} \\ 0, \begin{matrix} otherwise \end{matrix} \end{cases}$

$t_{i}^{c r i} = {\begin{cases} T_{i}^{d}, if h_{i}^{o r i} = 1 \\ T_{i}^{a}, if h_{i}^{t e r} = 1 \end{cases}$

This paper defines the time $T_{i}^{d}$ as the critical time point of starting trains which originate from the station and the time $T_{i}^{a}$ as the critical time point of finishing trains which terminate at the station.

Track properties constants

$J$ is the set of tracks including main lines and receiving–departure tracks in a station, $j, s \in J$ , $J = {j | j = 1, 2, \dots, m, m + 1, m + 2, \dots, m + q}$ , where m is the total number of sidings and q is the number of main lines.

$t_{j}$ is the average walking time for passengers from the entrance hall to the platform next to the track j;

$g_{j}^{o p} = {\begin{cases} 1, \begin{matrix} \begin{array}{l} if the j th track can provide a \\ certain operation o p \end{array} \end{matrix} \\ 0, \begin{matrix} otherwise \end{matrix} \end{cases}$ ;

$g_{j s}^{p} = {\begin{cases} 1, \begin{matrix} \begin{array}{l} if the j th track and the s th track share \\ the same platform \end{array} \end{matrix} \\ 0, \begin{matrix} otherwise \end{matrix} \end{cases}$ .

Decision variables

For this problem, the decision is whether the train i is assigned to track j. Thus, decision variables are expressed as follows

c_{i j} = {\begin{cases} 1, \begin{matrix} if the i th train is assigned to the j th track \end{matrix} \\ 0, \begin{matrix} otherwise \end{matrix} \end{cases}

Objectives

The track allocation problem, which is the sub-problem of train timetabling problem and significantly affects the efficiency of train control system, can involve various consideration. The balanced usage of tracks is adopted as the evaluation index in Qiao,⁶ Liu et al.,⁷ Zhao et al.⁸ and Wu et al.¹⁰ For a high-speed railway station, the usage of arrival-departure tracks is related to the utilization of capacity. The low usage of tracks causes the waste of capacity while the excessive usage leads to the difficulty of rescheduling trains under disruption. Unbalanced use also leads to the switch failure and the improper route display. Meanwhile, the balanced utilization of tracks can improve the anti-interference of train station operations.¹⁵ This paper also adopts the balanced usage as an objective function from the infrastructure management perspective. Thus, the objective 1, which minimizes the variance between the total occupation time of each track, can be expressed as follows

\min F_{1} = \sum_{j = 1}^{m} {(\sum_{i \in I} ((T_{i}^{e} - T_{i}^{p a}) c_{i j}) - \frac{1}{m} \sum_{i \in I} (T_{i}^{e} - T_{i}^{p a}))}^{2}

(1)

Improving the service quality makes the high-speed railway more competitive. The short travel time means not only the travel time on trains but also the walking time in stations, especially the time for passengers to get on a train from the entrance. To improve the satisfaction of passengers from the service perspective, objective 2 which minimizes the walking time from the entrance hall to the platform can be set as follows

\min F_{2} = \sum_{i \in I} \sum_{j \in J} p_{i} t_{j} c_{i j}

(2)

Constraints

Hard constraints

To fulfill the operational and security requirements, a train can only take one receiving–departure track in a station. This constraint is shown in Equation (3)

\sum_{j \in J} c_{i j} = 1, \forall i \in I

(3)

Second, a track cannot be occupied by two trains at the same time. Two occupations on one track cannot overlap each other. If the time interval T_occ of two trains is not separated by the buffer time, they cannot be arranged to the same track

c_{i j} + c_{k j} \leq 1, \forall i, k \in I, \forall j \in J; i < k, T_{k}^{p a} < T_{i}^{e} + t_{b u f}

(4)

In addition, two trains with conflicting routes cannot be arranged to the same line group

c_{i j} + c_{k s} \leq 1, \forall i, k \in I, \forall j, s \in J, \forall {i, j, k, s} \in R_{c t}

(5)

Constraints (3)–(5) are the basic constraints in the track allocation problem.^5,15,16 And constraint (5) is always reduced to common if–then conditions, which makes this constraint hard to be solved.¹² This paper makes this difficult constraint easier to construct by introducing the pre-calculating strategy and line group method. To the best of our knowledge, up to now few related researches have considered the operation constraint and the main line constraint in the literature. However, these constraints are taken into consideration in this paper, which makes the proposed model more practicable.

Meanwhile, a train which needs a certain operation op during the dwelling time should be assigned to the arrival–departure track providing this operation

\sum_{j \in J} c_{i j} g_{j}^{o p} \geq h_{i}^{o p}, \forall i \in I

(6)

Besides, for a station, especially a high-speed railway intermediate station, the main lines should be used for nonstop trains rather than stop trains. A nonstop train should go through the main lines and the main lines generally cannot be assigned to stop trains

\sum_{j = m + 1}^{m + q} c_{i j} = h_{i}^{M}, \forall i \in I

(7)

Finally, Equation (8) defines the domain of variables

c_{i j} \in {0, 1}, \forall i \in I, \forall j \in J

(8)

Soft constraint

Normally, starting trains or finishing trains will have so many boarding or alighting passengers that the platform will be crowded with a large number of people in a short time. If two trains like that occupy the same platform with much time overlapped, it will reduce the service quality drastically.

Therefore, if two trains, whether they are starting or finishing, have more than 200 people to get on or get off and their critical time points stagger less than T_cri, these trains cannot be allocated to the tracks that share one platform. In China, the tickets will be checked 15 min earlier before a train departs. The value of T_cri can be set as 7 or 8 min, which is enough for most passengers to get on trains from the platform or leave from the platform. This constraint will reduce the congestion in the ticket barrier and the platform. The constraints can be expressed as follows

{\begin{cases} c_{i j} c_{k s} g_{j s}^{p} = 0, \forall i, k \in I, \forall j, s \in J, | t_{i}^{c r i} - t_{k}^{c r i} | \\ \leq T_{c r i}, p_{i} \geq 200, d_{k} \geq 200, h_{i}^{o r i} = 1, h_{k}^{t e r} = 1 \\ c_{i j} c_{k s} g_{j s}^{p} = 0, \forall i, k \in I, \forall j, s \in J, | t_{i}^{c r i} - t_{k}^{c r i} | \\ \leq T_{c r i}, p_{i} \geq 200, p_{k} \geq 200, h_{i}^{o r i} = 1, h_{k}^{o r i} = 1 \\ c_{i j} c_{k s} g_{j s}^{p} = 0, \forall i, k \in I, \forall j, s \in J, | t_{i}^{c r i} - t_{k}^{c r i} | \\ \leq T_{c r i}, d_{i} \geq 200, d_{k} \geq 200, h_{i}^{t e r} = 1, h_{k}^{t e r} = 1 \end{cases}

(9)

This constraint related to service quality is set as the soft constraint. If no result returns, it can be relaxed directly. Generally, when the quantity of these trains in the station is larger than the number of the platforms at a certain time, this constraint will not be satisfied; thus, the soft constraint can be relaxed.

Solving algorithm

The train allocation problem has been proved to be an NP problem.¹ The formulation in section ‘Problem formulation’ cannot get an accurate solution in a reasonable time when the problem scale is large. To solve the NP problem, intelligent algorithms, such as simulated annealing (SA) algorithm, greedy algorithm, genetic algorithm, and Tabu search algorithm, are widely used. Among them, SA is a stochastic optimization procedure and has been found effective and efficient.¹⁰ This method increases the chance to escape from the local optimal and can guarantee the convergence. Thus, the SA algorithm is proposed to get an optimized scheduling plan in this paper.

Simplification

First, the linear weighted sum method is usually used to simplify the multi-objective model.¹⁷ This method gives its corresponding weight coefficient according to the importance of each objective and then optimizes the linear combination to solve the multi-objective programming problem. This method transforming the multi-objective problem into a single-objective function is set properly as follows

{\begin{cases} \min F = λ_{1} F_{1} + λ_{2} F_{2} \\ λ_{1} + λ_{2} = 1 \end{cases}

(10)

where $λ_{1}$ and $λ_{2}$ represent the weights of two goal functions. The trade-off between infrastructure management and service quality can be made by setting different weight combination. If a station has a preference for the service, one can set $λ_{1}$ less than $λ_{2}$ . But on the basis of current railway operation situation, it suggests that the value of $λ_{1}$ should be larger than $λ_{2}$ .

Procedures of the SA

Then, an SA algorithm is applied to solve the problem in this paper. The framework of the SA is illustrated as Figure 10.

Figure 10.

Flowchart of the SA algorithm.

The detailed procedure of the SA is described as follows:

Step 1. Set initial parameters: initial temperature $T_{0}$ T₀ = 10,000, cooling coefficient $α$ = 0.94, iterations at each temperature $τ$ = 300 and the lowest temperature $T_{\min}$ = 0.1. Input basic data including train diagram, passengers’ walking time, track layout, number of the boarding passengers for each train.

Step 2. Generate the initial solution: set the original allocation plan which is schedule by hand to be the initial solution S₀. Let current solution S = S₀ and current temperature T = T₀. Calculate the current objective function value $F (S) = F (S_{0})$ .

Step 3. Set the inner iteration counter $η = 1$ .

Step 4. Generate a new solution S*. If the new plan S* satisfies constraints, turn to step 5. Otherwise, repeat step 4.

Step 5. Let the feasible new solution to be S′. Calculate the new objective function value $F (S^{'})$ and $Δ F = F (S^{'}) - F (S)$ . If $Δ F \leq 0$ , let $S = S^{'}$ and $F (S) = F (S^{'})$ . Otherwise, generate a random number $ξ \in (0, 1)$ . If $\exp (- Δ F / T) > ξ$ , let $S = S^{'}$ and $F (S) = F (S^{'})$ . Then turn to step 6. Otherwise, turn to step 6 directly.

Step 6. Let $η = η + 1$ . If $η > τ$ , turn to step 7. Otherwise, return to step 4.

Step 7. Let $T = T \times α$ . If $T > T_{\min}$ , return to step 3. Otherwise, stop.

New solution generation

The generation of the new solution is shown as follows.

Obtain a number $ε$ between 0 and 1 randomly. If $ε \geq 0.5$ , generate a new train allocation plan by changing one trains’ track randomly. Otherwise, change two trains’ tracks at random. An example of the generation of a new solution is illustrated in Figure 11.

Figure 11.

New solution generation of the SA algorithm.

In Figure 11, a matrix is used to express the solution. Each element denotes whether train i is arranged to track j or not. This generation method guarantees that one train is only assigned to one track and reduces the cycle times from the current solution to a new feasible solution.

Case study

To verify the effectiveness of this proposed model, a China high-speed railway station is illustrated as a case. This station is an intermediate station, connecting A, B, C and D. The track allocation plan can be divided into up and down parts considering the directions of train’s arrivals and the layout of this station in Figure 12. The detailed data including the trains’ timetable (from 6:00:00 to 12:00:00) and the walking time of passengers can be seen in Appendix 1. The emphasis here is that track 1 is not used to receive trains because of the inconvenience of passenger organization. As illustrated in Figure 12, considering the left side, tracks 1, 2, 3 and 4 are sorted into group I, while tracks 5 and 6 are classified into group II, according to the parallel routes; tracks 11 and 12 fall into group III, while tracks 13, 14, 15, 16 and 17 are in group IV. If only the right side is taken into account, tracks 1, 2, 3, 4, 5 and 6 are sorted like the left side; But, tracks 11, 12, 13, 14 and 15 are assigned to group V, while tracks 16 and 17 are in group VI. Main lines are divided into different groups VII, VIII, IX and X.

Figure 12.

Layout of the station.

The proposed algorithm is coded in MATLAB. Here, $t_{a \max}$ , $t_{a \min}$ , $t_{b u f}$ , $t_{d \min}$ , $t_{d w o r}$ , $T_{i}^{d l e d u r}$ and $T_{i}^{d e d u r}$ are set as 540, 120, 60, 180, 30, 90 and 30 s for a stop train, respectively. $T_{i}^{d e d u r n o}$ and $T_{i}^{d l e n o}$ are set as 10 and 15 s for a nonstop train.

The influences of different weights are shown explicitly in Figure 13, where numbers under the horizontal axis represent different value combinations of two weights. In detail, the number 07.03 denotes that the value of $λ_{1}$ is 0.7 and the value of $λ_{2}$ is 0.3. Every combination shows the average result of 10 cases. The left and right vertical axes represent the values of objectives 1 and 2, respectively. Two values (objective 1-down/up-00.10) are reduced in order to fit the range of the vertical axis. The solid lines report the cases of down trains, while the dashed lines represent the cases of up trains. Take the down trains as an example. When $λ_{1} / λ_{2} = 1.0 / 0.0$ , the optimization effect of objective 1 is the best of all cases, while the optimization effect of objective 2 is the worst; clearly, if the values of the $λ_{1}$ and $λ_{2}$ are increased, the variance of the total occupation time of each track F₁ and the total walking time F₂ are decreased, respectively. Note that the less the variance and the total walking time are, the better the solution is. When $λ_{1} / λ_{2} = 0.0 / 1.0$ , the optimization effect of objective 1 is the worst, while the optimization effect of objective 2 is the best. Thus, the better the objective we want to get, the larger the corresponding weight should be. The trade-off between two weights depends on the planners’ strategy. If the planners focus on the improvement of infrastructure management, they will set the value of $λ_{1}$ larger than $λ_{2}$ . Otherwise, the value of $λ_{2}$ will be larger than $λ_{1}$ .

Figure 13.

The influences of different weights.

In the following case, the values of $λ_{1}$ and $λ_{2}$ are set as 0.7 and 0.3, respectively, after interviewing more than 10 experts in the railway traffic control center and the high-speed railway station.

Table 3 lists the optimized arrival–departure track utilization plan. In Table 3, each train is arranged to one corresponding track and only the nonstop trains are assigned to main tracks.

Table 3.

Optimized train occupation plan.

Track	Train’s number
2	G345, D6003, G105, G11, G111, G41, G115, G13
3	G297, G51, G101, G57, G107, G31, G321, G211, G117
4	G347, G285, G471, G177, G113, G293, G329
5	D257, D6075, G261, G265, G55, G263, G179, G27, G323
6	G61, G279, G433, G165, G119
VII
VIII	G1
IX
X	G180, G182
11	D402, G202, G266
12	G484, G204, G264, G32
13	G482, G262, G102, G12
14	G390, G106, G108
15	G208, G1268, G178, G34, G110
16	G1208, G1248, D6072
17	G1244, G104, G184

To illustrate the result clearly, Figure 14 shows the trains’ occupation time of different tracks. As shown in Table 2, the track occupation starts from the preparation of the receiving route and ends up at the time point when the tail of the train passes by the starting signal. The white block presents the occupancy of the track and the black means the track is free during this time period. As can be seen in Figure 14, there is no overlap between the white sections on each track, which satisfies the safety requirement. Meanwhile, all nonstop trains are arranged to appropriate main tracks and no stop trains occupy the main lines. The tracks in the down part are busier than the up part. If there is a small disturbance between down trains, the up part of the station yard can be used to recover its scheduled plan.

Figure 14.

Trains’ occupation time of different tracks.

Moreover, the balanced utilization of tracks means not only the time but also the frequency.¹⁰ To evaluate the optimized allocation result, an extra evaluation function which represents the variance of the frequency of each track can be defined as follows

E = \frac{1}{m} \sum_{j = 1}^{m} {(\frac{1}{m} \sum_{j = 1}^{m} \sum_{i \in I} c_{i j} - \sum_{i \in I} c_{i j})}^{2}

(11)

The results of this evaluation can be seen in Table 4. Each track’s occupation frequency of the optimized track allocation plan, no matter down trains’ or up trains’, is much more balanced than the original plan (OP). Thus, the optimized plan improves the anti-interference of train station operations.

Table 4.

The variance of the frequency.

Variance	Optimal schedule	Original schedule
Down	2.24	3.44
Up	0.56	2.24

To verify the effectiveness of the method, two objective values of the optimized and original track allocation plans are shown in Figure 15. Obviously, the optimized track utilization scheme is better than the original for both objectives. The optimization effect of the objective 1 is much better than the objective 2, which satisfies the setting of the weighs.

Figure 15.

Values of two objectives of the optimized and original plan.

To illustrate the efficiency of the solution, the convergence tests of up and down trains are shown in Figure 16. Clearly, the algorithm can converge to a steady state, within iterations ending.

Figure 16.

Convergence curve.

To verify the efficiency and the quality of the algorithm, this paper uses the solver LINGO with its default setting, B&B algorithm, to get solutions of different time periods. The comparisons of the OP, B&B method and SA algorithm are shown in Table 5.

Table 5.

Comparisons with different time periods.

Time period	Trains’ direction	Scale	Function value of F						Running time(s)
Time period	Trains’ direction	Scale	OP	B&B	SA	Gap¹ (%)	Gap² (%)	Gap³ (%)	B&B	SA	Gap⁴ (%)
6–8	Up	4	2689	2251	2251	16.30	16.30	0.00	58	6	89.7
6–8	Down	7	2477	2155	2155	13.00	13.00	0.00	47	11	76.6
6–10	Up	9	3502	2742	2742	21.70	21.70	0.00	2984	6	99.8
6–10	Down	21	7657	3905	3908	49.00	49.00	0.00	4059	12	99.7
6–12	Up	27	5736	4403	4417	23.20	23.00	0.20	>2d	9	≈100
6–12	Down	39	10,593	5981	6047	43.50	42.90	0.60	>2d	14	≈100
6–24	Up	116	37,379	12,306^a	12,456	67.10	66.70	0.40	>5d	34	≈100
6–24	Down	118	32,775	14,927^a	15,143	54.50	53.80	0.70	>5d	36	≈100

OP: original plan; B&B: branch-and-bound; SA: simulated annealing.

Solution is not global optimal but local optimal.

In Table 5, from the columns of function value, the values of Gap¹ and Gap² are larger than 0, that is, two methods all get an optimized solution. The results of the B&B method are all global optimal except two largest instances. The largest instance cannot get the best solution in a short time; meanwhile, it takes a long time to get a local optimal result. The SA method can obtain the same solution as the B&B when the size of the problem is not large. With the raise of the problem scale, the value of Gap³ increases slowly, which indicates the SA method also get an optimized result and the difference between the SA and the B&B is very small. From the columns of running time, the calculating time of the B&B method grows dramatically with the expansion of the scale while the running time of the SA algorithm keeps stable basically. With the increase of the problem scale, the solutions calculated by the SA method are similar to the results calculated by the B&B method, while the running time of the former is much shorter than the latter. Thus, it is concluded that the SA algorithm is effective and much more efficient than the B&B method. Because the number of trains in a station won’t be too few, the SA algorithm is much more suitable than the B&B method when solving the track allocation problem.

Conclusion

Current studies about the track allocation optimization in a high-speed railway station focus on the basic operations from infrastructure management perspective. However, passengers ask for a higher standard of service nowadays. In this paper, the problem is solved at the tactical level from both infrastructure management and service perspectives. A multi-objective nonlinear 0-1 integer programming model is constructed to balance the usage of arrival–departure tracks and minimize the walking time of passengers in a station. In addition, constraints are divided into hard and soft constraints, which guarantees that there will always be a solution to return. Also, some important time points of receiving and departure routes in the station throat area are explained specifically. After that, this paper shows what is the conflicting route and uses the line group method to facilitate the construction of the conflicting route set. An SA-based algorithm is proposed to find an optimal solution effectively and efficiently. A case study of a China high-speed railway station is given to verify the model. Meanwhile, an accurate algorithm, the B&B method, is compared with the proposed algorithm. The comparison with the original track plan is given to evaluate two algorithms. It is proven that the SA algorithm is much more suitable when solving the track allocation problem.

Some possible improvements can be done in the future work. First, a model that describes the terminal stations which include train turnaround operations should be proposed. Compared with the high-speed railway intermediate stations, the track allocation problem is more complex in terminal stations because of some extra operations. Then, an algorithm that solves this multi-objective problem directly will be adopted to be compared with the proposed method. After that, more attention should be paid to solving the track allocation problem at the operational level. Finally, this problem can be settled among several stations in a certain section at the same time because the delay of trains influences more than one station. Moreover, in practice, this system is suitable for stations only with the high-speed rail. Several stations with the high-speed rail, conventional rail and freight lines are not compatible.

Footnotes

Appendix 1

The train working diagram, original track allocation plan and the number of boarding passengers are shown in Table 6. The walking time from the entrance to the platforms is given in Table 7.

Declaration of conflicting interests

The author(s) declared no potential conflicts of interest with respect to the research, authorship and/or publication of this article.

Funding

This work was supported by the National Key Research and Development Program of China [grant number 2018YFB1201403].

References

De Cardillo

Mione

. K L-list λ colouring of graphs. Eur J Oper Res 1998; 106(1): 160–164.

Zwaneveld

Kroon

Romeijn

et al . Routing trains through railway stations: model formulation and algorithms. Transport Sci 1996; 30(3): 181–194.

Zwaneveld

Kroon

Van Hoesel

SPM

. Routing trains through a railway station based on a node packing model. Eur J Oper Res 2001; 128(1): 14–33.

Carey

. A model and strategy for train pathing with choice of lines, platforms, and routes. Transport Res B: Meth 1994; 28: 333–353.

Billionnet

. Using integer programming to solve the train-platforming problem. Transport Sci 2003; 37(2): 213–222.

Qiao

. Research on selection and adjustment of receiving routes and dispatching routes in passenger dedicated line station. PhD Thesis, Beijing Jiaotong University, Beijing, 2012 (in Chinese).

Liu

Niu

Zhang

et al . Model and algorithm of high-speed railway station to track allocation. Mod Transport Tech 2015; 12(2): 69–73 (in Chinese).

Zhao

Song

Chen

et al . Comprehensive optimization of arrival-departure track allocation and the bottleneck occupation in a large railway passenger station. J Beijing Jiaotong Univ 2015; 39(6): 1–7 (in Chinese).

Kou

. Optimization of arrival and departure tracks in passenger stations based on branch and bound method. J Transp Eng Inform 2016; 14(4): 100–104 (in Chinese).

10.

Kang

Sun

et al . Track allocation optimization in railway station: mean-variance model and case study. J Transp Eng 2013; 139(5): 540–547.

11.

Yang

Gao

et al . Integrated multi-track station layout design and train scheduling models on railway corridors. Transport Res C: Emer 2016; 69: 91–119.

12.

Meng

Zhou

. Simultaneous train rerouting and rescheduling on an N -track network: a model reformulation with network-based cumulative flow variables. Transport Res B: Meth 2014; 67(3): 208–234.

13.

Carey

Carville

. Scheduling and platforming trains at busy complex stations. Transport Res A: Pol 2003; 37: 195–224.

14.

Sels

Vansteenwegen

Dewilde

et al . The train platforming problem: the infrastructure management company perspective. Transport Res B: Meth 2014; 61: 55–72.

15.

Jia

. Route allocation problem and buffer times at large-scale passenger rail stations. PhD Thesis, Beijing Jiaotong University, Beijing, 2010 (in Chinese).

16.

Ghaemi

Cats

Goverde

RMP

. Macroscopic multiple-station short-turning model in case of complete railway blockages. Transport Res C: Emer 2018; 89: 113–132.

17.

Zong

Wang

. A multi-objective programming model of route choice before travel. J Transp Sys Eng Inform Technol 2005; 5(6): 58–61 (in Chinese).