# A Multiobjective Optimization for Train Routing at the High-Speed Railway Station Based on Tabu Search Algorithm

Authors: Ziyan Feng; Chengxuan Cao; Yutong Liu; Yaling Zhou
Journal: Mathematical Problems in Engineering
 (2018)

---

## Abstract

This paper focuses on the train routing problem at a high-speed railway station to improve the railway station capacity and operational efficiency. We first describe a node-based railway network by defining the turnout node and the arrival-departure line node for the mathematical formulation. Both considering potential collisions of trains and convenience for passengers’ transfer in the station, the train routing problem at a high-speed railway station is formulated as a multiobjective mixed integer nonlinear programming model, which aims to minimize trains’ departure time deviations and total occupation time of all tracks and keep the most balanced utilization of arrival-departure lines. Since massive decision variables for the large-scale real-life train routing problem exist, a fast heuristic algorithm is proposed based on the tabu search to solve it. Two sets of numerical experiments are implemented to demonstrate the rationality and effectiveness of proposed method: the small-scale case confirms the accuracy of the algorithm; the resulting heuristic proved able to obtain excellent solution quality within 254 seconds of computing time on a standard personal computer for the large-scale station involving up to 17 arrival-departure lines and 46 trains.


---

## Body

## 1. Introduction

Generally, the station is composed of bottleneck and arrival-departure lines which is vital for trains arriving, departing, running, shunting operations, and so on. The efficiency of railway transport faces challenges due to increasing passengers and freight transportation demands. In order to enhance the capacity of the railway station, operators can be dedicated to adding the number of track lines, which requires plenty of manpower, materials, and financial resources obviously. By contrast, making proper arrangements of trains’ routes at bottleneck and arrival-departure lines based on existing track lines can save lots of resources and achieve the same effect. Hence, attention is paid to arrange the trains’ routes reasonably in the station to improve the operational efficiency and reduce the operation costs [1, 2] (D’Ariano et al., 2008).In general, the railway planning process is divided into strategic level, tactic level, and operational level. In this paper, we focus on the tactic level, especially on the timetable optimization and railway track allocation/train routing in a complex high-speed railway station. At present, the optimization of the train routing problem (TRP) in the railway station is mainly based on the mathematical optimization model. Some studies aimed at the complicated bottleneck of the railway station, as D’Ariano et al. [3] considered that reducing trains’ collisions at the bottleneck can improve punctuality without decreasing the capacity usage of the lines and a detailed model for conflict resolution and different algorithms was illustrated. Based on the robustness of routing assignment, Jia et al. [4] proposed the optimization of routing utilization at bottleneck. Kang et al. [2] presented a bottleneck optimization model thereafter to enhance the capacity by reasonably arranging routes and turnouts. Other parts of the researches concentrated on the problems of arrival-departure lines occupancy. For example, Billionnet [5] considered assigning trains to the available tracks at a railway station instead of taking into account the collision at the bottleneck. Caprara et al. [1] proposed a 0-1 integer programming model to describe the routing problem of trains at the station platform; moreover, the quadratic objective function was linearized and solved by integer linear programming. Besides, an optimization model is presented by Qiao et al. [6] based on the train schedules to arrange suitable arrival-departure lines for passenger trains. Furthermore, the research of the TRP with joint optimization of bottleneck and arrival-departure lines is also found in the literature. For instance, Zwaneveld et al. [7] considered both bottleneck and arrival-departure lines and proposed a 0-1 programming model to arrange trains passing the railway station. But the problem only at small-scale railway stations can be solved by branch-cut method. Based on the graph theory, Corman et al. [8] rearranged train routing in real-time unpredictable events and found the best solution using truncated branch-and-bound and tabu search algorithms.In the past few decades, there have been limited researches on TRP in high-speed railway stations. Most studies were associated with the train timetable problems [9–11]. TRP is tantamount to selecting a sequence of tracks for a train from its origin to destination, with the objective of minimizing the sum of travel time, the total operating cost, and/or increasing the capacity of railway network. Xu et al. [11] defined the objective function to minimize deviations between trains’ arrival time at the destination and original timetable. The optimization model proposed by Li et al. [12] aimed to minimize the total delay of all trains in the railway network. Liu et al. [13] developed a mathematical model whose aim is minimizing the total occupation time of station bottleneck sections to avoid train delays. In addition, some research focused on the optimization by keeping the most balanced utilization arrival-departure lines like Qiao et al. [6]. One of the objective functions considered by Zhou et al. [14] and Zhou et al. [10] was to minimize the total travel time on the track. Apart from this, the most important constraint should be taken into account was the spatiotemporal interactions between each train operation route in the TRP (D’Ariano et al., 2008) [2, 4, 12]. Furthermore, it should be considered that trains which occupy the same arrival-departure lines should satisfy a headway time constraint [1, 6]. Zhou et al. [14] and Corman et al. [8] proposed that trains should stop for enough time to ensure the transfer time of passengers and crews. What is more, Fang et al. [15] analyzed a comprehensive survey on different models by a clear classification based on the different scale, infrastructures, objectives, and constraints.It is well known that the TRP is the NP-hard problem [16] and unlikely to get an exact optimal solution in a short computational time under the large-scale and complex situation. In order to get an approximate optimal solution rapidly, many studies proposed different heuristic algorithms based on different strategies. Corman and Meng [17] introduced the online dynamic models and algorithms for the rail traffic management in order to provide punctual and reliable services. Specifically, Ahuja et al. [18] considered the issue of railway scheduling and presented a heuristic algorithm to get the approximate optimal solution in short time. Carey et al. [19] studied the large-scale problem that involved lots of train schedules and routes and proposed heuristic algorithms to solve it. Liu et al. [13] designed a hybrid algorithm between genetic algorithm and the simulated annealing algorithm. In recent years, for the sake of further improving the computational speed and quality of solution, some studies have proposed improving heuristic algorithms. He et al. [20] proposed an improve branch-and-price algorithm to deal with the large scale integer programming. Zhou et al. [10] used an efficient train-based lagrangian relaxation decomposition to the simultaneous passenger train routing and timetabling problem. Additionally, some studies used commercial software like Qi et al. [21] who obtained for an approximate optimal solution within 30s by a local search heuristic algorithm using CPLEX solver and Xu et al. [11] who solved train routing and timetabling problem with switchable rules by CPLEX solver with OPL language.Besides that, some studies dealt with the integer programming problem using tabu search algorithm, as Isaai and Singh combined the heuristic with tabu search and simulated annealing search control strategies to deal with the train timetabling problem. Similar, Corman et al. [8] rearranged trains’ routes based on the graph theory and got the approximate optimal solution of the combination of truncated branch-and-bound and tabu search algorithms. Li et al. [12] proposed a tabu search algorithm, and they pointed out that the algorithm relies on a better initial solution; otherwise the result obtained is not stable. In addition to this, Goh et al. proposed a tabu search with sampling and perturbation to generate feasible solutions. The tabu search algorithms and variable neighborhood are applied by Samà et al. [22] to improve the solution for the real-time management problem of scheduling and routing trains in complex and busy railway networks.As can be found in numerous studies, there were few elaborate mathematical models to describe TRP and further study on TRP in the network of the high-speed railway station. In this research, with the motivation of greatly improving the solving efficiency of TRP in the network of the high-speed railway station, we intend to provide the following contributions:(i)
Describe a railway network by defining the turnout node and the arrival-departure line node on account of the traditional layout of the railway station, which is regarded as a directed graph. The nodes are regarded as vertices, and the actual connection of the lines is regarded as arcs. The railway station is divided into three parts and the connection sets are built to satisfy the connection relationship of them.(ii)
According to the given nominal timetable, the calculation methods of trains occupying each track are elaborated. Then formulate the TRP in the network of the high-speed railway station as a multiobjective mixed integer nonlinear programming model, in which both are considered the potential collisions of trains and the convenience for passengers’ transfer in the high-speed railway station. In the proposed model, it is not only minimizing train departure time deviations with the most balanced utilization of arrival-departure lines but also minimizing the total occupation times of all tracks.(iii)
The TRP is NP-hard problem. Therefore, it is very unlikely to devise a polynomial-time (exact) algorithm for it. In order to get an approximate optimal solution rapidly, a heuristic algorithm is proposed based on the tabu search to solve the large-scale TRP in the network of the high-speed railway station.(iv)
Numerical examples are implemented to demonstrate the effectiveness and efficiency of proposed method. By taking advantage of an efficient tabu search algorithm, we can solve the model rapidly for a small case. The results we obtained from the algorithm are the same as obtained directly from CPLEX solver. In the large-scale case involving 17 arrival-departure lines and 46 trains between 16:00~19:00, the resulting heuristic proved able to obtain excellent solution quality within 254 seconds of computing time on a standard personal computer.The remainder of this paper is organized as follows. Section2 presents a detailed description of TRP problem. Section 3 provides the mathematical formulation for the TRP in the network of the high-speed railway station. Section 4 deals with the development of a heuristic algorithm based on the tabu search. Section 5 describes the instances used and provides computational results. Finally, some conclusions and further research directions are presented in Section 6.


## 2. Train Routing Problem Description

### 2.1. Layout of Railway Station

We consider a railway station as illustrated in Figure1. This railway station consists of bottlenecks and some arrival-departure lines whose length is Ls. The left side of the station in Figure 1 is defined as left bottleneck whose length is Ll. The route set of it is L=l1,l2,⋯,lk1. Similarly, the right side is defined as right bottleneck whose length is Lr. The route set of it is R=r1,r2,⋯,rk2. The bottleneck involves tracks where trains arrive and depart. For instance, an outbound train arrives from node d1 and stops at arrival-departure line. In Figure 2(a), there are 4 possible routes for the outbound train that arrives from node d1, whose set is L1=l1,l2,l3,l4 in the left bottleneck. Similar, an inbound train departs from arrival-departure line to the node d2. There are also 4 possible routes for the inbound train departs from node d2 as shown in Figure 2(b) whose set is L2=l5,l6,l7,l8. So the route set of the left bottleneck is L=L1∪L2=l1,l2,…,l8. In particular, at large stations, the number of routes in the bottleneck may be larger than the number of arrival-departure lines due to the existence of multiple crossovers and turnouts. The route set of arrival-departure lines is S=s1,s2,…,sm, which containsI,II,3, and4 as shown in Figure 1.Figure 1
An illustration of a railway station.Figure 2
The route set of left bottleneck in the railway station.
(a) (b)Normally, track lines are divided by insulation joints. In this paper, the turnout node and the arrival-departure line node are defined as follows to describe the railway station.1.
Turnout node: the intersection of the lines in the station. It includes turnouts (as shown in Figure 1, d5 and d6, etc.), crossovers (as shown in Figure 1, d7, etc.), and the position of signal which located in the entrance of the bottleneck (i.e., the boundary point of the station).2.
Arrival-departure line node: the connection points of bottleneck and arrival-departure lines in the railway station, namely, the signal position of the entrance of the arrival-departure lines (i.e.. the nodes d8~d10 in Figure 1).During the operation, the outbound trains can only arrive from turnout noded1 and depart from turnout node d3 as shown in Figure 1. Similar, the inbound trains can only arrive from turnout node d4 and depart from turnout node d2. However, no matter in which direction trains are, any of arrival-departure lines can be occupied. Hence the physical network of the railway is regarded as a directed graph. The nodes are regarded as vertices, and the actual connection of the lines is regarded as arcs. Let D denote the set of all vertices and A denote the set of all arcs in the network.


### 2.2. Trains

We consider a set of trains in both directions. The set of trains is denoted byC=c1,c2,⋯,cn, in which C1=c1,c3,c5,⋯ is the set of outbound trains and C2=c2,c4,c6,⋯ is the set of inbound trains. The heterogeneous trains are taken into account. We assume that these trains are categorized into two types: slow trains and fast trains. In addition, there are shunting operation beside train reception and departure operations. The speeds of shunting trains are slower than the ordinary trains.In addition, some of the fast trains pass the station without stopping while some trains stop at platform for passengers to alight or transfer. Different trains’ stop time may be different, whether they are fast or slow trains. As we all know, the speed of trains is not a constant, while it changes with the driver’s braking when the train would stop at the platform. Similarly, the speed of trains does not increase suddenly when departing from the platform. Therefore, the additional time that provides trains’ acceleration and deceleration is considered. At the same time, the length of trains is also taken into account to meet the actual situation.


### 2.3. Conflicts and Potential Conflicts

The conflicts of tracks which trains occupy are the most imperative problem to be solved in TRP. In other words, trains cannot occupy the same track at the same time. A conflict occurs whenever trains traverse the same track and do not respect the minimum time interval at the bottleneck and arrival-departure lines. What is more, it would result in potential conflicts. These situations are discussed separately as follows.


#### 2.3.1. Train Routing Conflicts at Bottleneck

The bottleneck consists of channels with some turnouts, crossovers, and other facilities, which may cause spatial intersections of trains’ alternative sets of routes, especially when some unpredictable events or interruptions occurred. So it is an important task for train dispatchers to avoid the train collision and to assure the trains passing the tracks orderly. The conflicts between two trains in the bottleneck mainly occurred at the intersection of the track segments (the segmentd1~d2 as shown in Figure 3) and the intersection of crossovers (the point d3 as shown in Figure 3).Figure 3
The same/reverse direction conflicts of trains routing.
(a) (b)In Figures3(a) and 3(b), trains c1/c2 travel in the same/reverse direction, and the collision occurs at the track segment between nodes d1 and d2. Similarly, the collision occurs at the track segment at the node d3 when the trains c2 and c3 travel in the same and reverse direction, respectively. The methods to dissipate conflicts will be depicted in detail in Section 3.


#### 2.3.2. Train Routing Conflicts at Arrival-Departure Lines

When two consecutive trains plan to occupy the same arrival-departure line in the railway station, they should follow a headway time to suit the limited infrastructure capacity. That is, one train occupies this arrival-departure line a specific headway time later than the other one. As shown in Figure4, there are two trains c1 and c2. The origin and destination of train c1 are A and C, respectively, and the origin and destination of train c2 are B and C. Obviously, if the route p1 is assigned to c1 and c2 occupies route p2 in a short interval, this would cause a conflict at platform 1. In this case, the latter train should stop and wait until the previous train leaves from the platform 1 for a reasonable headway time. It may cause the latter train to be behind the schedule time and even to have second delay in severe cases. But if the train c2 occupies route p3, the conflicts would be avoided and the train operational efficiency would be ensured in the railway station.Figure 4
The conflict at arrival-departure lines.Therefore, if the two trains’ departure interval is smaller than the headway timeTm1, it is better to arrange them at different lines. Just as illustrated in Figure 4, if the difference of two trains’ departure time is bigger than the headway time Tm1, the same arrival-departure line can be arranged.


#### 2.3.3. Potential Conflicts of Train Routing

It is noteworthy that only considering trains’ routing at bottleneck and headway time at arrival-departure lines cannot completely meet the requirement of safe operation. There are further potential conflicts.For instance, the outbound trainc1 would stop at arrival-departure lineII from outbound main line while the inbound train c2 would depart from line3 to the inbound main line (as shown in Figure 5(a), the yellow dotted line and the blue dotted line represent the route of trains c1 and c2, respectively). There is no time provided to avoid the potential conflict area (the red circle area in Figure 5), since it is not in the context of the two conflicts described above. Therefore, a time separation should be adopted even though two trains do not occupy the same track; i.e., c1 first arrives and then c2 departs later or c2 first leaves and then c1 arrives later, the same as shown in Figure 5(b). It is necessary to set constraints so that two consecutive trains arrive the potential conflict area in a time separation.Figure 5
The illustrative of outbound and inbound trains’ potential conflicts.
(a) (b)In addition, when two trains are in the same direction, the conflicts between them are not potential conflicts. Just as shown in Figure6, c1 and c2 are outbound trains. It is apparent that there exists a conflict in the red circle area. However, due to the conflicts at the bottleneck between the two trains, the constraints are set to avoid the collision; namely, conflicts in the rad circle area are also dissolved. Therefore, the potential constraints we discussed are only among the reverse trains.Figure 6
The illustrative of the same direction trains occupied different lines.


### 2.4. The Calculation Methods of Track Occupation Time

In this paper, not only is the train routing chosen as the decision variables but also optimized the schedule of trains to start entering the station according to the planned schedule when trains depart from the station. Thus the time for trains passing the conflict tracks needs be calculated. In addition, the convenience factors of passengers transferring at station are taken into account, and the associated trains’ dwell-time intersection should be long enough. As a consequence, the trains’ travel time in different track sections should be clearly calculated.To our knowledge, as long as a track segment is occupied, the lines, the fouling posts, and the signals are also occupied at the same time. We elaborate the calculation of the occupied time and the end time of occupied of trains passing through the left bottleneck, the arrival-departure lines, and the right bottleneck in turn. The occupied trains at the bottleneck are divided into two situations: train reception and train departure, whose calculated method of train occupied time of tracks is same. So only take the outbound trains as an example to explain in detail.


#### 2.4.1. The Calculation of Trains Travel Time and the End Time of Occupied at the Bottleneck

For outbound trainsc∈C1 in the left bottleneck l∈L, they start to enter the station at tc+tcsetup and pass each node with speed vc. The track is unlocked after their tails pass the end node of the track section. So the trains’ occupied time of each track segment is calculated as follows:(1)ta=Lavc,where ta is occupancy time of a certain track segment a and La is length of the track segment a. Thus, the travel time of outbound trains c∈C1 from the left bottleneck signals to the arrival-departure lines is calculated with the following:(2)tcsl=Ll+Lcvc,where Ll is length of routes which is sum of each track segment in the left bottleneck and Lc is the length of the train c. In Figure 7, the length of Ld1~d10 is the sum of lengths of d1~d6 and d6~d10; the length of Ld1~d11 is the sum of lengths of d1~d6 and d6~d11. That is, the length of the different routes in the left bottleneck is different. The end of the left bottleneck occupied time of outbound trains is(3)tclend=tc+tcsetup+tcsl.Figure 7
The calculation of trains’ travel time in station.Take the railway station in Figure1 as an example to calculate the occupancy time of one route of outbound train in the left bottleneck. As shown in Figure 7, it is assumed that the train arrives from the node d1 and stops at lineI (i.e., the green dashed line in Figure 7). Then the travel time of train c from the left bottleneck signal to the line I is calculated as tcsIl1=(Ld1~d10+Lc)/vc. The end of the left bottleneck occupied time is tcl1end=tc+tcsetup+tcsIl1.The occupied time of outbound trains departing from the station through the right bottleneck is calculated as(4)tcsre=Lr+Lcvc,Similarly, the travel time of trains departing from the lineI and leaving to node d3 through the right bottleneck (i.e., the blue dashed line in Figure 7) is calculated as tcsIr1e=(Ld9~d3+Lc)/vc.For the inbound trainsc∈C2, the calculation of trains travel time and the end time of occupied at right bottleneck are as follows, respectively:(5)tcsr=Lr+Lcvc.(6)tcrend=tc+tcsetup+tcsr.The travel time in the left bottleneck when the train departs from the station is calculated by(7)tcsle=Ll+Lcvc.


#### 2.4.2. The Calculation of Trains Travel Time and the End of Occupied Time at Arrival-Departure Lines

The occupation of arrival-departure lines can be partitioned into two kinds. One is that some fast trains pass the station directly without stopping at the platform, and the other one is that trains stop for a time interval before leaving the station.In the first case, the train’s travel time through arrival-departure lines can be obtained directly according to the length of the arrival-departure lines and the speed of the trains:tcs=(Ls+Lc)/vc.In the second case, we consider the deceleration timetcsd when the speed of train c decelerates to0 to stop at the platform and the acceleration time tcsa when the train’s speed increases to vc from0 to leave the station. Then the travel time on the arrival-departure lines is tcs=tcsd+tcsa+tcss.For better expression in both cases, we adopt a binary variableτcss to imply if train c would stop at arrival-departure line s. Then the travel time on the arrival-departure lines can be calculated as follows:(8)tcs=τcsstcsd+tcsa+tcss+1-τcssLs+Lcvc.The departure time from the arrival-departure lines of the stopped trains is:(9)for  the  outbound  trainsc∈C1:tcf=tclend+tcsd+tcss,(10)for  the  inbound  trainsc∈C2:tcf=tcrend+tcsd+tcss.The end of occupied time at the arrival-departure lines is given at the same time:(11)for  the  outbound  trainsc∈C1:tcfend=tclend+tcs,(12)for  the  inbound  trainsc∈C2:tcfend=tcrend+tcs.In general, the relationship of train’s occupied time on the track can be illustrated clearly in Figure8. Figures 8(a) and 8(b) indicate the process of outbound trains and inbound trains passing through the station, respectively. The trends of curves in two graphs are similar since the principle of outbound trains and inbound trains is similar. The ordinate indicates train’s position when passing through the station, and the abscissa shows the time correspondingly. The red line represents trains that do not stop at the station and the blue one represents trains that would stop at the station.Figure 8
A space-time network of outbound and inbound trains passing through the rail station.
(a) (b)


### 2.5. Problem Statement and Notation

#### 2.5.1. Problem Description and Assumption

TRP is regarded as a pivotal component in providing high efficiency of operation, which can greatly affect the quality of train schedules and passengers service levels. In practice, TRP is often based on train planning problem, often predesigned by predicted demands and service capability. As mentioned above, the description of the physical railway station is restated in this paper. Moreover, the character of trains, the conflicts which may occur, and the calculation of trains’ travel time are introduced. In general, the problems we studied are the train routing optimization problems which involve lots of heterogeneous trains and many safety constraints in a complex high-speed railway station.Mathematically, we use binary decision variables to represent whether a train is allocated on a track segment or not. When a set of feasible decision variables are determined, the routing for each train can be specified concurrently. Then an integer decision variable is quoted to ensure punctuality of trains based on planned timetable. One of the objectives discussed in this paper is to minimize trains’ total travel time on the tracks in the station to ensure trains passing the station in a short time. It reduces the energy consumption and ensures the punctuality rate. It is worth noting that the route is shortest if train is allotted on the sidings close to main lines. Otherwise, the distance would increase if the train is arranged to stop on others, especially the furthest arrival-departure line from the main line. Nevertheless, it would cause serious wear and tear on the tracks if one arrival-departure line is often occupied repeatedly. Therefore, it is of importance to maintain the occupancy balance of the arrival-departure lines, which is reflected in the number of trains on the arrival-departure lines and the duration time. Finally, the punctuality of trains is considered so that it would not create trains delay to reduce the operation efficiency.Therefore, a mixed integer programming model is built based on the constraints of safety and station ability. The details and algorithm are discussed in Section3. The assumptions throughout this paper are listed as follows.Assumption 1.
The trains pass the station at a constant speedvc if they do not stop at the platform. For stopped trains, the additional acceleration and deceleration time of heterogeneous trains are same, respectively, for simplification.Assumption 2.
Due to the safety requirements of the fouling post, trains must stay within the fouling post. So we assume that all trains satisfy the safety requirements of the fouling post to ensure that the tails of trains would not collide.Assumption 3.
Each train has a planned departure time and cannot depart from the station earlier than the predetermined departure time.


#### 2.5.2. Notations

Regarding the trains, input data includes set/index, velocity, length, and other property parameters. In addition, it also covers relationship between trains, the time of trains’ setup, travel, and dwelling. Based on this basic input data of trains, we can further determine the relationship between trains and routes and trains occupation time and occupation end time, also predetermined as inputs of our model. As for the railway network, its input data involves the set/index of nodes and arcs, the set of connection of track segments, the length of different areas, and safety time interval and headway time. The details are summarized in Table1.Table 1
The indices, parameters, and sets.
Notations Description C Set of trains C 1,C2 Set of outbound trains and inbound trains respectively c Index of trains S Set of arrival-departure lines s Index of arrival-departure lines L , R Set of routes at left bottleneck and right bottleneck respectively l, r Index of routes at left bottleneck and right bottleneck respectively P Set of trains’ routes D,A Set of nodes and arcs of railway network respectively R s l, Rsr Set of left and right bottleneck routes connected to the arrival-departure linesrespectively α c Weight of the heterogeneous trains β Weight of different objective functions L l,Lr Length of routes in the left and the right bottleneck respectively L s Length of the arrival-departure lines L c Length of trains L d 1 d 2 Length of the track segment betweend1 and d2 t c ∗ Planned starting time of traincto pull into the station t c f Actual departure time of traincfrom the station v c Speed of trainc t c s e t u p Setup time of trainc t c l e n d Occupation end time at the left bottleneck of outbound trains t c r e n d Occupation end time at the right bottleneck of inbound trains t c f e n d Occupation end time at the arrival-departure lines t c s Travel time at the arrival-departure lines of train c t c s s Dwell time at the arrival-departure lines of train c t c s d, tcsa Additional times corresponding to acceleration and deceleration of trains, respectively t c s l, tcsre Travel time at left bottleneck to arrive and at right bottleneck to depart of outbound trainc t c s r, tcsle Travel time at right bottleneck to arrive and at left bottleneck to depart of inbound trainc t c 1 c 2 c o n Time interval between trainsc1 and c2 entering the conflict track segments τ c s s Binary parameters, if trainc would stop at arrival-departure lines, τcss=1, else, τcss=0 γ c 1 c 2 Binary parameters, if potential conflicts exist,γc1c2=1, else, γc1c2=0 θ p 1 p 2 Binary parameters, if there are conflicts between routesp1 and p2, θp1p2=1, else, θp1p2=0,l,s,r∈p δ s 1 s 2 Binary parameters, if arrival-departure liness1 and s2 are close to the same platform, δs1,s2=1, else, δs1,s2=0 ϑ c 1 c 2 Binary parameters, if there is transfer relationship between trainsc1 and c2, ϑc1,c2=1, else, ϑc1,c2=0 T m 1 Headway time of trains which occupy the same arrival-departure lines T m 2 Minimum time interval of two trains at the potential conflict area T m 3 Minimum transfer time of passengers on the platformThe outputs of TRP compose the traverse route sets of trains when they arrive at and depart form the station and the starting time of trains to pull into the station, as well as their precedence relation of two trains at the same track. The details are introduced in Table2.Table 2
Decision variables.
Notations Description x c s Binary variables, if the arrival-departure lines is occupied by the trainc, xcs=1. Otherwise, xcs=0 x c l i Binary variables, if the routel in the left bottleneck is occupied by the outbound train cwhen pulls in, xcli=1. Otherwise, xcli=1 x c l o Binary variables, if the routel in the left bottleneck is occupied by the inbound train cwhen departs from the station, xcli=1. Otherwise, xcli=1 x c r i Binary variables, if the router in the right bottleneck is occupied by the inbound train cwhen pulls in, xcri=1. Otherwise, xcri=1 x c r o Binary variables, if the routerin the right bottleneck is occupied by the outbound train cwhen departs from the station, xcro=1. Otherwise, xcro=1 t c Integer variables, indicates the starting time of trainc to pull into the station δ c 1 , c 2 Binary variables, indicates the trainsc1 and c2 precedence relation at the same track. If the train c1 precedes c2, δc1,c2=1. Otherwise, δc1,c2=0


## 2.1. Layout of Railway Station

We consider a railway station as illustrated in Figure1. This railway station consists of bottlenecks and some arrival-departure lines whose length is Ls. The left side of the station in Figure 1 is defined as left bottleneck whose length is Ll. The route set of it is L=l1,l2,⋯,lk1. Similarly, the right side is defined as right bottleneck whose length is Lr. The route set of it is R=r1,r2,⋯,rk2. The bottleneck involves tracks where trains arrive and depart. For instance, an outbound train arrives from node d1 and stops at arrival-departure line. In Figure 2(a), there are 4 possible routes for the outbound train that arrives from node d1, whose set is L1=l1,l2,l3,l4 in the left bottleneck. Similar, an inbound train departs from arrival-departure line to the node d2. There are also 4 possible routes for the inbound train departs from node d2 as shown in Figure 2(b) whose set is L2=l5,l6,l7,l8. So the route set of the left bottleneck is L=L1∪L2=l1,l2,…,l8. In particular, at large stations, the number of routes in the bottleneck may be larger than the number of arrival-departure lines due to the existence of multiple crossovers and turnouts. The route set of arrival-departure lines is S=s1,s2,…,sm, which containsI,II,3, and4 as shown in Figure 1.Figure 1
An illustration of a railway station.Figure 2
The route set of left bottleneck in the railway station.
(a) (b)Normally, track lines are divided by insulation joints. In this paper, the turnout node and the arrival-departure line node are defined as follows to describe the railway station.1.
Turnout node: the intersection of the lines in the station. It includes turnouts (as shown in Figure 1, d5 and d6, etc.), crossovers (as shown in Figure 1, d7, etc.), and the position of signal which located in the entrance of the bottleneck (i.e., the boundary point of the station).2.
Arrival-departure line node: the connection points of bottleneck and arrival-departure lines in the railway station, namely, the signal position of the entrance of the arrival-departure lines (i.e.. the nodes d8~d10 in Figure 1).During the operation, the outbound trains can only arrive from turnout noded1 and depart from turnout node d3 as shown in Figure 1. Similar, the inbound trains can only arrive from turnout node d4 and depart from turnout node d2. However, no matter in which direction trains are, any of arrival-departure lines can be occupied. Hence the physical network of the railway is regarded as a directed graph. The nodes are regarded as vertices, and the actual connection of the lines is regarded as arcs. Let D denote the set of all vertices and A denote the set of all arcs in the network.


## 2.2. Trains

We consider a set of trains in both directions. The set of trains is denoted byC=c1,c2,⋯,cn, in which C1=c1,c3,c5,⋯ is the set of outbound trains and C2=c2,c4,c6,⋯ is the set of inbound trains. The heterogeneous trains are taken into account. We assume that these trains are categorized into two types: slow trains and fast trains. In addition, there are shunting operation beside train reception and departure operations. The speeds of shunting trains are slower than the ordinary trains.In addition, some of the fast trains pass the station without stopping while some trains stop at platform for passengers to alight or transfer. Different trains’ stop time may be different, whether they are fast or slow trains. As we all know, the speed of trains is not a constant, while it changes with the driver’s braking when the train would stop at the platform. Similarly, the speed of trains does not increase suddenly when departing from the platform. Therefore, the additional time that provides trains’ acceleration and deceleration is considered. At the same time, the length of trains is also taken into account to meet the actual situation.


## 2.3. Conflicts and Potential Conflicts

The conflicts of tracks which trains occupy are the most imperative problem to be solved in TRP. In other words, trains cannot occupy the same track at the same time. A conflict occurs whenever trains traverse the same track and do not respect the minimum time interval at the bottleneck and arrival-departure lines. What is more, it would result in potential conflicts. These situations are discussed separately as follows.


### 2.3.1. Train Routing Conflicts at Bottleneck

The bottleneck consists of channels with some turnouts, crossovers, and other facilities, which may cause spatial intersections of trains’ alternative sets of routes, especially when some unpredictable events or interruptions occurred. So it is an important task for train dispatchers to avoid the train collision and to assure the trains passing the tracks orderly. The conflicts between two trains in the bottleneck mainly occurred at the intersection of the track segments (the segmentd1~d2 as shown in Figure 3) and the intersection of crossovers (the point d3 as shown in Figure 3).Figure 3
The same/reverse direction conflicts of trains routing.
(a) (b)In Figures3(a) and 3(b), trains c1/c2 travel in the same/reverse direction, and the collision occurs at the track segment between nodes d1 and d2. Similarly, the collision occurs at the track segment at the node d3 when the trains c2 and c3 travel in the same and reverse direction, respectively. The methods to dissipate conflicts will be depicted in detail in Section 3.


### 2.3.2. Train Routing Conflicts at Arrival-Departure Lines

When two consecutive trains plan to occupy the same arrival-departure line in the railway station, they should follow a headway time to suit the limited infrastructure capacity. That is, one train occupies this arrival-departure line a specific headway time later than the other one. As shown in Figure4, there are two trains c1 and c2. The origin and destination of train c1 are A and C, respectively, and the origin and destination of train c2 are B and C. Obviously, if the route p1 is assigned to c1 and c2 occupies route p2 in a short interval, this would cause a conflict at platform 1. In this case, the latter train should stop and wait until the previous train leaves from the platform 1 for a reasonable headway time. It may cause the latter train to be behind the schedule time and even to have second delay in severe cases. But if the train c2 occupies route p3, the conflicts would be avoided and the train operational efficiency would be ensured in the railway station.Figure 4
The conflict at arrival-departure lines.Therefore, if the two trains’ departure interval is smaller than the headway timeTm1, it is better to arrange them at different lines. Just as illustrated in Figure 4, if the difference of two trains’ departure time is bigger than the headway time Tm1, the same arrival-departure line can be arranged.


### 2.3.3. Potential Conflicts of Train Routing

It is noteworthy that only considering trains’ routing at bottleneck and headway time at arrival-departure lines cannot completely meet the requirement of safe operation. There are further potential conflicts.For instance, the outbound trainc1 would stop at arrival-departure lineII from outbound main line while the inbound train c2 would depart from line3 to the inbound main line (as shown in Figure 5(a), the yellow dotted line and the blue dotted line represent the route of trains c1 and c2, respectively). There is no time provided to avoid the potential conflict area (the red circle area in Figure 5), since it is not in the context of the two conflicts described above. Therefore, a time separation should be adopted even though two trains do not occupy the same track; i.e., c1 first arrives and then c2 departs later or c2 first leaves and then c1 arrives later, the same as shown in Figure 5(b). It is necessary to set constraints so that two consecutive trains arrive the potential conflict area in a time separation.Figure 5
The illustrative of outbound and inbound trains’ potential conflicts.
(a) (b)In addition, when two trains are in the same direction, the conflicts between them are not potential conflicts. Just as shown in Figure6, c1 and c2 are outbound trains. It is apparent that there exists a conflict in the red circle area. However, due to the conflicts at the bottleneck between the two trains, the constraints are set to avoid the collision; namely, conflicts in the rad circle area are also dissolved. Therefore, the potential constraints we discussed are only among the reverse trains.Figure 6
The illustrative of the same direction trains occupied different lines.


## 2.3.1. Train Routing Conflicts at Bottleneck

The bottleneck consists of channels with some turnouts, crossovers, and other facilities, which may cause spatial intersections of trains’ alternative sets of routes, especially when some unpredictable events or interruptions occurred. So it is an important task for train dispatchers to avoid the train collision and to assure the trains passing the tracks orderly. The conflicts between two trains in the bottleneck mainly occurred at the intersection of the track segments (the segmentd1~d2 as shown in Figure 3) and the intersection of crossovers (the point d3 as shown in Figure 3).Figure 3
The same/reverse direction conflicts of trains routing.
(a) (b)In Figures3(a) and 3(b), trains c1/c2 travel in the same/reverse direction, and the collision occurs at the track segment between nodes d1 and d2. Similarly, the collision occurs at the track segment at the node d3 when the trains c2 and c3 travel in the same and reverse direction, respectively. The methods to dissipate conflicts will be depicted in detail in Section 3.


## 2.3.2. Train Routing Conflicts at Arrival-Departure Lines

When two consecutive trains plan to occupy the same arrival-departure line in the railway station, they should follow a headway time to suit the limited infrastructure capacity. That is, one train occupies this arrival-departure line a specific headway time later than the other one. As shown in Figure4, there are two trains c1 and c2. The origin and destination of train c1 are A and C, respectively, and the origin and destination of train c2 are B and C. Obviously, if the route p1 is assigned to c1 and c2 occupies route p2 in a short interval, this would cause a conflict at platform 1. In this case, the latter train should stop and wait until the previous train leaves from the platform 1 for a reasonable headway time. It may cause the latter train to be behind the schedule time and even to have second delay in severe cases. But if the train c2 occupies route p3, the conflicts would be avoided and the train operational efficiency would be ensured in the railway station.Figure 4
The conflict at arrival-departure lines.Therefore, if the two trains’ departure interval is smaller than the headway timeTm1, it is better to arrange them at different lines. Just as illustrated in Figure 4, if the difference of two trains’ departure time is bigger than the headway time Tm1, the same arrival-departure line can be arranged.


## 2.3.3. Potential Conflicts of Train Routing

It is noteworthy that only considering trains’ routing at bottleneck and headway time at arrival-departure lines cannot completely meet the requirement of safe operation. There are further potential conflicts.For instance, the outbound trainc1 would stop at arrival-departure lineII from outbound main line while the inbound train c2 would depart from line3 to the inbound main line (as shown in Figure 5(a), the yellow dotted line and the blue dotted line represent the route of trains c1 and c2, respectively). There is no time provided to avoid the potential conflict area (the red circle area in Figure 5), since it is not in the context of the two conflicts described above. Therefore, a time separation should be adopted even though two trains do not occupy the same track; i.e., c1 first arrives and then c2 departs later or c2 first leaves and then c1 arrives later, the same as shown in Figure 5(b). It is necessary to set constraints so that two consecutive trains arrive the potential conflict area in a time separation.Figure 5
The illustrative of outbound and inbound trains’ potential conflicts.
(a) (b)In addition, when two trains are in the same direction, the conflicts between them are not potential conflicts. Just as shown in Figure6, c1 and c2 are outbound trains. It is apparent that there exists a conflict in the red circle area. However, due to the conflicts at the bottleneck between the two trains, the constraints are set to avoid the collision; namely, conflicts in the rad circle area are also dissolved. Therefore, the potential constraints we discussed are only among the reverse trains.Figure 6
The illustrative of the same direction trains occupied different lines.


## 2.4. The Calculation Methods of Track Occupation Time

In this paper, not only is the train routing chosen as the decision variables but also optimized the schedule of trains to start entering the station according to the planned schedule when trains depart from the station. Thus the time for trains passing the conflict tracks needs be calculated. In addition, the convenience factors of passengers transferring at station are taken into account, and the associated trains’ dwell-time intersection should be long enough. As a consequence, the trains’ travel time in different track sections should be clearly calculated.To our knowledge, as long as a track segment is occupied, the lines, the fouling posts, and the signals are also occupied at the same time. We elaborate the calculation of the occupied time and the end time of occupied of trains passing through the left bottleneck, the arrival-departure lines, and the right bottleneck in turn. The occupied trains at the bottleneck are divided into two situations: train reception and train departure, whose calculated method of train occupied time of tracks is same. So only take the outbound trains as an example to explain in detail.


### 2.4.1. The Calculation of Trains Travel Time and the End Time of Occupied at the Bottleneck

For outbound trainsc∈C1 in the left bottleneck l∈L, they start to enter the station at tc+tcsetup and pass each node with speed vc. The track is unlocked after their tails pass the end node of the track section. So the trains’ occupied time of each track segment is calculated as follows:(1)ta=Lavc,where ta is occupancy time of a certain track segment a and La is length of the track segment a. Thus, the travel time of outbound trains c∈C1 from the left bottleneck signals to the arrival-departure lines is calculated with the following:(2)tcsl=Ll+Lcvc,where Ll is length of routes which is sum of each track segment in the left bottleneck and Lc is the length of the train c. In Figure 7, the length of Ld1~d10 is the sum of lengths of d1~d6 and d6~d10; the length of Ld1~d11 is the sum of lengths of d1~d6 and d6~d11. That is, the length of the different routes in the left bottleneck is different. The end of the left bottleneck occupied time of outbound trains is(3)tclend=tc+tcsetup+tcsl.Figure 7
The calculation of trains’ travel time in station.Take the railway station in Figure1 as an example to calculate the occupancy time of one route of outbound train in the left bottleneck. As shown in Figure 7, it is assumed that the train arrives from the node d1 and stops at lineI (i.e., the green dashed line in Figure 7). Then the travel time of train c from the left bottleneck signal to the line I is calculated as tcsIl1=(Ld1~d10+Lc)/vc. The end of the left bottleneck occupied time is tcl1end=tc+tcsetup+tcsIl1.The occupied time of outbound trains departing from the station through the right bottleneck is calculated as(4)tcsre=Lr+Lcvc,Similarly, the travel time of trains departing from the lineI and leaving to node d3 through the right bottleneck (i.e., the blue dashed line in Figure 7) is calculated as tcsIr1e=(Ld9~d3+Lc)/vc.For the inbound trainsc∈C2, the calculation of trains travel time and the end time of occupied at right bottleneck are as follows, respectively:(5)tcsr=Lr+Lcvc.(6)tcrend=tc+tcsetup+tcsr.The travel time in the left bottleneck when the train departs from the station is calculated by(7)tcsle=Ll+Lcvc.


### 2.4.2. The Calculation of Trains Travel Time and the End of Occupied Time at Arrival-Departure Lines

The occupation of arrival-departure lines can be partitioned into two kinds. One is that some fast trains pass the station directly without stopping at the platform, and the other one is that trains stop for a time interval before leaving the station.In the first case, the train’s travel time through arrival-departure lines can be obtained directly according to the length of the arrival-departure lines and the speed of the trains:tcs=(Ls+Lc)/vc.In the second case, we consider the deceleration timetcsd when the speed of train c decelerates to0 to stop at the platform and the acceleration time tcsa when the train’s speed increases to vc from0 to leave the station. Then the travel time on the arrival-departure lines is tcs=tcsd+tcsa+tcss.For better expression in both cases, we adopt a binary variableτcss to imply if train c would stop at arrival-departure line s. Then the travel time on the arrival-departure lines can be calculated as follows:(8)tcs=τcsstcsd+tcsa+tcss+1-τcssLs+Lcvc.The departure time from the arrival-departure lines of the stopped trains is:(9)for  the  outbound  trainsc∈C1:tcf=tclend+tcsd+tcss,(10)for  the  inbound  trainsc∈C2:tcf=tcrend+tcsd+tcss.The end of occupied time at the arrival-departure lines is given at the same time:(11)for  the  outbound  trainsc∈C1:tcfend=tclend+tcs,(12)for  the  inbound  trainsc∈C2:tcfend=tcrend+tcs.In general, the relationship of train’s occupied time on the track can be illustrated clearly in Figure8. Figures 8(a) and 8(b) indicate the process of outbound trains and inbound trains passing through the station, respectively. The trends of curves in two graphs are similar since the principle of outbound trains and inbound trains is similar. The ordinate indicates train’s position when passing through the station, and the abscissa shows the time correspondingly. The red line represents trains that do not stop at the station and the blue one represents trains that would stop at the station.Figure 8
A space-time network of outbound and inbound trains passing through the rail station.
(a) (b)


## 2.4.1. The Calculation of Trains Travel Time and the End Time of Occupied at the Bottleneck

For outbound trainsc∈C1 in the left bottleneck l∈L, they start to enter the station at tc+tcsetup and pass each node with speed vc. The track is unlocked after their tails pass the end node of the track section. So the trains’ occupied time of each track segment is calculated as follows:(1)ta=Lavc,where ta is occupancy time of a certain track segment a and La is length of the track segment a. Thus, the travel time of outbound trains c∈C1 from the left bottleneck signals to the arrival-departure lines is calculated with the following:(2)tcsl=Ll+Lcvc,where Ll is length of routes which is sum of each track segment in the left bottleneck and Lc is the length of the train c. In Figure 7, the length of Ld1~d10 is the sum of lengths of d1~d6 and d6~d10; the length of Ld1~d11 is the sum of lengths of d1~d6 and d6~d11. That is, the length of the different routes in the left bottleneck is different. The end of the left bottleneck occupied time of outbound trains is(3)tclend=tc+tcsetup+tcsl.Figure 7
The calculation of trains’ travel time in station.Take the railway station in Figure1 as an example to calculate the occupancy time of one route of outbound train in the left bottleneck. As shown in Figure 7, it is assumed that the train arrives from the node d1 and stops at lineI (i.e., the green dashed line in Figure 7). Then the travel time of train c from the left bottleneck signal to the line I is calculated as tcsIl1=(Ld1~d10+Lc)/vc. The end of the left bottleneck occupied time is tcl1end=tc+tcsetup+tcsIl1.The occupied time of outbound trains departing from the station through the right bottleneck is calculated as(4)tcsre=Lr+Lcvc,Similarly, the travel time of trains departing from the lineI and leaving to node d3 through the right bottleneck (i.e., the blue dashed line in Figure 7) is calculated as tcsIr1e=(Ld9~d3+Lc)/vc.For the inbound trainsc∈C2, the calculation of trains travel time and the end time of occupied at right bottleneck are as follows, respectively:(5)tcsr=Lr+Lcvc.(6)tcrend=tc+tcsetup+tcsr.The travel time in the left bottleneck when the train departs from the station is calculated by(7)tcsle=Ll+Lcvc.


## 2.4.2. The Calculation of Trains Travel Time and the End of Occupied Time at Arrival-Departure Lines

The occupation of arrival-departure lines can be partitioned into two kinds. One is that some fast trains pass the station directly without stopping at the platform, and the other one is that trains stop for a time interval before leaving the station.In the first case, the train’s travel time through arrival-departure lines can be obtained directly according to the length of the arrival-departure lines and the speed of the trains:tcs=(Ls+Lc)/vc.In the second case, we consider the deceleration timetcsd when the speed of train c decelerates to0 to stop at the platform and the acceleration time tcsa when the train’s speed increases to vc from0 to leave the station. Then the travel time on the arrival-departure lines is tcs=tcsd+tcsa+tcss.For better expression in both cases, we adopt a binary variableτcss to imply if train c would stop at arrival-departure line s. Then the travel time on the arrival-departure lines can be calculated as follows:(8)tcs=τcsstcsd+tcsa+tcss+1-τcssLs+Lcvc.The departure time from the arrival-departure lines of the stopped trains is:(9)for  the  outbound  trainsc∈C1:tcf=tclend+tcsd+tcss,(10)for  the  inbound  trainsc∈C2:tcf=tcrend+tcsd+tcss.The end of occupied time at the arrival-departure lines is given at the same time:(11)for  the  outbound  trainsc∈C1:tcfend=tclend+tcs,(12)for  the  inbound  trainsc∈C2:tcfend=tcrend+tcs.In general, the relationship of train’s occupied time on the track can be illustrated clearly in Figure8. Figures 8(a) and 8(b) indicate the process of outbound trains and inbound trains passing through the station, respectively. The trends of curves in two graphs are similar since the principle of outbound trains and inbound trains is similar. The ordinate indicates train’s position when passing through the station, and the abscissa shows the time correspondingly. The red line represents trains that do not stop at the station and the blue one represents trains that would stop at the station.Figure 8
A space-time network of outbound and inbound trains passing through the rail station.
(a) (b)


## 2.5. Problem Statement and Notation

### 2.5.1. Problem Description and Assumption

TRP is regarded as a pivotal component in providing high efficiency of operation, which can greatly affect the quality of train schedules and passengers service levels. In practice, TRP is often based on train planning problem, often predesigned by predicted demands and service capability. As mentioned above, the description of the physical railway station is restated in this paper. Moreover, the character of trains, the conflicts which may occur, and the calculation of trains’ travel time are introduced. In general, the problems we studied are the train routing optimization problems which involve lots of heterogeneous trains and many safety constraints in a complex high-speed railway station.Mathematically, we use binary decision variables to represent whether a train is allocated on a track segment or not. When a set of feasible decision variables are determined, the routing for each train can be specified concurrently. Then an integer decision variable is quoted to ensure punctuality of trains based on planned timetable. One of the objectives discussed in this paper is to minimize trains’ total travel time on the tracks in the station to ensure trains passing the station in a short time. It reduces the energy consumption and ensures the punctuality rate. It is worth noting that the route is shortest if train is allotted on the sidings close to main lines. Otherwise, the distance would increase if the train is arranged to stop on others, especially the furthest arrival-departure line from the main line. Nevertheless, it would cause serious wear and tear on the tracks if one arrival-departure line is often occupied repeatedly. Therefore, it is of importance to maintain the occupancy balance of the arrival-departure lines, which is reflected in the number of trains on the arrival-departure lines and the duration time. Finally, the punctuality of trains is considered so that it would not create trains delay to reduce the operation efficiency.Therefore, a mixed integer programming model is built based on the constraints of safety and station ability. The details and algorithm are discussed in Section3. The assumptions throughout this paper are listed as follows.Assumption 1.
The trains pass the station at a constant speedvc if they do not stop at the platform. For stopped trains, the additional acceleration and deceleration time of heterogeneous trains are same, respectively, for simplification.Assumption 2.
Due to the safety requirements of the fouling post, trains must stay within the fouling post. So we assume that all trains satisfy the safety requirements of the fouling post to ensure that the tails of trains would not collide.Assumption 3.
Each train has a planned departure time and cannot depart from the station earlier than the predetermined departure time.


### 2.5.2. Notations

Regarding the trains, input data includes set/index, velocity, length, and other property parameters. In addition, it also covers relationship between trains, the time of trains’ setup, travel, and dwelling. Based on this basic input data of trains, we can further determine the relationship between trains and routes and trains occupation time and occupation end time, also predetermined as inputs of our model. As for the railway network, its input data involves the set/index of nodes and arcs, the set of connection of track segments, the length of different areas, and safety time interval and headway time. The details are summarized in Table1.Table 1
The indices, parameters, and sets.
Notations Description C Set of trains C 1,C2 Set of outbound trains and inbound trains respectively c Index of trains S Set of arrival-departure lines s Index of arrival-departure lines L , R Set of routes at left bottleneck and right bottleneck respectively l, r Index of routes at left bottleneck and right bottleneck respectively P Set of trains’ routes D,A Set of nodes and arcs of railway network respectively R s l, Rsr Set of left and right bottleneck routes connected to the arrival-departure linesrespectively α c Weight of the heterogeneous trains β Weight of different objective functions L l,Lr Length of routes in the left and the right bottleneck respectively L s Length of the arrival-departure lines L c Length of trains L d 1 d 2 Length of the track segment betweend1 and d2 t c ∗ Planned starting time of traincto pull into the station t c f Actual departure time of traincfrom the station v c Speed of trainc t c s e t u p Setup time of trainc t c l e n d Occupation end time at the left bottleneck of outbound trains t c r e n d Occupation end time at the right bottleneck of inbound trains t c f e n d Occupation end time at the arrival-departure lines t c s Travel time at the arrival-departure lines of train c t c s s Dwell time at the arrival-departure lines of train c t c s d, tcsa Additional times corresponding to acceleration and deceleration of trains, respectively t c s l, tcsre Travel time at left bottleneck to arrive and at right bottleneck to depart of outbound trainc t c s r, tcsle Travel time at right bottleneck to arrive and at left bottleneck to depart of inbound trainc t c 1 c 2 c o n Time interval between trainsc1 and c2 entering the conflict track segments τ c s s Binary parameters, if trainc would stop at arrival-departure lines, τcss=1, else, τcss=0 γ c 1 c 2 Binary parameters, if potential conflicts exist,γc1c2=1, else, γc1c2=0 θ p 1 p 2 Binary parameters, if there are conflicts between routesp1 and p2, θp1p2=1, else, θp1p2=0,l,s,r∈p δ s 1 s 2 Binary parameters, if arrival-departure liness1 and s2 are close to the same platform, δs1,s2=1, else, δs1,s2=0 ϑ c 1 c 2 Binary parameters, if there is transfer relationship between trainsc1 and c2, ϑc1,c2=1, else, ϑc1,c2=0 T m 1 Headway time of trains which occupy the same arrival-departure lines T m 2 Minimum time interval of two trains at the potential conflict area T m 3 Minimum transfer time of passengers on the platformThe outputs of TRP compose the traverse route sets of trains when they arrive at and depart form the station and the starting time of trains to pull into the station, as well as their precedence relation of two trains at the same track. The details are introduced in Table2.Table 2
Decision variables.
Notations Description x c s Binary variables, if the arrival-departure lines is occupied by the trainc, xcs=1. Otherwise, xcs=0 x c l i Binary variables, if the routel in the left bottleneck is occupied by the outbound train cwhen pulls in, xcli=1. Otherwise, xcli=1 x c l o Binary variables, if the routel in the left bottleneck is occupied by the inbound train cwhen departs from the station, xcli=1. Otherwise, xcli=1 x c r i Binary variables, if the router in the right bottleneck is occupied by the inbound train cwhen pulls in, xcri=1. Otherwise, xcri=1 x c r o Binary variables, if the routerin the right bottleneck is occupied by the outbound train cwhen departs from the station, xcro=1. Otherwise, xcro=1 t c Integer variables, indicates the starting time of trainc to pull into the station δ c 1 , c 2 Binary variables, indicates the trainsc1 and c2 precedence relation at the same track. If the train c1 precedes c2, δc1,c2=1. Otherwise, δc1,c2=0


## 2.5.1. Problem Description and Assumption

TRP is regarded as a pivotal component in providing high efficiency of operation, which can greatly affect the quality of train schedules and passengers service levels. In practice, TRP is often based on train planning problem, often predesigned by predicted demands and service capability. As mentioned above, the description of the physical railway station is restated in this paper. Moreover, the character of trains, the conflicts which may occur, and the calculation of trains’ travel time are introduced. In general, the problems we studied are the train routing optimization problems which involve lots of heterogeneous trains and many safety constraints in a complex high-speed railway station.Mathematically, we use binary decision variables to represent whether a train is allocated on a track segment or not. When a set of feasible decision variables are determined, the routing for each train can be specified concurrently. Then an integer decision variable is quoted to ensure punctuality of trains based on planned timetable. One of the objectives discussed in this paper is to minimize trains’ total travel time on the tracks in the station to ensure trains passing the station in a short time. It reduces the energy consumption and ensures the punctuality rate. It is worth noting that the route is shortest if train is allotted on the sidings close to main lines. Otherwise, the distance would increase if the train is arranged to stop on others, especially the furthest arrival-departure line from the main line. Nevertheless, it would cause serious wear and tear on the tracks if one arrival-departure line is often occupied repeatedly. Therefore, it is of importance to maintain the occupancy balance of the arrival-departure lines, which is reflected in the number of trains on the arrival-departure lines and the duration time. Finally, the punctuality of trains is considered so that it would not create trains delay to reduce the operation efficiency.Therefore, a mixed integer programming model is built based on the constraints of safety and station ability. The details and algorithm are discussed in Section3. The assumptions throughout this paper are listed as follows.Assumption 1.
The trains pass the station at a constant speedvc if they do not stop at the platform. For stopped trains, the additional acceleration and deceleration time of heterogeneous trains are same, respectively, for simplification.Assumption 2.
Due to the safety requirements of the fouling post, trains must stay within the fouling post. So we assume that all trains satisfy the safety requirements of the fouling post to ensure that the tails of trains would not collide.Assumption 3.
Each train has a planned departure time and cannot depart from the station earlier than the predetermined departure time.


## 2.5.2. Notations

Regarding the trains, input data includes set/index, velocity, length, and other property parameters. In addition, it also covers relationship between trains, the time of trains’ setup, travel, and dwelling. Based on this basic input data of trains, we can further determine the relationship between trains and routes and trains occupation time and occupation end time, also predetermined as inputs of our model. As for the railway network, its input data involves the set/index of nodes and arcs, the set of connection of track segments, the length of different areas, and safety time interval and headway time. The details are summarized in Table1.Table 1
The indices, parameters, and sets.
Notations Description C Set of trains C 1,C2 Set of outbound trains and inbound trains respectively c Index of trains S Set of arrival-departure lines s Index of arrival-departure lines L , R Set of routes at left bottleneck and right bottleneck respectively l, r Index of routes at left bottleneck and right bottleneck respectively P Set of trains’ routes D,A Set of nodes and arcs of railway network respectively R s l, Rsr Set of left and right bottleneck routes connected to the arrival-departure linesrespectively α c Weight of the heterogeneous trains β Weight of different objective functions L l,Lr Length of routes in the left and the right bottleneck respectively L s Length of the arrival-departure lines L c Length of trains L d 1 d 2 Length of the track segment betweend1 and d2 t c ∗ Planned starting time of traincto pull into the station t c f Actual departure time of traincfrom the station v c Speed of trainc t c s e t u p Setup time of trainc t c l e n d Occupation end time at the left bottleneck of outbound trains t c r e n d Occupation end time at the right bottleneck of inbound trains t c f e n d Occupation end time at the arrival-departure lines t c s Travel time at the arrival-departure lines of train c t c s s Dwell time at the arrival-departure lines of train c t c s d, tcsa Additional times corresponding to acceleration and deceleration of trains, respectively t c s l, tcsre Travel time at left bottleneck to arrive and at right bottleneck to depart of outbound trainc t c s r, tcsle Travel time at right bottleneck to arrive and at left bottleneck to depart of inbound trainc t c 1 c 2 c o n Time interval between trainsc1 and c2 entering the conflict track segments τ c s s Binary parameters, if trainc would stop at arrival-departure lines, τcss=1, else, τcss=0 γ c 1 c 2 Binary parameters, if potential conflicts exist,γc1c2=1, else, γc1c2=0 θ p 1 p 2 Binary parameters, if there are conflicts between routesp1 and p2, θp1p2=1, else, θp1p2=0,l,s,r∈p δ s 1 s 2 Binary parameters, if arrival-departure liness1 and s2 are close to the same platform, δs1,s2=1, else, δs1,s2=0 ϑ c 1 c 2 Binary parameters, if there is transfer relationship between trainsc1 and c2, ϑc1,c2=1, else, ϑc1,c2=0 T m 1 Headway time of trains which occupy the same arrival-departure lines T m 2 Minimum time interval of two trains at the potential conflict area T m 3 Minimum transfer time of passengers on the platformThe outputs of TRP compose the traverse route sets of trains when they arrive at and depart form the station and the starting time of trains to pull into the station, as well as their precedence relation of two trains at the same track. The details are introduced in Table2.Table 2
Decision variables.
Notations Description x c s Binary variables, if the arrival-departure lines is occupied by the trainc, xcs=1. Otherwise, xcs=0 x c l i Binary variables, if the routel in the left bottleneck is occupied by the outbound train cwhen pulls in, xcli=1. Otherwise, xcli=1 x c l o Binary variables, if the routel in the left bottleneck is occupied by the inbound train cwhen departs from the station, xcli=1. Otherwise, xcli=1 x c r i Binary variables, if the router in the right bottleneck is occupied by the inbound train cwhen pulls in, xcri=1. Otherwise, xcri=1 x c r o Binary variables, if the routerin the right bottleneck is occupied by the outbound train cwhen departs from the station, xcro=1. Otherwise, xcro=1 t c Integer variables, indicates the starting time of trainc to pull into the station δ c 1 , c 2 Binary variables, indicates the trainsc1 and c2 precedence relation at the same track. If the train c1 precedes c2, δc1,c2=1. Otherwise, δc1,c2=0


## 3. Mathematical Model of TRP in High-Speed Railway Station

In this section, we put forward a mathematical model for TRP in a high-speed rail station. To depict this problem more clearly, the following discussion will concentrate on specifying each part of the models, including the objective functions and systematic constraints.


### 3.1. Objective Function

#### 3.1.1. Utilization Balanced of the Arrival-Departure Lines

During railway operations, the challenge is to decrease the overall cost by means of a more efficient use of available resources as mentioned in Giacco et al. [23]. It is worth noting that the route is shortest if train is allotted on the sidings close to main lines. Otherwise, the distance would increase if the train is arranged to stop on others, especially the furthest arrival-departure line from the main line. If the objective is only to minimize the trains’ total travel time, a large number of trains would like to stop at the arrival-departure lines near the main line, while the arrival-departure lines far from the main line are not occupied. If things go on like this it would cause serious wear and tear on the tracks if one arrival-departure line is often occupied repeatedly, which may bring extra costs owing to the frequent maintenance and repaired, the utilization proportionality of the arrival-departure lines should be kept when arranging trains’ routes. The served trains provided by the arrival-departure lines include passing trains and stopping trains. As can be seen, the equilibrium is not only reflected in the number of trains, but also in the train’s travel time that involves dwell time on the arrival-departure lines. It is converted into the mathematical expression and represented by the sum of variances of the number of trains and their dwell times: (13)minz1=1m∑s∈S∑c∈Cxcs-nm2+1m∑s∈S∑c∈Ctcsxcs-∑c∈Ctcsm2.In the objective function (13),m is the number of arrival-departure lines and n is the number of trains (i.e., the number of arrival-departure lines that are occupied). ∑c∈Ctcsxcs denotes the sum of all trains’ travel time on the arrival-departure lines. The first half of the function (13) shows the number of trains’ occupancy balance and the second half means that the trains’ travel time are relatively balanced on the arrival-departure lines.


#### 3.1.2. Minimize the Trains’ Total Travel Time

Trains’ travel time on the tracks is another important factor in the optimization of the train routing problem. So the second optimization objective function is minimizing the trains’ total travel time in the station:(14)minz2=∑s∈S∑l∈L∑r∈R∑c∈C1αcxclitcsl+xcstcs+xcrotcsle+∑s∈S∑l∈L∑r∈R∑c∈C2αcxcritcsr+xcstcs+xclotcsle.In (14), the front part indicates the total travel time of outbound trains c∈C1; the last half expresses inbound trains c∈C2 total travel time in the railway station. In order to ensure the satisfaction of passengers, the train reception and departure operations are punctuality and cannot be adjusted drastically. Compared to this, the shunting operations can be adjusted to be relatively flexible.  At the same time, the punctuality requirements are different for different types of trains (passenger trains and freight trains). Therefore, the weight coefficient αc is introduced to indicate the significance of each train.


#### 3.1.3. Minimize the Trains’ Total Departure Time Deviations

For railway operators, the punctuality of trains is necessary for the order and efficient operation of the station. Meanwhile, it is also the most concern of passengers. Therefore, the third optimization objective considered in this paper is minimizing the trains’ total deviations between the trains’ starting time to enter the station and the planned timetables of trains pulling in(15)minz3=∑c∈Cαctc-tc∗.In (15), the same αc weight coefficient is quoted. tc is the starting time of train c pulling into the station, and tc∗ represents the planned entering time of trains which can calculate through pregiven timetable.In summary, the linearly weighted compromise approach is adopted to handle the objective functions, and the objective function studied in this paper is(16)minZ=β1z1+β2z2+β3z3.In the objective function (16), βi(i=1,2,3) are the weight coefficients with 0≤βi≤1(i=1,2,3) and meet the equation requirement: β1+β2+β3=1. It is set to distinguish the importance of different objectives. The specific values are given in the cases study.


### 3.2. Constraints

#### 3.2.1. Constraints of Conflicts and Dispersion

There are two types of routing conflicts: on the overlap track segments of trains’ routes and the potential conflicts at turnout nodes beside arrival-departure line. More detailed formulation of each set of constraints is provided as follows.(  1) Conflicts and Dispersion of Trains’ Routes on Track Segments. The conflicts on the overlap track segments of trains’ routes are discussed into the conflicts at left bottleneck, arrival-departure lines, and right bottleneck when trains go through the railway station. Here we build mathematical formulas to illustrate how to mitigate the conflicts.If there is a conflict owing to the delay or interruption, that is, there would be hostile routes of trains, railway operators should take certain measures to ensure trains pass the hostile track segments orderly and efficiently. Figure9 is a schematic diagram of routing conflicts of the same/reverse direction. The conflict occurs at track segment d1~d2 of trains c1 and c2, and track insulation joints b1,b2 and b3. When the same direction conflicts take place (i.e., as shown in Figure 9(a)), if c1 is arranged first, train c2 can enter after the tail of train c1 passing the insulation joint b2 to suit the safety requirement. Similar, when the reverse direction conflict occurs as shown in Figure 9(b), train c2 can enter after the tail of train c1 passes the insulation joint b2 if train c1 is arranged first; train c1 can enter after the tail of train c2 passes the insulation joint b2 if train c2 is arranged first.Figure 9
Conflict resolution when (a) two same direction trains’ routing conflict, where (b) is a conflict of two reverse direction trains’ routes.
(a) (b)In accordance with the progress of the trains, each possible conflict is considered and stated as follows.(i) Routes Conflicts at the Left Bottleneck. As described previously, we first discuss two outbound trains’ routes which have overlapped tracks when arriving at the station from the left bottleneck. It should be formulated as tc2-tc1-tc1c2con≥0, or tc1-tc2-tc2c1con≥0, where tc1c2con is the time from train c1 starting pulling into the station to the tail of it passing through the insulation joint b2, i.e., the time interval of trains to enter the railway station. The value can be obtained by (1). Similarly, tc2c1con is the time from train c2 starting entering to the tail of it passing through the insulation joint b1.Considering the order and relationship between trains and routes which are chosen, the constraints can be expressed as(17)xc1l1ixc2l2iθl1l2tc2-tc1-tc1c2con+M1-δc1,c2≥0,∀c1,c2∈C1,l1,l2∈L,(18)xc1l1ixc2l2iθl1l2tc1-tc2-tc2c1con+Mδc1,c2≥0,∀c1,c2∈C1,l1,l2∈L.In the constraints (17) and (18), δc1,c2 is a binary variable that indicates the trains’ precedence relationship passing through the overlapping tracks. If train c1 precedes train c2, δc1,c2=1. Otherwise, δc1,c2=0.M is a sufficiently large number. Not only the safety time interval but also the routes’ selection relationship are taken into account. So in constraints (17) and (18), if a route l1 is chosen in the left bottleneck by outbound train c1 (xc1l1i=1, else, xc1l1i=0) and a route l2 is occupied by outbound train c2 to enter the station (xc2l2i=1, else, xc2l2i=0) and, in the meantime, there are spatial conflicts between routes l1 and l2 (if there are spatial conflicts between routes, θl1l2=1. Otherwise, θl1l2=0.), then the safe time interval tc1c2con should be held between entrance time of trains c1 and c2.Secondly, the situation for two inbound trains that depart from the station through the left bottleneck is similar. That is, after the front train leaving the station, the latter train can depart from the arrival-departure lines through the left bottleneck after the safe time intervaltc1c2con. tc2fend-tc1fend-tc1c2con≥0 or tc1fend-tc2fend-tc2c1con≥0 must hold which are equivalent to the following constraints: (19)xc1l1ixc2l2iθl1l2tc2fend-tc1fend-tc1c2con+M1-δc1,c2≥0,∀c1,c2∈C2,l1,l2∈L,(20)xc1l1ixc2l2iθl1l2tc1fend-tc2fend-tc2c1con+Mδc1,c2≥0,∀c1,c2∈C2,l1,l2∈L.The occupation ending time on the arrival-departure lines can be calculated by (6) and (12), which is tcfend=tc+tcsetup+tcsr+tcs.Thirdly, for two opposite direction trains, an outbound trainc1 would arrive at the station through the left bottleneck while an inbound train c2 would depart from the arrival-departure lines; then they may cause route conflicts which can be avoided by the following constraints:(21)xc1l1ixc2l2iθl1l2tc2fend-tc1-tc1c2con+M1-δc1,c2≥0,∀c1∈C1,c2∈C2,l1,l2∈L,(22)xc1l1ixc2l2iθl1l2tc1-tc2fend-tc2c1con+Mδc1,c2≥0,∀c1∈C1,c2∈C2,l1,l2∈L.(ii) Routes Conflicts at the Right Bottleneck. Similar to the conflicts in the left bottleneck, the trains routing conflicts for two inbound trains, two outbound trains, and two opposite direction trains should satisfy the following constraints in the right bottleneck.When two inbound trains arrive at the station through the right bottleneck, the route conflicts may occur. Therefore, we set following constraints to avoid collision:(23)xc1r1ixc2r2iθr1r2tc2-tc1-tc1c2con+M1-δc1,c2≥0,∀c1,c2∈C2,r1,r2∈R,(24)xc1r1ixc2r2iθr1r2tc1-tc2-tc2c1con+Mδc1,c2≥0,∀c1,c2∈C2,r1,r2∈R.For two outbound trains which would depart from the station through the right bottleneck(25)xc1r1ixc2r2iθr1r2tc2f-tc1f-tc1c2con+M1-δc1,c2≥0,∀c1,c2∈C1,r1,r2∈R,(26)xc1r1ixc2r2iθr1r2tc1f-tc2f-tc2c1con+Mδc1,c2≥0,∀c1,c2∈C1,r1,r2∈R.For two opposite direction trains, considering the order and relationship between trains and routes which are chosen, the constraint can be(27)xc1r1ixc2r2iθr1r2tc2-tc1fend-tc1c2con+M1-δc1,c2≥0,∀c1∈C1,c2∈C2,r1,r2∈R,(28)xc1r1ixc2r2iθr1r2tc1fend-tc2-tc2c1con+Mδc1,c2≥0,∀c1∈C1,c2∈C2,r1,r2∈R.Among these six constraints, the safe time intervaltc1c2con should be kept. The same with the discussion above, the occupation end time on the arrival-departure lines can be calculated by (6) and (12).(iii) Routes Conflicts on the Arrival-Departure Lines. The train routing conflicts which may occur on the arrival-departure lines has been described in Section 2. Here we propose the algebraic formulas to resolve the conflicts. If the difference of two trains’ departure time is smaller than the headway time Tm1, in other words, if train c1 occupies the arrival-departure line first, train c2 can enter from bottleneck after the end of occupied time at arrival-departure lines of train c1 and after a headway time: tc2f-tcss-tcsd-tc1f+tcsa-Tm1≥0, where tcf=tclend+tcsd+tcss for the outbound trains and for the inbound trains tcf=tcrend+tcsd+tcss which can be calculated according to (9) and (10) described in Section 2. According to Assumption 1, the additional acceleration and deceleration time of trains that run in different speed are same, and the formula is converted to tc2f-tc1f-tc2s-Tm1≥0. Similar, if train c2 enters first, it should be satisfied: tc1f-tc2f-tc1s-Tm1≥0.Thus the constraints should be satisfied as follows:(29)xc1sxc2stc2f-tc1f-tc2s-Tm1+M1-δc1,c2≥0,∀c1,c2∈C,l1,l2∈L,s∈S(30)xc1sxc2stc1f-tc2f-tc1s-Tm1+Mδc1,c2≥0,∀c1,c2∈C,l1,l2∈L,s∈S.The value oftcf can be calculated from (3), (6), (9), and (10).(  2) Potential Conflicts and Avoidance. In small scale stations, there are a small number of arrival-departure lines and platforms that any of them can be occupied by trains. As shown in Figure 5, the outbound train c1 may occupy the arrival-departure line3 to stop when the operation is busy. In this case, it may cause potential conflicts between opposite direction trains if they choose the arrival-departure lines on the same side. Thus measures should be adopted to avoid the two trains arriving the potential conflicting area simultaneously. The trains’ order should be determined by the decision variable δc1,c2. In Figure 5(a), if train c1 arrives at the station through the left bottleneck, train c2 can depart from the arrival-departure line3 after the tail of train c1 passes the potential conflicting area after a safety time interval Tm2 (i.e., the inequality tc2f-tc1lend-Tm2≥0 should be satisfied). Similar, if train c2 leaves the station first, after a safety time interval, train c1 can enter the station through the left bottleneck after the tail of train c2 passes the potential conflicting area (i.e., satisfying tc1-tc2fend-Tm2≥0).To sum up, we use the following formula to avoid potential conflicts:(31)xc1lixc2sγc1c2tc2f-tc1lend-Tm2+M(1-δc1,c2≥0,∀c1∈C1,c2∈C2,l∈L,s∈S,(32)xc1lixc2sγc1c2tc1-tc2fend-Tm2+Mδc1,c2≥0,∀c1∈C1,c2∈C2,l∈L,s∈S.It is suitable for solving the potential conflicts as shown in Figure5(a). Constraints (33) and (34) are used to solve the problems of the situation in Figure 5(b):(33)xc1rixc2sγc1c2tc2-tc1fend-Tm2+M(1-δc1,c2≥0,∀c1∈C1,c2∈C2,r∈R,s∈S,(34)xc1rixc2sγc1c2tc1f-tc2rend-Tm2+Mδc1,c2≥0,∀c1∈C1,c2∈C2,r∈R,s∈S.


#### 3.2.2. The Limited Capacity Restrictions

This constraint set considers the limited infrastructure capacity. Obviously, a train can only utilize one route at bottleneck and arrival-departure lines. To guarantee the safe operation of trains traveling in the railway station, the constraints are listed as follows:(35)∑s∈Sxcs=1∀c∈C,(36)∑l∈Lxcli=1∀c∈C1,(37)∑r∈Rxcro=1∀c∈C1,(38)∑r∈Rxcri=1∀c∈C2,(39)∑l∈Lxclo=1∀c∈C2.Constraint (35) ensures that only one arrival-departure line can be occupied by one train. Constraints (36) and (37) guarantee that each train must utilize one and only one route to traverse the left and right bottleneck for each outbound train, respectively. Similarly, only one route in the right and left bottleneck can be chosen by each inbound train through constraints (38) and (39), respectively.


#### 3.2.3. Connectivity of Train Routing Constraints

Trains’ routing connectivity should be ensured. That is, for an outbound train, the route occupied at the left bottleneck should connect to the arrival-departure line which must connect to the route in the right bottleneck. Otherwise, it is conceivable that the train cannot pass the discontinuous route through the station. Therefore, these restrictions can guarantee the feasibility of trains’ routes.(40)xcs=∑l∈Rslxcli,∀c∈C1,s∈S,l∈L,(41)xcs=∑l∈Rslxclo,∀c∈C2,s∈S,l∈L,(42)xcs=∑r∈Rsrxcri,∀c∈C2,s∈S,r∈R,(43)xcs=∑r∈Rsrxcro,∀c∈C1,s∈S,r∈R,whereRsl and Rsr are sets of left and right bottleneck routes connected to the arrival-departure line s respectively.


#### 3.2.4. Restrictions of Passengers’ Transfer at Station

It represents one of the concerns of railway operators to facilitate passengers transfer to improve the service level. Nowadays, various large scale high-speed rail stations have set up shortcut channels in the railway station to offer convenience for passengers’ transfer in station. This enables passengers to achieve their traveling purpose in a shorter time and cost. There are transfer elevators at each platform in some large and well-equipped facilities stations. And passengers can quickly find the corresponding ticket gate directly through the information from the ticket or the electronic screen.Two trains that may have transfer relationship are discussed in this paper. A constraint is set to keep the two trains stopped at two near platforms to ensure that passengers or crews transfer in a comfortable time:(44)xc1s1xc2s2δs1s2ϑc1c2≥1,∀c1,c2∈C,s1,s2∈S,At the same time, the target train should stop at the platform for a time intervalTm3 to ensure that all passengers complete transfer comfortably, which is required to allow passengers alight from one train, move to the corresponding platform track, and board the other train. So we obtain the following constraints:(45)ϑc1c2xc1s1xc2s2tc2f-tc1f-tc1ss-Tm3+M1-δc1,c2≥0,∀c1,c2∈C,s1,s2∈S,(46)ϑc1c2xc1s1xc2s2tc1f-tc2f-tc2ss-Tm3+Mδc1,c2≥0,∀c1,c2∈C,s1,s2∈S.


#### 3.2.5. Variable Feasible Ranges

The following constraints indicate the feasible ranges of the variables:(47)tc-tc∗≥0,∀c∈C,(48)tc∈Z,∀c∈C,(49)xcs,xcli,xclo,xcri,xcro∈0,1,s∈S,c∈C,l∈L,r∈R,(50)δc1,c2∈0,1,c∈C.Constraint (47) indicates that all trains cannot depart from the station before the planned timetable, where integer decision variable tc indicates the start time measured in minutes to enter the station of train c. Constraints (49) and (50) ensure that those decision variables are 0-1 variables.Herein, the train routing problem for heterogeneous trains can be formulated as the following model, which is essentially a mixed integer nonlinear programming model:(51)minZ=β1z1+β2z2+β3z3,s.t.constraints  (17)–(50).


## 3.1. Objective Function

### 3.1.1. Utilization Balanced of the Arrival-Departure Lines

During railway operations, the challenge is to decrease the overall cost by means of a more efficient use of available resources as mentioned in Giacco et al. [23]. It is worth noting that the route is shortest if train is allotted on the sidings close to main lines. Otherwise, the distance would increase if the train is arranged to stop on others, especially the furthest arrival-departure line from the main line. If the objective is only to minimize the trains’ total travel time, a large number of trains would like to stop at the arrival-departure lines near the main line, while the arrival-departure lines far from the main line are not occupied. If things go on like this it would cause serious wear and tear on the tracks if one arrival-departure line is often occupied repeatedly, which may bring extra costs owing to the frequent maintenance and repaired, the utilization proportionality of the arrival-departure lines should be kept when arranging trains’ routes. The served trains provided by the arrival-departure lines include passing trains and stopping trains. As can be seen, the equilibrium is not only reflected in the number of trains, but also in the train’s travel time that involves dwell time on the arrival-departure lines. It is converted into the mathematical expression and represented by the sum of variances of the number of trains and their dwell times: (13)minz1=1m∑s∈S∑c∈Cxcs-nm2+1m∑s∈S∑c∈Ctcsxcs-∑c∈Ctcsm2.In the objective function (13),m is the number of arrival-departure lines and n is the number of trains (i.e., the number of arrival-departure lines that are occupied). ∑c∈Ctcsxcs denotes the sum of all trains’ travel time on the arrival-departure lines. The first half of the function (13) shows the number of trains’ occupancy balance and the second half means that the trains’ travel time are relatively balanced on the arrival-departure lines.


### 3.1.2. Minimize the Trains’ Total Travel Time

Trains’ travel time on the tracks is another important factor in the optimization of the train routing problem. So the second optimization objective function is minimizing the trains’ total travel time in the station:(14)minz2=∑s∈S∑l∈L∑r∈R∑c∈C1αcxclitcsl+xcstcs+xcrotcsle+∑s∈S∑l∈L∑r∈R∑c∈C2αcxcritcsr+xcstcs+xclotcsle.In (14), the front part indicates the total travel time of outbound trains c∈C1; the last half expresses inbound trains c∈C2 total travel time in the railway station. In order to ensure the satisfaction of passengers, the train reception and departure operations are punctuality and cannot be adjusted drastically. Compared to this, the shunting operations can be adjusted to be relatively flexible.  At the same time, the punctuality requirements are different for different types of trains (passenger trains and freight trains). Therefore, the weight coefficient αc is introduced to indicate the significance of each train.


### 3.1.3. Minimize the Trains’ Total Departure Time Deviations

For railway operators, the punctuality of trains is necessary for the order and efficient operation of the station. Meanwhile, it is also the most concern of passengers. Therefore, the third optimization objective considered in this paper is minimizing the trains’ total deviations between the trains’ starting time to enter the station and the planned timetables of trains pulling in(15)minz3=∑c∈Cαctc-tc∗.In (15), the same αc weight coefficient is quoted. tc is the starting time of train c pulling into the station, and tc∗ represents the planned entering time of trains which can calculate through pregiven timetable.In summary, the linearly weighted compromise approach is adopted to handle the objective functions, and the objective function studied in this paper is(16)minZ=β1z1+β2z2+β3z3.In the objective function (16), βi(i=1,2,3) are the weight coefficients with 0≤βi≤1(i=1,2,3) and meet the equation requirement: β1+β2+β3=1. It is set to distinguish the importance of different objectives. The specific values are given in the cases study.


## 3.1.1. Utilization Balanced of the Arrival-Departure Lines

During railway operations, the challenge is to decrease the overall cost by means of a more efficient use of available resources as mentioned in Giacco et al. [23]. It is worth noting that the route is shortest if train is allotted on the sidings close to main lines. Otherwise, the distance would increase if the train is arranged to stop on others, especially the furthest arrival-departure line from the main line. If the objective is only to minimize the trains’ total travel time, a large number of trains would like to stop at the arrival-departure lines near the main line, while the arrival-departure lines far from the main line are not occupied. If things go on like this it would cause serious wear and tear on the tracks if one arrival-departure line is often occupied repeatedly, which may bring extra costs owing to the frequent maintenance and repaired, the utilization proportionality of the arrival-departure lines should be kept when arranging trains’ routes. The served trains provided by the arrival-departure lines include passing trains and stopping trains. As can be seen, the equilibrium is not only reflected in the number of trains, but also in the train’s travel time that involves dwell time on the arrival-departure lines. It is converted into the mathematical expression and represented by the sum of variances of the number of trains and their dwell times: (13)minz1=1m∑s∈S∑c∈Cxcs-nm2+1m∑s∈S∑c∈Ctcsxcs-∑c∈Ctcsm2.In the objective function (13),m is the number of arrival-departure lines and n is the number of trains (i.e., the number of arrival-departure lines that are occupied). ∑c∈Ctcsxcs denotes the sum of all trains’ travel time on the arrival-departure lines. The first half of the function (13) shows the number of trains’ occupancy balance and the second half means that the trains’ travel time are relatively balanced on the arrival-departure lines.


## 3.1.2. Minimize the Trains’ Total Travel Time

Trains’ travel time on the tracks is another important factor in the optimization of the train routing problem. So the second optimization objective function is minimizing the trains’ total travel time in the station:(14)minz2=∑s∈S∑l∈L∑r∈R∑c∈C1αcxclitcsl+xcstcs+xcrotcsle+∑s∈S∑l∈L∑r∈R∑c∈C2αcxcritcsr+xcstcs+xclotcsle.In (14), the front part indicates the total travel time of outbound trains c∈C1; the last half expresses inbound trains c∈C2 total travel time in the railway station. In order to ensure the satisfaction of passengers, the train reception and departure operations are punctuality and cannot be adjusted drastically. Compared to this, the shunting operations can be adjusted to be relatively flexible.  At the same time, the punctuality requirements are different for different types of trains (passenger trains and freight trains). Therefore, the weight coefficient αc is introduced to indicate the significance of each train.


## 3.1.3. Minimize the Trains’ Total Departure Time Deviations

For railway operators, the punctuality of trains is necessary for the order and efficient operation of the station. Meanwhile, it is also the most concern of passengers. Therefore, the third optimization objective considered in this paper is minimizing the trains’ total deviations between the trains’ starting time to enter the station and the planned timetables of trains pulling in(15)minz3=∑c∈Cαctc-tc∗.In (15), the same αc weight coefficient is quoted. tc is the starting time of train c pulling into the station, and tc∗ represents the planned entering time of trains which can calculate through pregiven timetable.In summary, the linearly weighted compromise approach is adopted to handle the objective functions, and the objective function studied in this paper is(16)minZ=β1z1+β2z2+β3z3.In the objective function (16), βi(i=1,2,3) are the weight coefficients with 0≤βi≤1(i=1,2,3) and meet the equation requirement: β1+β2+β3=1. It is set to distinguish the importance of different objectives. The specific values are given in the cases study.


## 3.2. Constraints

### 3.2.1. Constraints of Conflicts and Dispersion

There are two types of routing conflicts: on the overlap track segments of trains’ routes and the potential conflicts at turnout nodes beside arrival-departure line. More detailed formulation of each set of constraints is provided as follows.(  1) Conflicts and Dispersion of Trains’ Routes on Track Segments. The conflicts on the overlap track segments of trains’ routes are discussed into the conflicts at left bottleneck, arrival-departure lines, and right bottleneck when trains go through the railway station. Here we build mathematical formulas to illustrate how to mitigate the conflicts.If there is a conflict owing to the delay or interruption, that is, there would be hostile routes of trains, railway operators should take certain measures to ensure trains pass the hostile track segments orderly and efficiently. Figure9 is a schematic diagram of routing conflicts of the same/reverse direction. The conflict occurs at track segment d1~d2 of trains c1 and c2, and track insulation joints b1,b2 and b3. When the same direction conflicts take place (i.e., as shown in Figure 9(a)), if c1 is arranged first, train c2 can enter after the tail of train c1 passing the insulation joint b2 to suit the safety requirement. Similar, when the reverse direction conflict occurs as shown in Figure 9(b), train c2 can enter after the tail of train c1 passes the insulation joint b2 if train c1 is arranged first; train c1 can enter after the tail of train c2 passes the insulation joint b2 if train c2 is arranged first.Figure 9
Conflict resolution when (a) two same direction trains’ routing conflict, where (b) is a conflict of two reverse direction trains’ routes.
(a) (b)In accordance with the progress of the trains, each possible conflict is considered and stated as follows.(i) Routes Conflicts at the Left Bottleneck. As described previously, we first discuss two outbound trains’ routes which have overlapped tracks when arriving at the station from the left bottleneck. It should be formulated as tc2-tc1-tc1c2con≥0, or tc1-tc2-tc2c1con≥0, where tc1c2con is the time from train c1 starting pulling into the station to the tail of it passing through the insulation joint b2, i.e., the time interval of trains to enter the railway station. The value can be obtained by (1). Similarly, tc2c1con is the time from train c2 starting entering to the tail of it passing through the insulation joint b1.Considering the order and relationship between trains and routes which are chosen, the constraints can be expressed as(17)xc1l1ixc2l2iθl1l2tc2-tc1-tc1c2con+M1-δc1,c2≥0,∀c1,c2∈C1,l1,l2∈L,(18)xc1l1ixc2l2iθl1l2tc1-tc2-tc2c1con+Mδc1,c2≥0,∀c1,c2∈C1,l1,l2∈L.In the constraints (17) and (18), δc1,c2 is a binary variable that indicates the trains’ precedence relationship passing through the overlapping tracks. If train c1 precedes train c2, δc1,c2=1. Otherwise, δc1,c2=0.M is a sufficiently large number. Not only the safety time interval but also the routes’ selection relationship are taken into account. So in constraints (17) and (18), if a route l1 is chosen in the left bottleneck by outbound train c1 (xc1l1i=1, else, xc1l1i=0) and a route l2 is occupied by outbound train c2 to enter the station (xc2l2i=1, else, xc2l2i=0) and, in the meantime, there are spatial conflicts between routes l1 and l2 (if there are spatial conflicts between routes, θl1l2=1. Otherwise, θl1l2=0.), then the safe time interval tc1c2con should be held between entrance time of trains c1 and c2.Secondly, the situation for two inbound trains that depart from the station through the left bottleneck is similar. That is, after the front train leaving the station, the latter train can depart from the arrival-departure lines through the left bottleneck after the safe time intervaltc1c2con. tc2fend-tc1fend-tc1c2con≥0 or tc1fend-tc2fend-tc2c1con≥0 must hold which are equivalent to the following constraints: (19)xc1l1ixc2l2iθl1l2tc2fend-tc1fend-tc1c2con+M1-δc1,c2≥0,∀c1,c2∈C2,l1,l2∈L,(20)xc1l1ixc2l2iθl1l2tc1fend-tc2fend-tc2c1con+Mδc1,c2≥0,∀c1,c2∈C2,l1,l2∈L.The occupation ending time on the arrival-departure lines can be calculated by (6) and (12), which is tcfend=tc+tcsetup+tcsr+tcs.Thirdly, for two opposite direction trains, an outbound trainc1 would arrive at the station through the left bottleneck while an inbound train c2 would depart from the arrival-departure lines; then they may cause route conflicts which can be avoided by the following constraints:(21)xc1l1ixc2l2iθl1l2tc2fend-tc1-tc1c2con+M1-δc1,c2≥0,∀c1∈C1,c2∈C2,l1,l2∈L,(22)xc1l1ixc2l2iθl1l2tc1-tc2fend-tc2c1con+Mδc1,c2≥0,∀c1∈C1,c2∈C2,l1,l2∈L.(ii) Routes Conflicts at the Right Bottleneck. Similar to the conflicts in the left bottleneck, the trains routing conflicts for two inbound trains, two outbound trains, and two opposite direction trains should satisfy the following constraints in the right bottleneck.When two inbound trains arrive at the station through the right bottleneck, the route conflicts may occur. Therefore, we set following constraints to avoid collision:(23)xc1r1ixc2r2iθr1r2tc2-tc1-tc1c2con+M1-δc1,c2≥0,∀c1,c2∈C2,r1,r2∈R,(24)xc1r1ixc2r2iθr1r2tc1-tc2-tc2c1con+Mδc1,c2≥0,∀c1,c2∈C2,r1,r2∈R.For two outbound trains which would depart from the station through the right bottleneck(25)xc1r1ixc2r2iθr1r2tc2f-tc1f-tc1c2con+M1-δc1,c2≥0,∀c1,c2∈C1,r1,r2∈R,(26)xc1r1ixc2r2iθr1r2tc1f-tc2f-tc2c1con+Mδc1,c2≥0,∀c1,c2∈C1,r1,r2∈R.For two opposite direction trains, considering the order and relationship between trains and routes which are chosen, the constraint can be(27)xc1r1ixc2r2iθr1r2tc2-tc1fend-tc1c2con+M1-δc1,c2≥0,∀c1∈C1,c2∈C2,r1,r2∈R,(28)xc1r1ixc2r2iθr1r2tc1fend-tc2-tc2c1con+Mδc1,c2≥0,∀c1∈C1,c2∈C2,r1,r2∈R.Among these six constraints, the safe time intervaltc1c2con should be kept. The same with the discussion above, the occupation end time on the arrival-departure lines can be calculated by (6) and (12).(iii) Routes Conflicts on the Arrival-Departure Lines. The train routing conflicts which may occur on the arrival-departure lines has been described in Section 2. Here we propose the algebraic formulas to resolve the conflicts. If the difference of two trains’ departure time is smaller than the headway time Tm1, in other words, if train c1 occupies the arrival-departure line first, train c2 can enter from bottleneck after the end of occupied time at arrival-departure lines of train c1 and after a headway time: tc2f-tcss-tcsd-tc1f+tcsa-Tm1≥0, where tcf=tclend+tcsd+tcss for the outbound trains and for the inbound trains tcf=tcrend+tcsd+tcss which can be calculated according to (9) and (10) described in Section 2. According to Assumption 1, the additional acceleration and deceleration time of trains that run in different speed are same, and the formula is converted to tc2f-tc1f-tc2s-Tm1≥0. Similar, if train c2 enters first, it should be satisfied: tc1f-tc2f-tc1s-Tm1≥0.Thus the constraints should be satisfied as follows:(29)xc1sxc2stc2f-tc1f-tc2s-Tm1+M1-δc1,c2≥0,∀c1,c2∈C,l1,l2∈L,s∈S(30)xc1sxc2stc1f-tc2f-tc1s-Tm1+Mδc1,c2≥0,∀c1,c2∈C,l1,l2∈L,s∈S.The value oftcf can be calculated from (3), (6), (9), and (10).(  2) Potential Conflicts and Avoidance. In small scale stations, there are a small number of arrival-departure lines and platforms that any of them can be occupied by trains. As shown in Figure 5, the outbound train c1 may occupy the arrival-departure line3 to stop when the operation is busy. In this case, it may cause potential conflicts between opposite direction trains if they choose the arrival-departure lines on the same side. Thus measures should be adopted to avoid the two trains arriving the potential conflicting area simultaneously. The trains’ order should be determined by the decision variable δc1,c2. In Figure 5(a), if train c1 arrives at the station through the left bottleneck, train c2 can depart from the arrival-departure line3 after the tail of train c1 passes the potential conflicting area after a safety time interval Tm2 (i.e., the inequality tc2f-tc1lend-Tm2≥0 should be satisfied). Similar, if train c2 leaves the station first, after a safety time interval, train c1 can enter the station through the left bottleneck after the tail of train c2 passes the potential conflicting area (i.e., satisfying tc1-tc2fend-Tm2≥0).To sum up, we use the following formula to avoid potential conflicts:(31)xc1lixc2sγc1c2tc2f-tc1lend-Tm2+M(1-δc1,c2≥0,∀c1∈C1,c2∈C2,l∈L,s∈S,(32)xc1lixc2sγc1c2tc1-tc2fend-Tm2+Mδc1,c2≥0,∀c1∈C1,c2∈C2,l∈L,s∈S.It is suitable for solving the potential conflicts as shown in Figure5(a). Constraints (33) and (34) are used to solve the problems of the situation in Figure 5(b):(33)xc1rixc2sγc1c2tc2-tc1fend-Tm2+M(1-δc1,c2≥0,∀c1∈C1,c2∈C2,r∈R,s∈S,(34)xc1rixc2sγc1c2tc1f-tc2rend-Tm2+Mδc1,c2≥0,∀c1∈C1,c2∈C2,r∈R,s∈S.


### 3.2.2. The Limited Capacity Restrictions

This constraint set considers the limited infrastructure capacity. Obviously, a train can only utilize one route at bottleneck and arrival-departure lines. To guarantee the safe operation of trains traveling in the railway station, the constraints are listed as follows:(35)∑s∈Sxcs=1∀c∈C,(36)∑l∈Lxcli=1∀c∈C1,(37)∑r∈Rxcro=1∀c∈C1,(38)∑r∈Rxcri=1∀c∈C2,(39)∑l∈Lxclo=1∀c∈C2.Constraint (35) ensures that only one arrival-departure line can be occupied by one train. Constraints (36) and (37) guarantee that each train must utilize one and only one route to traverse the left and right bottleneck for each outbound train, respectively. Similarly, only one route in the right and left bottleneck can be chosen by each inbound train through constraints (38) and (39), respectively.


### 3.2.3. Connectivity of Train Routing Constraints

Trains’ routing connectivity should be ensured. That is, for an outbound train, the route occupied at the left bottleneck should connect to the arrival-departure line which must connect to the route in the right bottleneck. Otherwise, it is conceivable that the train cannot pass the discontinuous route through the station. Therefore, these restrictions can guarantee the feasibility of trains’ routes.(40)xcs=∑l∈Rslxcli,∀c∈C1,s∈S,l∈L,(41)xcs=∑l∈Rslxclo,∀c∈C2,s∈S,l∈L,(42)xcs=∑r∈Rsrxcri,∀c∈C2,s∈S,r∈R,(43)xcs=∑r∈Rsrxcro,∀c∈C1,s∈S,r∈R,whereRsl and Rsr are sets of left and right bottleneck routes connected to the arrival-departure line s respectively.


### 3.2.4. Restrictions of Passengers’ Transfer at Station

It represents one of the concerns of railway operators to facilitate passengers transfer to improve the service level. Nowadays, various large scale high-speed rail stations have set up shortcut channels in the railway station to offer convenience for passengers’ transfer in station. This enables passengers to achieve their traveling purpose in a shorter time and cost. There are transfer elevators at each platform in some large and well-equipped facilities stations. And passengers can quickly find the corresponding ticket gate directly through the information from the ticket or the electronic screen.Two trains that may have transfer relationship are discussed in this paper. A constraint is set to keep the two trains stopped at two near platforms to ensure that passengers or crews transfer in a comfortable time:(44)xc1s1xc2s2δs1s2ϑc1c2≥1,∀c1,c2∈C,s1,s2∈S,At the same time, the target train should stop at the platform for a time intervalTm3 to ensure that all passengers complete transfer comfortably, which is required to allow passengers alight from one train, move to the corresponding platform track, and board the other train. So we obtain the following constraints:(45)ϑc1c2xc1s1xc2s2tc2f-tc1f-tc1ss-Tm3+M1-δc1,c2≥0,∀c1,c2∈C,s1,s2∈S,(46)ϑc1c2xc1s1xc2s2tc1f-tc2f-tc2ss-Tm3+Mδc1,c2≥0,∀c1,c2∈C,s1,s2∈S.


### 3.2.5. Variable Feasible Ranges

The following constraints indicate the feasible ranges of the variables:(47)tc-tc∗≥0,∀c∈C,(48)tc∈Z,∀c∈C,(49)xcs,xcli,xclo,xcri,xcro∈0,1,s∈S,c∈C,l∈L,r∈R,(50)δc1,c2∈0,1,c∈C.Constraint (47) indicates that all trains cannot depart from the station before the planned timetable, where integer decision variable tc indicates the start time measured in minutes to enter the station of train c. Constraints (49) and (50) ensure that those decision variables are 0-1 variables.Herein, the train routing problem for heterogeneous trains can be formulated as the following model, which is essentially a mixed integer nonlinear programming model:(51)minZ=β1z1+β2z2+β3z3,s.t.constraints  (17)–(50).


## 3.2.1. Constraints of Conflicts and Dispersion

There are two types of routing conflicts: on the overlap track segments of trains’ routes and the potential conflicts at turnout nodes beside arrival-departure line. More detailed formulation of each set of constraints is provided as follows.(  1) Conflicts and Dispersion of Trains’ Routes on Track Segments. The conflicts on the overlap track segments of trains’ routes are discussed into the conflicts at left bottleneck, arrival-departure lines, and right bottleneck when trains go through the railway station. Here we build mathematical formulas to illustrate how to mitigate the conflicts.If there is a conflict owing to the delay or interruption, that is, there would be hostile routes of trains, railway operators should take certain measures to ensure trains pass the hostile track segments orderly and efficiently. Figure9 is a schematic diagram of routing conflicts of the same/reverse direction. The conflict occurs at track segment d1~d2 of trains c1 and c2, and track insulation joints b1,b2 and b3. When the same direction conflicts take place (i.e., as shown in Figure 9(a)), if c1 is arranged first, train c2 can enter after the tail of train c1 passing the insulation joint b2 to suit the safety requirement. Similar, when the reverse direction conflict occurs as shown in Figure 9(b), train c2 can enter after the tail of train c1 passes the insulation joint b2 if train c1 is arranged first; train c1 can enter after the tail of train c2 passes the insulation joint b2 if train c2 is arranged first.Figure 9
Conflict resolution when (a) two same direction trains’ routing conflict, where (b) is a conflict of two reverse direction trains’ routes.
(a) (b)In accordance with the progress of the trains, each possible conflict is considered and stated as follows.(i) Routes Conflicts at the Left Bottleneck. As described previously, we first discuss two outbound trains’ routes which have overlapped tracks when arriving at the station from the left bottleneck. It should be formulated as tc2-tc1-tc1c2con≥0, or tc1-tc2-tc2c1con≥0, where tc1c2con is the time from train c1 starting pulling into the station to the tail of it passing through the insulation joint b2, i.e., the time interval of trains to enter the railway station. The value can be obtained by (1). Similarly, tc2c1con is the time from train c2 starting entering to the tail of it passing through the insulation joint b1.Considering the order and relationship between trains and routes which are chosen, the constraints can be expressed as(17)xc1l1ixc2l2iθl1l2tc2-tc1-tc1c2con+M1-δc1,c2≥0,∀c1,c2∈C1,l1,l2∈L,(18)xc1l1ixc2l2iθl1l2tc1-tc2-tc2c1con+Mδc1,c2≥0,∀c1,c2∈C1,l1,l2∈L.In the constraints (17) and (18), δc1,c2 is a binary variable that indicates the trains’ precedence relationship passing through the overlapping tracks. If train c1 precedes train c2, δc1,c2=1. Otherwise, δc1,c2=0.M is a sufficiently large number. Not only the safety time interval but also the routes’ selection relationship are taken into account. So in constraints (17) and (18), if a route l1 is chosen in the left bottleneck by outbound train c1 (xc1l1i=1, else, xc1l1i=0) and a route l2 is occupied by outbound train c2 to enter the station (xc2l2i=1, else, xc2l2i=0) and, in the meantime, there are spatial conflicts between routes l1 and l2 (if there are spatial conflicts between routes, θl1l2=1. Otherwise, θl1l2=0.), then the safe time interval tc1c2con should be held between entrance time of trains c1 and c2.Secondly, the situation for two inbound trains that depart from the station through the left bottleneck is similar. That is, after the front train leaving the station, the latter train can depart from the arrival-departure lines through the left bottleneck after the safe time intervaltc1c2con. tc2fend-tc1fend-tc1c2con≥0 or tc1fend-tc2fend-tc2c1con≥0 must hold which are equivalent to the following constraints: (19)xc1l1ixc2l2iθl1l2tc2fend-tc1fend-tc1c2con+M1-δc1,c2≥0,∀c1,c2∈C2,l1,l2∈L,(20)xc1l1ixc2l2iθl1l2tc1fend-tc2fend-tc2c1con+Mδc1,c2≥0,∀c1,c2∈C2,l1,l2∈L.The occupation ending time on the arrival-departure lines can be calculated by (6) and (12), which is tcfend=tc+tcsetup+tcsr+tcs.Thirdly, for two opposite direction trains, an outbound trainc1 would arrive at the station through the left bottleneck while an inbound train c2 would depart from the arrival-departure lines; then they may cause route conflicts which can be avoided by the following constraints:(21)xc1l1ixc2l2iθl1l2tc2fend-tc1-tc1c2con+M1-δc1,c2≥0,∀c1∈C1,c2∈C2,l1,l2∈L,(22)xc1l1ixc2l2iθl1l2tc1-tc2fend-tc2c1con+Mδc1,c2≥0,∀c1∈C1,c2∈C2,l1,l2∈L.(ii) Routes Conflicts at the Right Bottleneck. Similar to the conflicts in the left bottleneck, the trains routing conflicts for two inbound trains, two outbound trains, and two opposite direction trains should satisfy the following constraints in the right bottleneck.When two inbound trains arrive at the station through the right bottleneck, the route conflicts may occur. Therefore, we set following constraints to avoid collision:(23)xc1r1ixc2r2iθr1r2tc2-tc1-tc1c2con+M1-δc1,c2≥0,∀c1,c2∈C2,r1,r2∈R,(24)xc1r1ixc2r2iθr1r2tc1-tc2-tc2c1con+Mδc1,c2≥0,∀c1,c2∈C2,r1,r2∈R.For two outbound trains which would depart from the station through the right bottleneck(25)xc1r1ixc2r2iθr1r2tc2f-tc1f-tc1c2con+M1-δc1,c2≥0,∀c1,c2∈C1,r1,r2∈R,(26)xc1r1ixc2r2iθr1r2tc1f-tc2f-tc2c1con+Mδc1,c2≥0,∀c1,c2∈C1,r1,r2∈R.For two opposite direction trains, considering the order and relationship between trains and routes which are chosen, the constraint can be(27)xc1r1ixc2r2iθr1r2tc2-tc1fend-tc1c2con+M1-δc1,c2≥0,∀c1∈C1,c2∈C2,r1,r2∈R,(28)xc1r1ixc2r2iθr1r2tc1fend-tc2-tc2c1con+Mδc1,c2≥0,∀c1∈C1,c2∈C2,r1,r2∈R.Among these six constraints, the safe time intervaltc1c2con should be kept. The same with the discussion above, the occupation end time on the arrival-departure lines can be calculated by (6) and (12).(iii) Routes Conflicts on the Arrival-Departure Lines. The train routing conflicts which may occur on the arrival-departure lines has been described in Section 2. Here we propose the algebraic formulas to resolve the conflicts. If the difference of two trains’ departure time is smaller than the headway time Tm1, in other words, if train c1 occupies the arrival-departure line first, train c2 can enter from bottleneck after the end of occupied time at arrival-departure lines of train c1 and after a headway time: tc2f-tcss-tcsd-tc1f+tcsa-Tm1≥0, where tcf=tclend+tcsd+tcss for the outbound trains and for the inbound trains tcf=tcrend+tcsd+tcss which can be calculated according to (9) and (10) described in Section 2. According to Assumption 1, the additional acceleration and deceleration time of trains that run in different speed are same, and the formula is converted to tc2f-tc1f-tc2s-Tm1≥0. Similar, if train c2 enters first, it should be satisfied: tc1f-tc2f-tc1s-Tm1≥0.Thus the constraints should be satisfied as follows:(29)xc1sxc2stc2f-tc1f-tc2s-Tm1+M1-δc1,c2≥0,∀c1,c2∈C,l1,l2∈L,s∈S(30)xc1sxc2stc1f-tc2f-tc1s-Tm1+Mδc1,c2≥0,∀c1,c2∈C,l1,l2∈L,s∈S.The value oftcf can be calculated from (3), (6), (9), and (10).(  2) Potential Conflicts and Avoidance. In small scale stations, there are a small number of arrival-departure lines and platforms that any of them can be occupied by trains. As shown in Figure 5, the outbound train c1 may occupy the arrival-departure line3 to stop when the operation is busy. In this case, it may cause potential conflicts between opposite direction trains if they choose the arrival-departure lines on the same side. Thus measures should be adopted to avoid the two trains arriving the potential conflicting area simultaneously. The trains’ order should be determined by the decision variable δc1,c2. In Figure 5(a), if train c1 arrives at the station through the left bottleneck, train c2 can depart from the arrival-departure line3 after the tail of train c1 passes the potential conflicting area after a safety time interval Tm2 (i.e., the inequality tc2f-tc1lend-Tm2≥0 should be satisfied). Similar, if train c2 leaves the station first, after a safety time interval, train c1 can enter the station through the left bottleneck after the tail of train c2 passes the potential conflicting area (i.e., satisfying tc1-tc2fend-Tm2≥0).To sum up, we use the following formula to avoid potential conflicts:(31)xc1lixc2sγc1c2tc2f-tc1lend-Tm2+M(1-δc1,c2≥0,∀c1∈C1,c2∈C2,l∈L,s∈S,(32)xc1lixc2sγc1c2tc1-tc2fend-Tm2+Mδc1,c2≥0,∀c1∈C1,c2∈C2,l∈L,s∈S.It is suitable for solving the potential conflicts as shown in Figure5(a). Constraints (33) and (34) are used to solve the problems of the situation in Figure 5(b):(33)xc1rixc2sγc1c2tc2-tc1fend-Tm2+M(1-δc1,c2≥0,∀c1∈C1,c2∈C2,r∈R,s∈S,(34)xc1rixc2sγc1c2tc1f-tc2rend-Tm2+Mδc1,c2≥0,∀c1∈C1,c2∈C2,r∈R,s∈S.


## 3.2.2. The Limited Capacity Restrictions

This constraint set considers the limited infrastructure capacity. Obviously, a train can only utilize one route at bottleneck and arrival-departure lines. To guarantee the safe operation of trains traveling in the railway station, the constraints are listed as follows:(35)∑s∈Sxcs=1∀c∈C,(36)∑l∈Lxcli=1∀c∈C1,(37)∑r∈Rxcro=1∀c∈C1,(38)∑r∈Rxcri=1∀c∈C2,(39)∑l∈Lxclo=1∀c∈C2.Constraint (35) ensures that only one arrival-departure line can be occupied by one train. Constraints (36) and (37) guarantee that each train must utilize one and only one route to traverse the left and right bottleneck for each outbound train, respectively. Similarly, only one route in the right and left bottleneck can be chosen by each inbound train through constraints (38) and (39), respectively.


## 3.2.3. Connectivity of Train Routing Constraints

Trains’ routing connectivity should be ensured. That is, for an outbound train, the route occupied at the left bottleneck should connect to the arrival-departure line which must connect to the route in the right bottleneck. Otherwise, it is conceivable that the train cannot pass the discontinuous route through the station. Therefore, these restrictions can guarantee the feasibility of trains’ routes.(40)xcs=∑l∈Rslxcli,∀c∈C1,s∈S,l∈L,(41)xcs=∑l∈Rslxclo,∀c∈C2,s∈S,l∈L,(42)xcs=∑r∈Rsrxcri,∀c∈C2,s∈S,r∈R,(43)xcs=∑r∈Rsrxcro,∀c∈C1,s∈S,r∈R,whereRsl and Rsr are sets of left and right bottleneck routes connected to the arrival-departure line s respectively.


## 3.2.4. Restrictions of Passengers’ Transfer at Station

It represents one of the concerns of railway operators to facilitate passengers transfer to improve the service level. Nowadays, various large scale high-speed rail stations have set up shortcut channels in the railway station to offer convenience for passengers’ transfer in station. This enables passengers to achieve their traveling purpose in a shorter time and cost. There are transfer elevators at each platform in some large and well-equipped facilities stations. And passengers can quickly find the corresponding ticket gate directly through the information from the ticket or the electronic screen.Two trains that may have transfer relationship are discussed in this paper. A constraint is set to keep the two trains stopped at two near platforms to ensure that passengers or crews transfer in a comfortable time:(44)xc1s1xc2s2δs1s2ϑc1c2≥1,∀c1,c2∈C,s1,s2∈S,At the same time, the target train should stop at the platform for a time intervalTm3 to ensure that all passengers complete transfer comfortably, which is required to allow passengers alight from one train, move to the corresponding platform track, and board the other train. So we obtain the following constraints:(45)ϑc1c2xc1s1xc2s2tc2f-tc1f-tc1ss-Tm3+M1-δc1,c2≥0,∀c1,c2∈C,s1,s2∈S,(46)ϑc1c2xc1s1xc2s2tc1f-tc2f-tc2ss-Tm3+Mδc1,c2≥0,∀c1,c2∈C,s1,s2∈S.


## 3.2.5. Variable Feasible Ranges

The following constraints indicate the feasible ranges of the variables:(47)tc-tc∗≥0,∀c∈C,(48)tc∈Z,∀c∈C,(49)xcs,xcli,xclo,xcri,xcro∈0,1,s∈S,c∈C,l∈L,r∈R,(50)δc1,c2∈0,1,c∈C.Constraint (47) indicates that all trains cannot depart from the station before the planned timetable, where integer decision variable tc indicates the start time measured in minutes to enter the station of train c. Constraints (49) and (50) ensure that those decision variables are 0-1 variables.Herein, the train routing problem for heterogeneous trains can be formulated as the following model, which is essentially a mixed integer nonlinear programming model:(51)minZ=β1z1+β2z2+β3z3,s.t.constraints  (17)–(50).


## 4. Solution Methodology Based on Tabu Search

The number of decision variables of the model will increase greatly as the increasing number of optional routes of trains which is NP-hard problem mentioned in Ahuja et al. [18] and Carey et al. [19]. In the proposed model, the situation scale of the values of variables x is huge as the number of them is great. For instance, when C=c1,c2 and L=l1,l2,l3, there are 26 kinds of values of x=[xc1l1i,xc1l2i,xc1l3i,xc2l1i,xc2l2i,xc2l3i], where each element of x may take 0 or 1. It would cost a significant amount of time to solve the problem under a larger case and may not even get the optimal solution in a reasonable computation time. Apart from this, the mathematic model is nonlinear and there is no algorithm which can solve such problems accurately at present. Therefore in this section, we design a tabu search algorithm stepwise to obtain the near-optimal solution based on the nonlinear characteristic of the model for the TRP with a large scale railway station.The tabu search algorithm is a deterministic meta-heuristic on account of local search [24], which makes extensive use of memory for guiding the search. From the incumbent solution, non-tabu moves define a set of solutions which called the neighborhood of the incumbent solution. The best solution is selected as the new incumbent solution at each step and stored in the tabu list to avoid being trapped in local optima and re-visiting the same solutions. When the number of solutions achieves the length of the tabu list, the earliest one which entered the list is released. The algorithm stops until reaching the termination conditions.In our model, we notice that constraints (17)-(34) and constraints (45) and (46) are nonlinear. It is obvious that if the variable x is determined, the model (51) would become an integer linear programming model that determines the departure time of each train. For such mathematical programming model, there are already mature algorithms, such as branch and bound and cutting plane, etc. Taking constraints (17) and (18) as an example, the decision variables xc1l1i and xc2l2i are binary variables, and θl1l2 is known binary parameters according to wether there are conflicts between routes l1 and l2. There are two cases due to the value of decision variables. The first is that the value of any variables or parameter is 0 among the decision variables xc1l1i, xc2l2i and parameter θl1l2. Then the left side of the formula is 0, and the constraint is effective apparently. The second case is that the values of them are 1, then the constraints were satisfied if the formulas are satisfied inside the brackets. Hence the inequality constraints are obviously satisfied in the first case. And in the second case, the constraints turn into an integer linear constraints, not only for constraints (17) and (18), but for other constraints in the model (51). As a result, we set the decision variable x as the tabu object. Based on that, through generating neighborhood of incumbent solution and searching a good solution at each step, we can gradually approach the near-optimal solution.To deal with the problems mentioned above in the model presented in this paper, we discuss the setting of the neighborhood of incumbent solution, the selection of initial solution, and the scheme of algorithm in detail below.


### 4.1. Neighborhood of Incumbent Solution

The establishment of incumbent solution neighborhood is crucial for a better direction of the search, which affects the quality of solution at each step. In our model, we hope that trains would have the shortest travel time, which performances the shortest routes. As mentioned, the travel distance would increase if trains are arranged on the sidings far from the main line. In our problem, we need to determine a good quality initial solution and tabu move to reach the near-optimal solution. Therefore we generate two different neighborhoods of the incumbent solution, respectively:Ninitial: based on the incumbent routing set, which contains routes in bottleneck and arrival-departure line, the two adjacent sidings and corresponding routes in bottleneck are accommodated into it. That is, the neighborhood contains not only the incumbent arrival-departure lines of trains and corresponding routes in left and right bottleneck, but also the two adjacent sidings and corresponding routes in the bottleneck.Ntabu: the neighborhood of incumbent routing set for tabu move contains Ninitial, which involves four adjacent siding and corresponding routes in bottleneck. Besides, remove the situation that trains with close departure times and occupy the same sidings.In general,Ninitial is used to determine a good quality initial solution, whose scale is smaller. And we need to search the solution roughly in a short time. In contrast to this, Ntabu is a wide neighborhood in order to avoid empty neighborhoods as far as possible while avoiding to search in all possible situations. It is thus worthwhile distinguishing the different neighborhood structures.


### 4.2. Determined of Initial Solution

As describe above, the quality of initial solution is crucial for the performance of tabu search. A good initial feasible solution can greatly improve the speed of searching for the optimal solution. If we randomly assign a set of routes as the incumbent solution, it would take a lot of time to search, and the quality of the near-optimal solution cannot be guaranteed. The objective value is much smaller obviously than the previous strategy if starting from a good incumbent solution. So in this paper, we can get a feasible solution of train routing set through our prior knowledge of trains’ character and construction of the railway station which is just a preliminary program. In view of this, the corresponding routing set solution is selected which satisfies constraints and at the same time reaches the minimum objective function in the solution neighborhoods at next step. Then regard this solution as a new incumbent solution. By cycling this step until the iterative termination condition is satisfied, a batter initial solution of the tabu search algorithm is determined. The procedure is summarized in Table3.Table 3
The scheme of determining initial solution.
Step  1. Input initial information, including trains’ character, railway station parameters, train speed profiles, trains with transfer relationship, planned timetable, etc., set i=0. Step  2.Choose a feasible routes set as incumbent solution xinc=xf through prior knowledge of trains and parameters of the railway station, get objective value sxinc. Step  3. Generate neighborhood Ninitial(xinc) of xinc, and corresponding neighborhood solution: SNinitial(xinc). Step  4.Search the best solution sx∗ in SNinitial(xinc) and corresponding routing set x∗ Step  5. If the objective value of sx∗is better than that of sxinc, sxinc=sx∗, xinc=x∗; otherwise, let xinc as current solution continuously. Step  6. If the value of xinc does not change, i+=1; otherwise, go to step 7. Step  7. If i==1, output sxinc and the corresponding routing set xinc, stop. Else, go to step 3.


### 4.3. The Algorithm Scheme

In this paper, we first obtain the initial routes based on method describe in Table3. Then we generate the neighborhood Ntabu of the incumbent solution to reduce the range of the search. And we solve the corresponding MLP in the Ntabu to choose the best solution. Finally, the best solution is chosen as the new incumbent solution and stored in the tabu list. The steps shown in Table 3 are repeated in sequence recursively. We summarize the procedure of this heuristic algorithm in Table 4.Table 4
Pseudocode of the tabu search algorithm.
Input: xinc as an initial solution, parameter θr1r2,tc1c2con,tc2c1con, etc T L = ∅ assign the incumbent solution:xnow=xinc while the frequency of one solution is not reached: generate neighborhoodNtabu(xnow) updateNtabu(xnow) by removing duplicate and solutions that do not satisfy constraints for i in Ntabuxnow: get solutions: S(i) satisfied the constraints in the mathematical model S N t a b u ( x n o w ).append(S(i)) which is neighborhood solution get the decision variabletc and δc1,c2 correspondingly choose the non-tabu optimal solutionsx′ in SNtabuxnow search the corresponding routing set:x′ x n o w = x ′ T L . a p p e n d ( x n o w ) if len(TL)>5: delTL[0] if the number of iterations is an integer multiple of 5: if exist a solution xasp satisfy aspiration criterion: x n o w = x a s p t a b u l i s t . a p p e n d ( x n o w ) if len(TL)>5: delTL[0] Output: optimal solution: xnow, tc and δc1,c2In this case the tabu list contains the situation of all trains’ routes. The aspiration criterion is set to reinforce the local search to avoid losing an admirable state. That is, if a solution in the tabu list is largely superior to others, then reconsider and search it as a new incumbent solution. The other solutions are forbidden in the tabu list to avoid being trapped in local optima or infinite loops.


## 4.1. Neighborhood of Incumbent Solution

The establishment of incumbent solution neighborhood is crucial for a better direction of the search, which affects the quality of solution at each step. In our model, we hope that trains would have the shortest travel time, which performances the shortest routes. As mentioned, the travel distance would increase if trains are arranged on the sidings far from the main line. In our problem, we need to determine a good quality initial solution and tabu move to reach the near-optimal solution. Therefore we generate two different neighborhoods of the incumbent solution, respectively:Ninitial: based on the incumbent routing set, which contains routes in bottleneck and arrival-departure line, the two adjacent sidings and corresponding routes in bottleneck are accommodated into it. That is, the neighborhood contains not only the incumbent arrival-departure lines of trains and corresponding routes in left and right bottleneck, but also the two adjacent sidings and corresponding routes in the bottleneck.Ntabu: the neighborhood of incumbent routing set for tabu move contains Ninitial, which involves four adjacent siding and corresponding routes in bottleneck. Besides, remove the situation that trains with close departure times and occupy the same sidings.In general,Ninitial is used to determine a good quality initial solution, whose scale is smaller. And we need to search the solution roughly in a short time. In contrast to this, Ntabu is a wide neighborhood in order to avoid empty neighborhoods as far as possible while avoiding to search in all possible situations. It is thus worthwhile distinguishing the different neighborhood structures.


## 4.2. Determined of Initial Solution

As describe above, the quality of initial solution is crucial for the performance of tabu search. A good initial feasible solution can greatly improve the speed of searching for the optimal solution. If we randomly assign a set of routes as the incumbent solution, it would take a lot of time to search, and the quality of the near-optimal solution cannot be guaranteed. The objective value is much smaller obviously than the previous strategy if starting from a good incumbent solution. So in this paper, we can get a feasible solution of train routing set through our prior knowledge of trains’ character and construction of the railway station which is just a preliminary program. In view of this, the corresponding routing set solution is selected which satisfies constraints and at the same time reaches the minimum objective function in the solution neighborhoods at next step. Then regard this solution as a new incumbent solution. By cycling this step until the iterative termination condition is satisfied, a batter initial solution of the tabu search algorithm is determined. The procedure is summarized in Table3.Table 3
The scheme of determining initial solution.
Step  1. Input initial information, including trains’ character, railway station parameters, train speed profiles, trains with transfer relationship, planned timetable, etc., set i=0. Step  2.Choose a feasible routes set as incumbent solution xinc=xf through prior knowledge of trains and parameters of the railway station, get objective value sxinc. Step  3. Generate neighborhood Ninitial(xinc) of xinc, and corresponding neighborhood solution: SNinitial(xinc). Step  4.Search the best solution sx∗ in SNinitial(xinc) and corresponding routing set x∗ Step  5. If the objective value of sx∗is better than that of sxinc, sxinc=sx∗, xinc=x∗; otherwise, let xinc as current solution continuously. Step  6. If the value of xinc does not change, i+=1; otherwise, go to step 7. Step  7. If i==1, output sxinc and the corresponding routing set xinc, stop. Else, go to step 3.


## 4.3. The Algorithm Scheme

In this paper, we first obtain the initial routes based on method describe in Table3. Then we generate the neighborhood Ntabu of the incumbent solution to reduce the range of the search. And we solve the corresponding MLP in the Ntabu to choose the best solution. Finally, the best solution is chosen as the new incumbent solution and stored in the tabu list. The steps shown in Table 3 are repeated in sequence recursively. We summarize the procedure of this heuristic algorithm in Table 4.Table 4
Pseudocode of the tabu search algorithm.
Input: xinc as an initial solution, parameter θr1r2,tc1c2con,tc2c1con, etc T L = ∅ assign the incumbent solution:xnow=xinc while the frequency of one solution is not reached: generate neighborhoodNtabu(xnow) updateNtabu(xnow) by removing duplicate and solutions that do not satisfy constraints for i in Ntabuxnow: get solutions: S(i) satisfied the constraints in the mathematical model S N t a b u ( x n o w ).append(S(i)) which is neighborhood solution get the decision variabletc and δc1,c2 correspondingly choose the non-tabu optimal solutionsx′ in SNtabuxnow search the corresponding routing set:x′ x n o w = x ′ T L . a p p e n d ( x n o w ) if len(TL)>5: delTL[0] if the number of iterations is an integer multiple of 5: if exist a solution xasp satisfy aspiration criterion: x n o w = x a s p t a b u l i s t . a p p e n d ( x n o w ) if len(TL)>5: delTL[0] Output: optimal solution: xnow, tc and δc1,c2In this case the tabu list contains the situation of all trains’ routes. The aspiration criterion is set to reinforce the local search to avoid losing an admirable state. That is, if a solution in the tabu list is largely superior to others, then reconsider and search it as a new incumbent solution. The other solutions are forbidden in the tabu list to avoid being trapped in local optima or infinite loops.


## 5. Numerical Experiments

In this section, two sets of numerical experiments are implemented to show the performance of our proposed model. Specifically, for the models formulated, a small case is implemented to demonstrate the application and performance, in which CPLEX solver is used to obtain exact optimal solution which compares with the near-optimal solution obtained by the proposed heuristic algorithm based on the tabu search, while in large scale case experiment, we apply the proposed heuristic algorithm to the Jinan West high-speed railway station, in which a tabu search algorithm is designed in PYTHON 2.7.13 to obtain the near-optimal solutions of trains routing on a Windows 10 platform with Intel(R) Core(TM) i7-8550U CPU and 8G RAM.


### 5.1. A Small-Scale Case Study

In this case, we consider a two mainI andII lines railway station as shown in Figure 10 which is outbound and inbound direction, respectively. In the left bottleneck, there are a reception line z1 of outbound trains, a departure line z2 of inbound trains, and a locomotive waiting track j1. At the same time, there are 6 arrival-departure lines, of which arrival-departure linesII, 3 and 4 next to a platform. In the right bottleneck, there are 4 lines including a departure line g1 of outbound trains, a reception line g2 of inbound trains. and two locomotive waiting tracks j2 and j3. The distances between connection points in this railway station are shown in Table 5.Table 5
Distances between points in the railway network in Figure10.
Node:di Node:di Distance(m) Node:di Node:di Distance(m) Node:di Node:di Distance(m) 1 2 90 9 11 60 22 28 85 1 9 305 10 12 80 23 28 90 2 4 60 11 16 85 24 25 90 3 5 48 11 17 90 25 34 300 3 6 60 12 18 750 25 26 60 4 5 60 13 19 750 26 29 100 4 6 48 14 20 750 27 30 148 5 8 175 15 21 750 28 27 60 6 7 100 16 22 750 29 31 60 7 14 170 17 23 750 29 32 90 7 9 90 18 24 80 30 31 90 8 10 90 19 25 125 30 32 60 8 13 125 20 26 170 31 33 50 9 15 125 21 27 125 33 34 60Figure 10
The structure of a small-scale station.In order to test the effectiveness of the proposed models and solution algorithms, we derive a set of instances in this small-scale rail station with different numbers of trains (the type of trains is exhaustive to demonstrate the versatility and correctness of the model). Table6 shows the origin and destination of each train, as well as the characteristic parameters of them. Trains c1 and c4 are outbound trains, while c3 is inbound train. At the same time, there is a transfer relationship between c1 and c3. Trains c2 and c5 are shunting operations, wherein c2 travels from the locomotive waiting tracks j2 to j1 and c5 travels from j1 to be an originating train (i.e., train c5 would choose an arrival-departure line to stop and then depart from the station through the departure node g1). In order to distinguish the importance of operations, the higher punctuality required for train reception, and departure operations compared to the shunting operations, we set the weights to 0.9 and 0.1, respectively. As for the multiobjective of our model, we attach the most importance to the punctuality, then the total travel time and utilization balanced of the arrival-departure lines are considered evenly. Thus set the parameters β1=β2=0.3 and β3=0.4. In addition to this, the preparation time of each train is 1 min, and the additional time that provides trains’ acceleration and deceleration is 2 min and 1 min, respectively.Table 6
The parameters of trains in the small case.
Train Origin Destination Average velocity (km/h) Operations Planned timetable Stop time (min) c 1 z 1 g 1 30 Passing 11:25 17 c 2 j 2 j 1 15 Shunting 11:28 0 c 3 g 2 z 2 30 Passing 11:30 10 c 4 z 1 g 1 30 Passing 11:34 6 c 5 j 1 g 1 15 Shunting 11:37 30We assume the headway timeTm1=2min, the minimum time interval of potential area of two trains Tm2=1min, and the minimum transfer time offered to passengers in the arrival-departure lines Tm3=10min. It is easy to neglect in this small example that if two opposite direction trains pass through node d9 or d27 one after the other, there may be potential conflicts.The algorithm designed in Section4 is used to solve the model of this small case. First, an incumbent solution of trains’ routing is chosen based on the scheme described in Table 3, whose quality has a great influence on the efficiency of searching the near-optimal solution. The prior knowledge we considered here includes our analysis of the station structure, the nature of each train, and the route by which the train is most likely to occupy, etc. For instance, there is a transfer relationship between c1 and c3, while the arrival-departure linesII and4 are located on either side of the platform. Therefore, we can arrange arrival-departure linesII and4, respectively, as initial routes of trains c1 and c3. In terms of the origin and destination of train c2, there is only one route. And for the remaining two trains, they can be organized to stop at the arrival-departure lines close to the entrance line, as c4 occupies arrival-departure line I and c5 would stop at arrival-departure line4.At the same time, there are 5 trains stopping and passing through the railway station. In the case that origin and destination are prespecified, the number of each train’s route at left bottleneck, arrival-departure line, and right bottleneck is 6, respectively. Therefore, there are 65 possibilities for the routing arrangement of 5 trains. Of course, it may increase exponentially sharply with the number of trains and arrival-departure lines. Therefore, in order to reduce computation time, we take the trains’ routes arrangement as tabu decision variable based on the scheme described in Table 4. Then we get the near-optimal routing arrangement of each train (as shown in Figure 11) and the start time when trains enter the station (as shown in Table 7) based on the designed algorithm in a short time.Table 7
The start time of trains to enter the station.
Train c 1 c 2 c 3 c 4 c 5 Start time 11:25 11:28 11:30 11:34 11:37 Delay time(min) 0 0 0 0 0Figure 11
The route arrangements of the small case.The routing arrangements can be seen clearly in Figure11. From our intuitive, the objective that utilization balanced of the arrival-departure lines is not only satisfied but also meets the transfer relationship between c1 and c3. What is more, all trains are of punctuality. It is noteworthy that the results we obtained from the algorithm are the same as obtained directly from CPLEX solver, and the result suits the requirements of train operations absolutely. Therefore, it can be demonstrated that the proposed model can optimize the routes of trains and the algorithm can get a reasonable solution to ensure the punctuality of train and the rationality of routing.


### 5.2. Large-Scale Case Experiment

To test the effectiveness and efficiency of our proposed train routing problem model and approach, this section applies the proposed model to a real-world case study on the Jinan West high-speed railway station in China, which involves 17 arrival-departure lines including 4 main lines and 8 platforms to the operations of reception and departure. The network of railway is described by the method mentioned in Section2.1 as shown in Figure 12.Figure 12
Construction of Jinan West Railway Station in China.In Figure12, arrival-departure lines I andIII are outbound main lines andII andIV are inbound main lines, respective. Arrival-departure lines I andII are used to receive and depart trains between Beijing and Shanghai, and the direction from Shanghai toward Beijing is defined as the inbound direction, while it is outbound direction. Similarly, arrival-departure linesIII andIVare used to receiving and departing trains between Beijing and Qingdao, while the direction from Qingdao toward Beijing is defined as the inbound direction, whereas it is outbound direction. The arrival-departure lines5~10are located on the side of the outbound, while arrival-departure lines11~17are located on the side of the inbound. The distribution of the platform is shown in Figure 12. In addition, there are four locomotive waiting tracks j1~j4.Owing to the scale of the station, the number of turnouts and crossovers is large, so it is difficult to collect the actual length between all track segments. Thus, the distances between various connection points are not listed here. It is described that if a train stops on the arrival-departure line which is far away from the main line, this would cost more travel time. In the real-world operation, trains need to align with the platform signs when they arrive at the station which need a little more time, and this need not be considered when trains depart from the station. In addition, in terms of our common sense, the trains’ speed will decrease when arrive at the station due to the limit of lateral speed at turnouts. So there is insignificant difference in traveling time in the station between trains running at 300 km/h and 250 km/h. Combined with the calculation methods of track occupied time described in Section2.4 and the large number of observation results in the control center, the occupancy time of each route is shown in Table 8. The parameters αc=1 since the shunting operation is not regarded.Table 8
Travel time of trains on the left bottleneck, the arrival-departure lines, and the right bottleneck.
Stopped arrival-departure line of outbound trains Travel time of reception at the right bottlenecktcsr(s) Travel time of departure at the left bottlenecktcsle(s) Stopped arrival-departure line of inbound trains Travel time of reception at the left bottlenecktcsl(s) Travel time of departure at the right bottlenecktcsre(s) 11 100 80 5 125 105 12 105 85 6 120 100 13 110 90 7 115 95 14 115 95 8 110 90 15 120 100 9 105 85 16 125 105 10 100 80 17 130 110In the real-world station trains reception and departure operations, the nonstopped trains directly pass through the station on main lines, while the stopped trains can stop on any arrival-departure lines except main lines. However, if inbound trains enter the station fromg2 and stop on the arrival-departure line5 in the station as shown in Figure 12, this not only causes route conflicts with the outbound trains but also brings inconvenience to the outbound trains, which occupies more equipment and increases the difficulty of operations. Therefore, the inbound train should occupy the arrival-departure line on the side of inbound main line correspondingly (i.e., inbound trains enter the station from g2 or e2 and stop at arrival-departure lines11~17). Like the outbound trains, namely, outbound trains enter the station from z1 or h1 and stop at arrival-departure lines5~10. As a result, the trains’ travel time on the left or right bottleneck is listed in Table 8. We select all trains passing through the Jinan West railway station between 16:00 and 19:00, that is, 46 trains (including 27 outbound trains and 19 inbound trains). The parameters are shown in Table 9.Table 9
Parameters of trains passing through the Jinan West railway station.
Train Terminal Arrival time Departure time Stop time (min) Direction Origin/Destination in station Operations G30 Beijing South 16:00 16:02 2 Inbound g 2 / z 2 Passing G215 Shanghai 16:05 16:08 3 Outbound z 1 / g 1 Passing G191 Qingdao 16:00 16:09 9 Outbound h 1 / e 1 Passing G143 Shanghai 16:10 16:12 2 Outbound z 1 / g 1 Passing G168 Beijing South 16:12 16:16 4 Inbound g 2 / z 2 Passing G17 Shanghai 16:22 16:24 2 Outbound z 1 / g 1 Passing G132 Beijing South 16:21 16:28 7 Inbound g 2 / z 2 Passing G145 Shanghai 16:15 16:34 19 Outbound z 1 / g 1 Passing G322 Beijing South 16:31 16:39 8 Inbound g 2 / z 2 Passing G1203 Shanghai 16:37 16:43 6 Outbound z 1 / g 1 Passing G412 Beijing South 16:37 16:44 7 Inbound g 2 / z 2 Passing G193 Qingdao 16:42 16:47 5 Outbound h 1 / e 1 Passing G35 Hangzhou East 16:51 16:53 2 Outbound z 1 / g 1 Passing G56 Beijing South 16:51 16:53 2 Inbound g 2 / z 2 Passing G161 Anqing 16:57 16:58 2 Outbound z 1 / g 1 Passing G4 Beijing South 16:59 17:01 2 Inbound g 2 / z 2 Passing G53 Hangzhou East 17:00 17:03 3 Outbound z 1 / g 1 Passing G134 Beijing South 17:09 17:11 2 Inbound g 2 / z 2 Passing G4218 Beijing South 17:01 17:15 14 Inbound e 2 / h 2 Passing G351 Huangshan North 17:17 17:19 2 Outbound z 1 / g 1 Passing G45 Jiangshan 17:22 17:24 2 Outbound z 1 / g 1 Passing G475 Rongcheng 17:29 17:31 2 Outbound h 1 / e 1 Passing G194 Beijing South 17:28 17:32 4 Inbound e 2 / h 2 Passing G138 Beijing South 17:33 17:36 3 Inbound g 2 / z 2 Passing G1267 Qingdao East 17:34 17:40 6 Outbound h 1 / e 1 Passing G330 Tianjin West 17:37 17:40 3 Inbound g 2 / z 2 Passing G21 Shanghai 17:39 17:41 2 Outbound z 1 / g 1 Passing G147 Shanghai 17:43 17:45 2 Outbound z 1 / g 1 Passing G140 Beijing South 17:41 17:45 4 Inbound g 2 / z 2 Passing D6077 Rongcheng - 17:48 - Outbound j 1 / e 1 Originating G195 Qingdao 17:57 18:00 3 Outbound h 1 / e 1 Passing G18 Beijing South 17:59 18:01 2 Inbound g 2 / z 2 Passing G37 Hangzhou East 18:02 18:04 2 Outbound z 1 / g 1 Passing G164 Beijing South 17:53 18:06 13 Inbound g 2 / z 2 Passing G1235 Shanghai 18:08 18:14 6 Outbound z 1 / g 1 Passing G149 Shanghai 18:13 18:18 5 Outbound z 1 / g 1 Passing G142 Beijing South 18:18 18:21 3 Inbound g 2 / z 2 Passing G474 Beijing South 18:27 18:29 2 Inbound e 2 / h 2 Passing G1231 Shanghai 18:17 18:29 12 Outbound z 1 / g 1 Passing G197 Qingdao 18:28 18:31 3 Outbound h 1 / e 1 Passing G324 Beijing South 18:25 18:33 8 Inbound g 2 / z 2 Passing G39 Hangzhou East 18:33 18:35 2 Outbound z 1 / g 1 Passing G23 Shanghai 18:39 18:41 2 Outbound z 1 / g 1 Passing G52 Tianjin West 18:46 18:49 3 Inbound g 2 / z 2 Passing G1257 Shanghai 18:50 18:53 3 Outbound z 1 / g 1 Passing G153 Shanghai 18:56 18:58 2 Outbound z 1 / g 1 Passing The “-" in the table indicates that the corresponding train is originating train. The entry time and stop time depend on the actual situation. It is assumed here that D6077 train enters fromj1 and departs after 30 min.Since only a period of time is selected, we assume that the railway stations are all vacant. The data of every track segment cannot be obtained accurately; thus the value oftc1c2con is 1 min. If the large instance is solved accurately, only the situation of a train occupying the arrival-departure lines needs to calculate 1746 times. Such a large scale problem belongs to the NP-hard as mentioned above. We adopt the heuristic algorithm designed, starting from a set of routes of 46 trains which is the best solution chosen through the iterations of method described in Table 3 to obtain the superior initial solution. Based on that, the tabu search algorithm is implied. We choose the routes with the lowest objective value as the target of the next search. Consequently the efficiency of searching a better solution is ensured. After that, the near-optimal solution with train routing is obtained within 254 seconds, and the results of different direction trains are shown in Tables 10 and 11, respectively (only a part of nodes clearly expresses the routes occupied by train duo to the large number of nodes).Table 10
The routes occupied by outbound trains through the Jinan West railway station between 16:00 and 19:00.
Train Nodes of trains passing through at the left bottleneck when arrive at the station. Arrival-departure line Nodes of trains passing through at the right bottleneck when depart from the station. G215 z 1 , d 6 , d 8 , d 26 , d 41 9 d 58 , d 74 , d 90 , d 93 , g 1 G191 h 1 , d 18 , d 32 , d 40 8 d 57 , d 72 , d 81 , d 86 , d 88 , e 1 G143 z 1 , d 6 , d 8 , d 26 , d 41 9 d 58 , d 74 , d 88 , d 90 , d 93 , g 1 G17 z 1 , d 22 , d 23 , d 26 , d 33 , d 42 10 d 59 , d 73 , d 74 , d 90 , d 93 , g 1 G145 z 1 , d 6 , d 8 , d 10 , d 13 , d 17 , d 37 5 d 54 , d 83 , d 86 , d 88 , d 90 , d 93 , g 1 G1203 z 1 , d 22 , d 23 , d 26 , d 33 , d 42 10 d 59 , d 73 , d 74 , d 90 , d 93 , g 1 G193 h 1 , d 18 , d 39 7 d 56 , d 81 , d 91 , d 92 , e 1 G35 z 1 , d 22 , d 23 , d 26 , d 41 9 d 58 , d 74 , d 88 , d 90 , d 93 , g 1 G161 z 1 , d 6 , d 8 , d 18 , d 32 , d 40 8 d 57 , d 72 , d 81 , d 86 , d 88 , d 90 , d 93 , g 1 G53 z 1 , d 6 , d 8 , d 26 , d 41 9 d 58 , d 74 , d 90 , d 93 , g 1 G351 z 1 , d 6 , d 8 , d 10 , d 13 , d 17 , d 37 5 d 54 , d 83 , d 86 , d 88 , d 90 , d 93 , g 1 G45 z 1 , d 22 , d 23 , d 26 , d 33 , d 42 10 d 59 , d 73 , d 74 , d 90 , d 93 , g 1 G475 h 1 , d 18 , d 39 7 d 56 , d 81 , d 91 , d 92 , e 1 G1267 h 1 , d 26 , d 33 , d 42 10 d 59 , d 73 , d 74 , e 1 G21 z 1 , d 6 , d 8 , d 18 , d 32 , d 39 7 d 56 , d 81 , d 86 , d 88 , d 90 , d 93 , g 1 G147 z 1 , d 6 , d 8 , d 26 , d 41 9 d 58 , d 74 , d 90 , d 93 , g 1 D6077 j 1 , d 17 , d 31 , d 38 6 d 35 , d 71 , d 83 , d 86 , d 88 , e 1 G195 h 1 , d 26 , d 33 , d 42 10 d 59 , d 73 , d 74 , e 1 G37 z 1 , d 6 , d 8 , d 26 , d 41 9 d 58 , d 74 , d 90 , d 93 , g 1 G1235 z 1 , d 6 , d 8 , d 18 , d 32 , d 40 8 d 57 , d 72 , d 81 , d 86 , d 88 , d 90 , d 93 , g 1 G149 z 1 , d 6 , d 8 , d 10 , d 13 , d 17 , d 31 , d 38 6 d 55 , d 71 , d 83 , d 86 , d 88 , d 90 , d 93 , g 1 G1231 z 1 , d 6 , d 8 , d 18 , d 32 , d 39 7 d 56 , d 81 , d 86 , d 88 , d 90 , d 93 , g 1 G197 h 1 , d 18 , d 32 , d 40 8 d 57 , d 72 , d 81 , d 86 , d 88 , e 1 G39 z 1 , d 6 , d 8 , d 26 , d 41 9 d 58 , d 74 , d 90 , d 93 , g 1 G23 z 1 , d 22 , d 23 , d 26 , d 33 , d 42 10 d 59 , d 73 , d 74 , d 90 , d 93 , g 1 G1257 z 1 , d 6 , d 8 , d 26 , d 41 9 d 58 , d 74 , d 90 , d 93 , g 1 G153 z 1 , d 6 , d 8 , d 18 , d 32 , d 40 8 d 57 , d 72 , d 81 , d 86 , d 88 , d 90 , d 93 , g 1Table 11
The routes occupied by inbound trains through the Jinan West railway station between 16:00 and 19:00.
Train Nodes of trains passing through at the right bottleneck when arrive at the station. Arrival-departure line Nodes of trains passing through at the left bottleneck when depart from the station. G30 g 2 , d 98 , d 99 , d 76 , d 75 , d 64 11 d 47 , d 34 , d 28 , d 27 , d 24 , z 2 G168 g 2 , d 89 , d 87 , d 76 , d 65 12 d 48 , d 28 , d 15 , d 11 , z 2 G132 g 2 , d 98 , d 99 , d 82 , d 78 , d 67 14 d 50 , d 36 , d 25 , d 15 , d 11 , z 2 G322 g 2 , d 98 , d 99 , d 76 , d 75 , d 64 11 d 47 , d 34 , d 28 , d 27 , d 24 , z 2 G412 g 2 , d 98 , d 99 , d 82 , d 77 , d 66 13 d 49 , d 35 , d 25 , d 15 , d 11 , z 2 G56 g 2 , d 89 , d 87 , d 82 , d 68 15 d 51 , d 25 , d 15 , d 11 , z 2 G4 g 2 , d 98 , d 99 , d 82 , d 77 , d 66 13 d 49 , d 35 , d 25 , d 15 , d 11 , z 2 G134 g 2 , d 98 , d 99 , d 82 , d 78 , d 67 14 d 50 , d 36 , d 25 , d 15 , d 11 , z 2 G4218 e 2 , d 100 , d 101 , d 85 , d 80 , d 70 17 d 53 , d 30 , d 19 , h 2 G194 e 2 , d 76 , d 75 , d 64 11 d 47 , d 34 , d 28 , h 2 G138 g 2 , d 89 , d 87 , d 84 , d 79 , d 69 16 d 52 , d 29 , d 19 , d 15 , d 11 , z 2 G330 g 2 , d 98 , d 99 , d 82 , d 77 , d 66 13 d 49 , d 35 , d 25 , d 15 , d 11 , z 2 G140 g 2 , d 98 , d 99 , d 82 , d 78 , d 67 14 d 50 , d 36 , d 25 , d 15 , d 11 , z 2 G18 g 2 , d 89 , d 87 , d 76 , d 65 12 d 48 , d 28 , d 15 , d 11 , z 2 G164 g 2 , d 89 , d 87 , d 82 , d 68 15 d 51 , d 25 , d 15 , d 11 , z 2 G142 g 2 , d 98 , d 99 , d 82 , d 77 , d 66 13 d 49 , d 35 , d 25 , d 15 , d 11 , z 2 G474 e 2 , d 76 , d 65 12 d 48 , d 28 , h 2 G324 g 2 , d 89 , d 87 , d 84 , d 79 , d 69 16 d 52 , d 29 , d 19 , d 15 , d 11 , z 2 G52 g 2 , d 89 , d 87 , d 76 , d 65 12 d 48 , d 28 , d 15 , d 11 , z 2As shown in Tables10 and 11, it can be seen that the frequency of arrival-departure lines occupied are almost equal, which satisfies the objective of utilization balanced of them. The nonconflict parallels are occupied in the bottleneck as far as possible for two trains whose arrival time are close to each other. As for the inbound trains G134 and G4218, the arrival time of them are close and may cause a conflict in the right bottleneck. Therefore, routes are arranged on the parallel respectively as shown in Figure 13 (the red and green dotted lines represent the routes of the two trains, instead of the red and the yellow dotted line) to prevent the possibility of collision.Figure 13
The parallel routes of two trains at bottleneck.In addition, the planned start timetable to enter the station is obtained by the arrival time minus the travel time of the reception in the bottleneck according to Table9, which is same with the actual start time calculated by the algorithm. That is, the model we propose and designed algorithm can get the trains routing arrangement in a high quality and short time based on the punctuality of trains. From the analysis results of the examples, the proposed model and the designed algorithm can solve the TRP efficiently.It is worth mentioning that the problem we discussed is a NP-hard problem. Owing to the nonlinearity and numerous decision variables of the proposed mathematical model, there is neither proper commercial software available nor an algorithm which can solve such problems accurately at present. At the same time, the heuristic algorithm we designed can solve the problem accurately and efficiently as mentioned above. So we did not compare the designed algorithm with other methods in the large-scale case.


## 5.1. A Small-Scale Case Study

In this case, we consider a two mainI andII lines railway station as shown in Figure 10 which is outbound and inbound direction, respectively. In the left bottleneck, there are a reception line z1 of outbound trains, a departure line z2 of inbound trains, and a locomotive waiting track j1. At the same time, there are 6 arrival-departure lines, of which arrival-departure linesII, 3 and 4 next to a platform. In the right bottleneck, there are 4 lines including a departure line g1 of outbound trains, a reception line g2 of inbound trains. and two locomotive waiting tracks j2 and j3. The distances between connection points in this railway station are shown in Table 5.Table 5
Distances between points in the railway network in Figure10.
Node:di Node:di Distance(m) Node:di Node:di Distance(m) Node:di Node:di Distance(m) 1 2 90 9 11 60 22 28 85 1 9 305 10 12 80 23 28 90 2 4 60 11 16 85 24 25 90 3 5 48 11 17 90 25 34 300 3 6 60 12 18 750 25 26 60 4 5 60 13 19 750 26 29 100 4 6 48 14 20 750 27 30 148 5 8 175 15 21 750 28 27 60 6 7 100 16 22 750 29 31 60 7 14 170 17 23 750 29 32 90 7 9 90 18 24 80 30 31 90 8 10 90 19 25 125 30 32 60 8 13 125 20 26 170 31 33 50 9 15 125 21 27 125 33 34 60Figure 10
The structure of a small-scale station.In order to test the effectiveness of the proposed models and solution algorithms, we derive a set of instances in this small-scale rail station with different numbers of trains (the type of trains is exhaustive to demonstrate the versatility and correctness of the model). Table6 shows the origin and destination of each train, as well as the characteristic parameters of them. Trains c1 and c4 are outbound trains, while c3 is inbound train. At the same time, there is a transfer relationship between c1 and c3. Trains c2 and c5 are shunting operations, wherein c2 travels from the locomotive waiting tracks j2 to j1 and c5 travels from j1 to be an originating train (i.e., train c5 would choose an arrival-departure line to stop and then depart from the station through the departure node g1). In order to distinguish the importance of operations, the higher punctuality required for train reception, and departure operations compared to the shunting operations, we set the weights to 0.9 and 0.1, respectively. As for the multiobjective of our model, we attach the most importance to the punctuality, then the total travel time and utilization balanced of the arrival-departure lines are considered evenly. Thus set the parameters β1=β2=0.3 and β3=0.4. In addition to this, the preparation time of each train is 1 min, and the additional time that provides trains’ acceleration and deceleration is 2 min and 1 min, respectively.Table 6
The parameters of trains in the small case.
Train Origin Destination Average velocity (km/h) Operations Planned timetable Stop time (min) c 1 z 1 g 1 30 Passing 11:25 17 c 2 j 2 j 1 15 Shunting 11:28 0 c 3 g 2 z 2 30 Passing 11:30 10 c 4 z 1 g 1 30 Passing 11:34 6 c 5 j 1 g 1 15 Shunting 11:37 30We assume the headway timeTm1=2min, the minimum time interval of potential area of two trains Tm2=1min, and the minimum transfer time offered to passengers in the arrival-departure lines Tm3=10min. It is easy to neglect in this small example that if two opposite direction trains pass through node d9 or d27 one after the other, there may be potential conflicts.The algorithm designed in Section4 is used to solve the model of this small case. First, an incumbent solution of trains’ routing is chosen based on the scheme described in Table 3, whose quality has a great influence on the efficiency of searching the near-optimal solution. The prior knowledge we considered here includes our analysis of the station structure, the nature of each train, and the route by which the train is most likely to occupy, etc. For instance, there is a transfer relationship between c1 and c3, while the arrival-departure linesII and4 are located on either side of the platform. Therefore, we can arrange arrival-departure linesII and4, respectively, as initial routes of trains c1 and c3. In terms of the origin and destination of train c2, there is only one route. And for the remaining two trains, they can be organized to stop at the arrival-departure lines close to the entrance line, as c4 occupies arrival-departure line I and c5 would stop at arrival-departure line4.At the same time, there are 5 trains stopping and passing through the railway station. In the case that origin and destination are prespecified, the number of each train’s route at left bottleneck, arrival-departure line, and right bottleneck is 6, respectively. Therefore, there are 65 possibilities for the routing arrangement of 5 trains. Of course, it may increase exponentially sharply with the number of trains and arrival-departure lines. Therefore, in order to reduce computation time, we take the trains’ routes arrangement as tabu decision variable based on the scheme described in Table 4. Then we get the near-optimal routing arrangement of each train (as shown in Figure 11) and the start time when trains enter the station (as shown in Table 7) based on the designed algorithm in a short time.Table 7
The start time of trains to enter the station.
Train c 1 c 2 c 3 c 4 c 5 Start time 11:25 11:28 11:30 11:34 11:37 Delay time(min) 0 0 0 0 0Figure 11
The route arrangements of the small case.The routing arrangements can be seen clearly in Figure11. From our intuitive, the objective that utilization balanced of the arrival-departure lines is not only satisfied but also meets the transfer relationship between c1 and c3. What is more, all trains are of punctuality. It is noteworthy that the results we obtained from the algorithm are the same as obtained directly from CPLEX solver, and the result suits the requirements of train operations absolutely. Therefore, it can be demonstrated that the proposed model can optimize the routes of trains and the algorithm can get a reasonable solution to ensure the punctuality of train and the rationality of routing.


## 5.2. Large-Scale Case Experiment

To test the effectiveness and efficiency of our proposed train routing problem model and approach, this section applies the proposed model to a real-world case study on the Jinan West high-speed railway station in China, which involves 17 arrival-departure lines including 4 main lines and 8 platforms to the operations of reception and departure. The network of railway is described by the method mentioned in Section2.1 as shown in Figure 12.Figure 12
Construction of Jinan West Railway Station in China.In Figure12, arrival-departure lines I andIII are outbound main lines andII andIV are inbound main lines, respective. Arrival-departure lines I andII are used to receive and depart trains between Beijing and Shanghai, and the direction from Shanghai toward Beijing is defined as the inbound direction, while it is outbound direction. Similarly, arrival-departure linesIII andIVare used to receiving and departing trains between Beijing and Qingdao, while the direction from Qingdao toward Beijing is defined as the inbound direction, whereas it is outbound direction. The arrival-departure lines5~10are located on the side of the outbound, while arrival-departure lines11~17are located on the side of the inbound. The distribution of the platform is shown in Figure 12. In addition, there are four locomotive waiting tracks j1~j4.Owing to the scale of the station, the number of turnouts and crossovers is large, so it is difficult to collect the actual length between all track segments. Thus, the distances between various connection points are not listed here. It is described that if a train stops on the arrival-departure line which is far away from the main line, this would cost more travel time. In the real-world operation, trains need to align with the platform signs when they arrive at the station which need a little more time, and this need not be considered when trains depart from the station. In addition, in terms of our common sense, the trains’ speed will decrease when arrive at the station due to the limit of lateral speed at turnouts. So there is insignificant difference in traveling time in the station between trains running at 300 km/h and 250 km/h. Combined with the calculation methods of track occupied time described in Section2.4 and the large number of observation results in the control center, the occupancy time of each route is shown in Table 8. The parameters αc=1 since the shunting operation is not regarded.Table 8
Travel time of trains on the left bottleneck, the arrival-departure lines, and the right bottleneck.
Stopped arrival-departure line of outbound trains Travel time of reception at the right bottlenecktcsr(s) Travel time of departure at the left bottlenecktcsle(s) Stopped arrival-departure line of inbound trains Travel time of reception at the left bottlenecktcsl(s) Travel time of departure at the right bottlenecktcsre(s) 11 100 80 5 125 105 12 105 85 6 120 100 13 110 90 7 115 95 14 115 95 8 110 90 15 120 100 9 105 85 16 125 105 10 100 80 17 130 110In the real-world station trains reception and departure operations, the nonstopped trains directly pass through the station on main lines, while the stopped trains can stop on any arrival-departure lines except main lines. However, if inbound trains enter the station fromg2 and stop on the arrival-departure line5 in the station as shown in Figure 12, this not only causes route conflicts with the outbound trains but also brings inconvenience to the outbound trains, which occupies more equipment and increases the difficulty of operations. Therefore, the inbound train should occupy the arrival-departure line on the side of inbound main line correspondingly (i.e., inbound trains enter the station from g2 or e2 and stop at arrival-departure lines11~17). Like the outbound trains, namely, outbound trains enter the station from z1 or h1 and stop at arrival-departure lines5~10. As a result, the trains’ travel time on the left or right bottleneck is listed in Table 8. We select all trains passing through the Jinan West railway station between 16:00 and 19:00, that is, 46 trains (including 27 outbound trains and 19 inbound trains). The parameters are shown in Table 9.Table 9
Parameters of trains passing through the Jinan West railway station.
Train Terminal Arrival time Departure time Stop time (min) Direction Origin/Destination in station Operations G30 Beijing South 16:00 16:02 2 Inbound g 2 / z 2 Passing G215 Shanghai 16:05 16:08 3 Outbound z 1 / g 1 Passing G191 Qingdao 16:00 16:09 9 Outbound h 1 / e 1 Passing G143 Shanghai 16:10 16:12 2 Outbound z 1 / g 1 Passing G168 Beijing South 16:12 16:16 4 Inbound g 2 / z 2 Passing G17 Shanghai 16:22 16:24 2 Outbound z 1 / g 1 Passing G132 Beijing South 16:21 16:28 7 Inbound g 2 / z 2 Passing G145 Shanghai 16:15 16:34 19 Outbound z 1 / g 1 Passing G322 Beijing South 16:31 16:39 8 Inbound g 2 / z 2 Passing G1203 Shanghai 16:37 16:43 6 Outbound z 1 / g 1 Passing G412 Beijing South 16:37 16:44 7 Inbound g 2 / z 2 Passing G193 Qingdao 16:42 16:47 5 Outbound h 1 / e 1 Passing G35 Hangzhou East 16:51 16:53 2 Outbound z 1 / g 1 Passing G56 Beijing South 16:51 16:53 2 Inbound g 2 / z 2 Passing G161 Anqing 16:57 16:58 2 Outbound z 1 / g 1 Passing G4 Beijing South 16:59 17:01 2 Inbound g 2 / z 2 Passing G53 Hangzhou East 17:00 17:03 3 Outbound z 1 / g 1 Passing G134 Beijing South 17:09 17:11 2 Inbound g 2 / z 2 Passing G4218 Beijing South 17:01 17:15 14 Inbound e 2 / h 2 Passing G351 Huangshan North 17:17 17:19 2 Outbound z 1 / g 1 Passing G45 Jiangshan 17:22 17:24 2 Outbound z 1 / g 1 Passing G475 Rongcheng 17:29 17:31 2 Outbound h 1 / e 1 Passing G194 Beijing South 17:28 17:32 4 Inbound e 2 / h 2 Passing G138 Beijing South 17:33 17:36 3 Inbound g 2 / z 2 Passing G1267 Qingdao East 17:34 17:40 6 Outbound h 1 / e 1 Passing G330 Tianjin West 17:37 17:40 3 Inbound g 2 / z 2 Passing G21 Shanghai 17:39 17:41 2 Outbound z 1 / g 1 Passing G147 Shanghai 17:43 17:45 2 Outbound z 1 / g 1 Passing G140 Beijing South 17:41 17:45 4 Inbound g 2 / z 2 Passing D6077 Rongcheng - 17:48 - Outbound j 1 / e 1 Originating G195 Qingdao 17:57 18:00 3 Outbound h 1 / e 1 Passing G18 Beijing South 17:59 18:01 2 Inbound g 2 / z 2 Passing G37 Hangzhou East 18:02 18:04 2 Outbound z 1 / g 1 Passing G164 Beijing South 17:53 18:06 13 Inbound g 2 / z 2 Passing G1235 Shanghai 18:08 18:14 6 Outbound z 1 / g 1 Passing G149 Shanghai 18:13 18:18 5 Outbound z 1 / g 1 Passing G142 Beijing South 18:18 18:21 3 Inbound g 2 / z 2 Passing G474 Beijing South 18:27 18:29 2 Inbound e 2 / h 2 Passing G1231 Shanghai 18:17 18:29 12 Outbound z 1 / g 1 Passing G197 Qingdao 18:28 18:31 3 Outbound h 1 / e 1 Passing G324 Beijing South 18:25 18:33 8 Inbound g 2 / z 2 Passing G39 Hangzhou East 18:33 18:35 2 Outbound z 1 / g 1 Passing G23 Shanghai 18:39 18:41 2 Outbound z 1 / g 1 Passing G52 Tianjin West 18:46 18:49 3 Inbound g 2 / z 2 Passing G1257 Shanghai 18:50 18:53 3 Outbound z 1 / g 1 Passing G153 Shanghai 18:56 18:58 2 Outbound z 1 / g 1 Passing The “-" in the table indicates that the corresponding train is originating train. The entry time and stop time depend on the actual situation. It is assumed here that D6077 train enters fromj1 and departs after 30 min.Since only a period of time is selected, we assume that the railway stations are all vacant. The data of every track segment cannot be obtained accurately; thus the value oftc1c2con is 1 min. If the large instance is solved accurately, only the situation of a train occupying the arrival-departure lines needs to calculate 1746 times. Such a large scale problem belongs to the NP-hard as mentioned above. We adopt the heuristic algorithm designed, starting from a set of routes of 46 trains which is the best solution chosen through the iterations of method described in Table 3 to obtain the superior initial solution. Based on that, the tabu search algorithm is implied. We choose the routes with the lowest objective value as the target of the next search. Consequently the efficiency of searching a better solution is ensured. After that, the near-optimal solution with train routing is obtained within 254 seconds, and the results of different direction trains are shown in Tables 10 and 11, respectively (only a part of nodes clearly expresses the routes occupied by train duo to the large number of nodes).Table 10
The routes occupied by outbound trains through the Jinan West railway station between 16:00 and 19:00.
Train Nodes of trains passing through at the left bottleneck when arrive at the station. Arrival-departure line Nodes of trains passing through at the right bottleneck when depart from the station. G215 z 1 , d 6 , d 8 , d 26 , d 41 9 d 58 , d 74 , d 90 , d 93 , g 1 G191 h 1 , d 18 , d 32 , d 40 8 d 57 , d 72 , d 81 , d 86 , d 88 , e 1 G143 z 1 , d 6 , d 8 , d 26 , d 41 9 d 58 , d 74 , d 88 , d 90 , d 93 , g 1 G17 z 1 , d 22 , d 23 , d 26 , d 33 , d 42 10 d 59 , d 73 , d 74 , d 90 , d 93 , g 1 G145 z 1 , d 6 , d 8 , d 10 , d 13 , d 17 , d 37 5 d 54 , d 83 , d 86 , d 88 , d 90 , d 93 , g 1 G1203 z 1 , d 22 , d 23 , d 26 , d 33 , d 42 10 d 59 , d 73 , d 74 , d 90 , d 93 , g 1 G193 h 1 , d 18 , d 39 7 d 56 , d 81 , d 91 , d 92 , e 1 G35 z 1 , d 22 , d 23 , d 26 , d 41 9 d 58 , d 74 , d 88 , d 90 , d 93 , g 1 G161 z 1 , d 6 , d 8 , d 18 , d 32 , d 40 8 d 57 , d 72 , d 81 , d 86 , d 88 , d 90 , d 93 , g 1 G53 z 1 , d 6 , d 8 , d 26 , d 41 9 d 58 , d 74 , d 90 , d 93 , g 1 G351 z 1 , d 6 , d 8 , d 10 , d 13 , d 17 , d 37 5 d 54 , d 83 , d 86 , d 88 , d 90 , d 93 , g 1 G45 z 1 , d 22 , d 23 , d 26 , d 33 , d 42 10 d 59 , d 73 , d 74 , d 90 , d 93 , g 1 G475 h 1 , d 18 , d 39 7 d 56 , d 81 , d 91 , d 92 , e 1 G1267 h 1 , d 26 , d 33 , d 42 10 d 59 , d 73 , d 74 , e 1 G21 z 1 , d 6 , d 8 , d 18 , d 32 , d 39 7 d 56 , d 81 , d 86 , d 88 , d 90 , d 93 , g 1 G147 z 1 , d 6 , d 8 , d 26 , d 41 9 d 58 , d 74 , d 90 , d 93 , g 1 D6077 j 1 , d 17 , d 31 , d 38 6 d 35 , d 71 , d 83 , d 86 , d 88 , e 1 G195 h 1 , d 26 , d 33 , d 42 10 d 59 , d 73 , d 74 , e 1 G37 z 1 , d 6 , d 8 , d 26 , d 41 9 d 58 , d 74 , d 90 , d 93 , g 1 G1235 z 1 , d 6 , d 8 , d 18 , d 32 , d 40 8 d 57 , d 72 , d 81 , d 86 , d 88 , d 90 , d 93 , g 1 G149 z 1 , d 6 , d 8 , d 10 , d 13 , d 17 , d 31 , d 38 6 d 55 , d 71 , d 83 , d 86 , d 88 , d 90 , d 93 , g 1 G1231 z 1 , d 6 , d 8 , d 18 , d 32 , d 39 7 d 56 , d 81 , d 86 , d 88 , d 90 , d 93 , g 1 G197 h 1 , d 18 , d 32 , d 40 8 d 57 , d 72 , d 81 , d 86 , d 88 , e 1 G39 z 1 , d 6 , d 8 , d 26 , d 41 9 d 58 , d 74 , d 90 , d 93 , g 1 G23 z 1 , d 22 , d 23 , d 26 , d 33 , d 42 10 d 59 , d 73 , d 74 , d 90 , d 93 , g 1 G1257 z 1 , d 6 , d 8 , d 26 , d 41 9 d 58 , d 74 , d 90 , d 93 , g 1 G153 z 1 , d 6 , d 8 , d 18 , d 32 , d 40 8 d 57 , d 72 , d 81 , d 86 , d 88 , d 90 , d 93 , g 1Table 11
The routes occupied by inbound trains through the Jinan West railway station between 16:00 and 19:00.
Train Nodes of trains passing through at the right bottleneck when arrive at the station. Arrival-departure line Nodes of trains passing through at the left bottleneck when depart from the station. G30 g 2 , d 98 , d 99 , d 76 , d 75 , d 64 11 d 47 , d 34 , d 28 , d 27 , d 24 , z 2 G168 g 2 , d 89 , d 87 , d 76 , d 65 12 d 48 , d 28 , d 15 , d 11 , z 2 G132 g 2 , d 98 , d 99 , d 82 , d 78 , d 67 14 d 50 , d 36 , d 25 , d 15 , d 11 , z 2 G322 g 2 , d 98 , d 99 , d 76 , d 75 , d 64 11 d 47 , d 34 , d 28 , d 27 , d 24 , z 2 G412 g 2 , d 98 , d 99 , d 82 , d 77 , d 66 13 d 49 , d 35 , d 25 , d 15 , d 11 , z 2 G56 g 2 , d 89 , d 87 , d 82 , d 68 15 d 51 , d 25 , d 15 , d 11 , z 2 G4 g 2 , d 98 , d 99 , d 82 , d 77 , d 66 13 d 49 , d 35 , d 25 , d 15 , d 11 , z 2 G134 g 2 , d 98 , d 99 , d 82 , d 78 , d 67 14 d 50 , d 36 , d 25 , d 15 , d 11 , z 2 G4218 e 2 , d 100 , d 101 , d 85 , d 80 , d 70 17 d 53 , d 30 , d 19 , h 2 G194 e 2 , d 76 , d 75 , d 64 11 d 47 , d 34 , d 28 , h 2 G138 g 2 , d 89 , d 87 , d 84 , d 79 , d 69 16 d 52 , d 29 , d 19 , d 15 , d 11 , z 2 G330 g 2 , d 98 , d 99 , d 82 , d 77 , d 66 13 d 49 , d 35 , d 25 , d 15 , d 11 , z 2 G140 g 2 , d 98 , d 99 , d 82 , d 78 , d 67 14 d 50 , d 36 , d 25 , d 15 , d 11 , z 2 G18 g 2 , d 89 , d 87 , d 76 , d 65 12 d 48 , d 28 , d 15 , d 11 , z 2 G164 g 2 , d 89 , d 87 , d 82 , d 68 15 d 51 , d 25 , d 15 , d 11 , z 2 G142 g 2 , d 98 , d 99 , d 82 , d 77 , d 66 13 d 49 , d 35 , d 25 , d 15 , d 11 , z 2 G474 e 2 , d 76 , d 65 12 d 48 , d 28 , h 2 G324 g 2 , d 89 , d 87 , d 84 , d 79 , d 69 16 d 52 , d 29 , d 19 , d 15 , d 11 , z 2 G52 g 2 , d 89 , d 87 , d 76 , d 65 12 d 48 , d 28 , d 15 , d 11 , z 2As shown in Tables10 and 11, it can be seen that the frequency of arrival-departure lines occupied are almost equal, which satisfies the objective of utilization balanced of them. The nonconflict parallels are occupied in the bottleneck as far as possible for two trains whose arrival time are close to each other. As for the inbound trains G134 and G4218, the arrival time of them are close and may cause a conflict in the right bottleneck. Therefore, routes are arranged on the parallel respectively as shown in Figure 13 (the red and green dotted lines represent the routes of the two trains, instead of the red and the yellow dotted line) to prevent the possibility of collision.Figure 13
The parallel routes of two trains at bottleneck.In addition, the planned start timetable to enter the station is obtained by the arrival time minus the travel time of the reception in the bottleneck according to Table9, which is same with the actual start time calculated by the algorithm. That is, the model we propose and designed algorithm can get the trains routing arrangement in a high quality and short time based on the punctuality of trains. From the analysis results of the examples, the proposed model and the designed algorithm can solve the TRP efficiently.It is worth mentioning that the problem we discussed is a NP-hard problem. Owing to the nonlinearity and numerous decision variables of the proposed mathematical model, there is neither proper commercial software available nor an algorithm which can solve such problems accurately at present. At the same time, the heuristic algorithm we designed can solve the problem accurately and efficiently as mentioned above. So we did not compare the designed algorithm with other methods in the large-scale case.


## 6. Conclusions

This paper focuses on modeling and solving the TRP based on considering heterogeneous trains and detailed structure of the rail station. The main research work and conclusions are summarized as follows:(1)
A detailed mathematical formulation for TRP describes the routing arrangement in a large and complex high-speed railway station. The turnout node and the arrival-departure line node are defined to describe the layout of the railway station instead of the traditional railway network. The heterogeneous trains are taken into account; and the potential collisions of trains and convenience for passengers transferring at station are considered as constraints. Then we propose a method to calculate the occupied time of each track and describe the TRP problem more completely and realistically.(2)
A high-efficient algorithm based on tabu search is proposed based on the proposed model. We set two different neighborhoods for searching incumbent solution and tabu move to search the near-optimal solution. The scale of first neighborhood is smaller to search in a short time, and the second neighborhood is wilder in order to avoid empty neighborhoods as far as possible. Then we set two strategies of them, respectively.(3)
The correctness of the proposed model is verified with a small example that includes all types of trains and operations. The results obtained by the proposed tabu search algorithm are the same as those obtained directly from CPLEX solver. The result is fully in line with the requirements of train operations. In the large scale case, we chose the actual trains within 3 hours passing through the Jinan West railway station which involves 17 arrival-departure lines. The excellent solutions are obtained within 254 seconds by the designed algorithm.It is realistic and easy to understand our proposed model. However, it has the characteristics of non-linearity and has difficulties to solve the mathematical formulas. Therefore, one possible future direction is to improve the model. Second, the tabu search algorithm needs to set effective rules to generate the incumbent solution’s neighborhood and rules for tabu move. In this respect, further improvements are needed to obtain a better near-optimal solution more efficiently. More importantly, future research does not restrict to a railway stations. With the rapid development of high-speed railway, there are more train routing and scheduling problems, train rerouting and rescheduling optimization problems, etc., which need to be further studied.



---

*Source: 8394397-2018-10-03.xml*