A real-time train routing and platforming problem in complex railway stations

Abstract

This paper studies the real-time trains routing and platforming problem (RT-TRPP) in railway stations that arises from the unreliable arrival times of freight trains, flexible shunting operations and dynamic station layout caused by equipment failure. The feasibility of station timetable is checked before preparing a route for a train or after updating the station layout. If the station timetable is infeasible, the reassignment of trains is triggered. After introducing a problem formulation for the RT-TRPP, we propose an Integer Linear Program (ILP) that strives to minimize the number of conflicting trains. In resulting timetable, directions, arrival and leaving time remain the same with networks timetable to prevent traffic disturbance of neighboring territories. If the resulting timetable is still infeasible, conflicting trains are pointed out with the cause analysis. The method is tested on real-world complex station which receives always the overload of trains’ activities. The optimal full-day solution of 249 trains is obtained within 2 seconds. The efficiency of this method meets the time-critical nature of RT-TRPP.

Keywords

Train platforming train routing traffic management integer linear programming

1 Introduction

To meet increasing rail transport demands, railway networks are operated nearly at capacity margins. However, only certain critical resources are close to capacity limit. Junction center stations not only act as a customer service center but also need to balance the traffic on connecting lines and on complex rail network inside the station. As trains speed up on connecting lines, busy and complex railway station certainly becomes a critical resource. Compared with routing and scheduling problem on railway network, the buffer time and space in stations is greatly limited. To enhance capacity, new tracks and routes can be built. Except investments and space needed, such solutions are unlikely to be completed in short or medium terms. Furthermore, such extensions are usually infeasible to execute in urban areas. Thus, exploitation of pass-through capacity in stations is an economic and efficient remedy.

The traditional process to generate a timetable for a railway network is divided into several stages proposed by [12]. Firstly, an initial network timetable is generated by train activities managers (national, regional, freight) based on traffic frequencies, volume of traffic, rough layout of railway network together with the desired lines and their connection requirements [3, 8]. Then, station operators need to check whether the network timetable is feasible within the railway station while satisfying capacity, safety and customer service [6, 9]. Most of the studies focus on the generation of network timetable with a global point of view [1 , 4]. In practice, initial timetables based on rough pass-through capacity of stations does not always fit to existing infrastructure and shunting plan within stations.

Reference [5] considers computational complexity of trains routing problem in railway stations. The problem is formulated as a node-packing problem and describes the relationship between the routing problem and the Fixed Interval Scheduling Problem. Based on the satisfiability problem, they deduce that the safety feasibility problem is NP-complete if each train has three or more routing possibilities. However, if each train has at most two routing possibilities, then the general feasibility problem can be solved in polynomial time. Furthermore, if the layout of the railway station is fixed, then the safety optimization problem can be solved by a dynamic programming approach in an amount of time that is polynomial in the number of trains.

Reference [9] formulates train routing problem in stations, with given arrival and leaving times of trains in a cyclic timetable (one hour) and detailed station layout, as an integer linear program based on the Node Packing Problem (NPP). The deviations δ of original arrival and departure times are permitted. Furthermore, a solution procedure is proposed for the problem, based on a branch-and-cut approach. To reduce the size of the problem, they firstly determine the admissible combinations of routing possibilities (r, δ; r′, δ′) ∈ Ft, t^′ for combinations of trains t and t’, considering the safety, (un-)coupling, connection requirements and the set of allowable routing possibilities for each train. Secondly, the preprocessing step simplifies the problem by removing dominated nodes in the graph of node packing problem. Then, valid inequalities are added to tighten the problem. An initial solution is generated by heuristics method to accelerate the calculation. But the calculation of the set Ft,t’ requires a lot of calculation time O(T²*R²*δ²) in a large and busy railway station which consists of R possible paths and is passed through by a group of T trains with permitted deviation δ.

Reference [10] improves the previous model by extending the preprocessing techniques and considering routing preferences and shunting decisions. In the model, only the decision whether or not to shunt is considered without the feasibility checking on routes and tracks. If a train is to be shunted towards a parking area, the train is to have a standstill at its arrival track and a different departure track, and is to be at a track of parking area between these two standstills. The shunting decision and allocation preferences are represented by the weight coefficient of allocation variables. The node packing of maximum weight represents a feasible routing of trains with the maximal preference and maximum number of trains scheduled.

Reference [7] considers train scheduling problem for complex and busy stations. They develop a scheduling heuristics analogous to manual methods of train planners. With the progressive improvement of the search rules, the computing times fell from several hours to a few seconds, depending on the version of the algorithm and the scheduling problem, but the insolvable conflicts are removed by hand before the heuristics methods.

In our problem, each train has three or more routing possibilities. Considering the computational complexity, we solve the routing problem with the fixed arrival and leaving time in order to meet the real-time occasion. The arrival and leaving times are given by the network timetable or predicted by the current traffic. The conflicting trains are pointed out with the cause analysis.

The rest of the paper is organized as follows. This paper starts with the formalization of railway station layout and trains’ activities. We analyze the difference and relation between the network and station timetable. An integer linear programming model is described in section 3. The calculation process is introduced in section 4. In section 5, our method is tested on real cases in complex station which receives always the overload of trains’ activities. In section 6, we give a conclusion and discuss further developments and application of the methodology.

2 General description of the problem

This train routing and platforming problem faced by railway station managers is to generate a conflict-free timetable including train operations and shunting operations. The train routing and platforming problem in railway station studied in this paper can be described as following. Given layout of station, arrival and departure times as well as destination and origin of trains, we aim to route all trains through the station. This timetable must ensure that there are no pair of conflicting trains over routes and tracks, while allowing the coupling and uncoupling operations on tracks and respecting their tracks preferences and the accessibility of complete route of trains. This problem includes three sub-problems: routing, platforming and feasibility-checking.

2.1 Station layout

A standard station, as shown in Fig. 1, consists of signals, sections, switches and tracks next to a platform.

Sets and Objects in a station are classified in Table 1.

Fig. 1

A standard station layout.

Table 1

Sets and Objects in a station

Sets		Objects
Sections L^e	Block sections	S1LQG,SN1LQG,X1LQG,XN1LQG
	Shunting tracks	D1 G, D2G
Switches S		1DG 10DG
Tracks Lⁱ		IG, IIG, 3 G, 4G
Signals	Train signals	S,SN,X,XN, SI,XI,SII,XII,S3,X3,S4,X4,
	Shunting signals	D1,D2,D3,D4

A Train enters or leaves a railway station by a section. Both block sections and shunting tracks act as sections. A block section connects other railway stations. Used for coupling or uncoupling trains, a shunting track connects with shunting yards. Each section corresponds to a travelling direction. The railway network outside the sections is not relevant for our problem.

A Train enters by an inbound route and stops on a track to finish the planned train operations. Then it leaves by an outbound route. If the train arrives at the final station, shunting routes are used to deliver the train back to the garage. If the train departs from the original station, shunting routes are used to deliver the train to the track. Shunting routes are also used for the coupling or uncoupling operation. In practice, inbound route including switches and a track. In our model, a route only includes switches. Each route category is given an example in Table 2. Routes are named by the relevant signals.

Table 2

Routes category

Route category	Route name	Route objects
Inbound train route	S-SI	7DG,1DG
Outbound train route	XI-XN	2DG,8DG
Inbound shunting route	D3-D1	5DG
Outbound shunting route	D1-D1G	5DG

An inbound route includes a sequence of switches connecting a section to a track. In the opposite direction, an out bound route includes a sequence of switches connecting a track to a section. A complete route includes an inbound route, a track and an outbound route. The set of routes is denoted as P. Routes connecting the track l_i with the section l_e are classified in the set P^(l_i,l_e).

2.2 Train operations & movements

The traffic in the railway station is defined by a set of trains T. Every train t ∈ T consists of a set of ordered movements M^t and a set of ordered operations O^t. The index represents the chronological order, for example, $m_{1}^{t}$ occurs before $m_{2}^{t}$ , and $o_{1}^{t}$ occurs before $o_{2}^{t}$ . A train at least consists of two movements and one operation. A movement occupies a route and a track. An operation needs a track to stop the train. The train activities and necessary resources are summarized in Table 3.

Table 3
Train activities and resource demand

Train activities Resources Occupation duration

Inbound movement Inbound route (switches) Track [ $α_{m}$ , $β_{m}$ [

Operation Track [ $A_{t}^{net}$ , $B_{t}^{net}$ [

Outbound movement Outbound route (switches) Track [ $α_{m^{'}}$ , $β_{m^{'}}$ [

Train activities	Resources	Occupation duration
Inbound movement	Inbound route (switches) Track	[ $α_{m}$ , $β_{m}$ [
Operation	Track	[ $A_{t}^{net}$ , $B_{t}^{net}$ [
Outbound movement	Outbound route (switches) Track	[ $α_{m^{'}}$ , $β_{m^{'}}$ [

As soon as an inbound route is prepared for the train, its route and track assignment cannot be changed anymore. So the train set has two parts:

Trains with fixed route and track assignment, denoted as T^assigned. Relevant movements classified in the set M^assigned.

New arrival trains with flexible route and track assignment, denoted as T^new. Relevant movements classified in the set M^new.

So we have $T = T^{assigned} \cup T^{new}$ $M = M^{assigned} \cup M^{new}$

Movements from or to the same section l^e are classified in the set M^{l
^e}. Routes selectable for movement m are classified in the set P^m. P^m is the set of routes for the movement m, i.e. the set of routes connecting the section $l_{m}^{e}$ with a track $l_{i} \in L_{t}^{Pref}$ preferred by the train. $P^{m} = \underset{l_{i} \in L_{t}^{Pref}}{\cup} P^{(l_{i}, l_{m}^{e})}$ .

2.3 Routing & platforming

The routing problem is to assign each train to a complete route through the railway station. The same switch or track cannot be occupied by two trains at the same time. In practice, a switch is occupied from the preparation of the relevant route until the release time.

When the train arrives at the section, it reserves an inbound route leading to a track. As the train runs along the inbound route, the switches comprising the route are released sequentially. The safety rules dictate that any switches can be reserved by only one train at a time. In that case, another train cannot reserve the same switch until it is released. In principle, the reservation duration of a switch can be calculated by the length and speed of train. But the tightness of the resource distribution will easily led to interruptions of movement even collision of trains by any small perturbation. To reduce the risk, all switches in the inbound route are reserved until the train releases the route. Similarly, all switches of an outbound route are reserved until the train releases the route.

One track can be reserved by only one train at a time. Tracks are reserved from the beginning of the inbound movement until the end of the outbound movement. During standstill on a track between these movements, a minimum customer service time must be given to passengers to board or take off trains, or to transfer between trains. In addition, preferences of tracks and constraints on coupling and uncoupling of trains need also to be taken into account.

To assign a track to a train, we need consider both length and direction of trains. We need to pre-calculate $L_{t}^{Pref}$ set of tracks in preference order of train t. The set of tracks which satisfies train length is denoted as $L_{t}^{Length}$ . The set of tracks in preference order based on directions is denoted as $L_{t}^{PrefDir}$ . The direction is a character of movements. The set of tracks which satisfies movement direction is denoted as $L_{m}^{PrefDir}$ . The sorting of tracks depends on all preference factors. $L_{t}^{Pref}$ is generate as bellows. $\begin{matrix} t \in T, L_{t}^{Pref} & = ⋂_{m \in M_{t}} L_{m}^{PrefDir} ⋂ L_{t}^{Length} \\ = L_{t}^{PrefDir} ⋂ L_{t}^{Length} \end{matrix}$

2.4 Feasibility-checking

On real-time occasion, traffic disturbance changes the arrival time of trains. Equipment failure and maintenance change the station layout. The station timetable should update according to the current occasion. So there are four occasions to regenerate the station timetable:

hen a train arrives, the arrival time is different from the planned time

When a train departs, the departure time is different from the planned time

A new maintenance plan is delivered

An equipment breakdowns or gets back to normal. If a switch is breakdown, all the relevant routes are unavailable.

2.5 Network timetable & station timetable

In network timetable, the arrival time is the time at which the train stops at a track. The departure time of a train is the time at which the train starts to leave the track. As described at the beginning of this section, the arrival or departure time of trains are generated by administrative levels and railway station manager. The time unit is minutes. In practice, the occupation of tracks in network timetable is always shorter than real occupation duration in station timetable. The occupation duration $[A_{t}^{macro}, B_{t}^{macro}]$ in network timetable is represented in Fig. 2. The occupation duration in station timetable is always extended to $[A_{t}^{micro}, B_{t}^{micro}$ ].

As shown in Fig. 3, track occupation in station consists of three parts:

Fig. 2

Network timetable.

Fig. 3

Occupation of track in station timetable.

Part 1: As soon as the inbound route $p_{m_{1}^{t}}$ is prepared, the track is occupied in order to ensure a smooth inbound movement without interruptions. The duration of movement can be calculated according to speed profile of trains, length of trains, length of tracks, length and gradient of routes.

Part 2: The occupation duration of part 2 is same as defined in network timetable.

Part 3: When trains start to leave the station, trains need to firstly leave the track. So during part 3, trains occupy both of tracks and outbound routes. $δ_{t}^{start}$ is calculated according to speed profile of trains and length of trains.

In our problem, we define the track occupation time [A_t, B_t [as below: $A_{t} = min_{m \in M^{t}} α_{m}$ $B_{t} = max_{m \in M^{t}} α_{m} + δ_{t}^{start}$

α_m is predicted according to the current traffic.

3 Routing & platforming modelling

In this section, we start to formalize the routing and platforming problem and establish an ILP model.

3.1 Notation: Sets and parameters

L ^e

Set of sections

L ⁱ

Set of tracks

L_{l^{e}}^{i}

Set of tracks accessible to the sections l_e

L_{t}^{Pref}

Set of tracks in preference order of train t

Set of switches

Set of routes

P ^m

Set of routes selectable for movement m.

P ^(l_i,l_e)

Set of routes connecting track l_i with Sections l_e

Set of trains

T ^assigned

Set of trains with fixed routes and tracks assignment

T ^new

Set of new arrival trains with flexible route and track assignment

Set of movements

M ^assigned

Set of movements with fixed routes assignment

M ^new

Set of movements with flexible route assignment

M ^t

Set of movements in chronological order of train t

M ^{l
_e}

Set of movements entering or leaving station from block section l_e

[α_m, β_m [

Occupation duration of routes for movement m.

[A_t, B_t [

Occupation duration of track for train t.

Y _p,p′

Pair of conflicting routes. If p∩ p′ ≠ ø, Y_p,p′ = 1. Otherwise 0.

C_{m, m'}^{M}

Pair of potential conflicting movements. If [ $α_{m}$ , $β_{m}$ [∩ [ $α_{m'}$ , $β_{m'}$ [≠ø, $C_{m, m'}^{refM} = 1$ .

Otherwise 0.

C_{t, t'}^{T}

Pairs of potential conflicting trains.

If [ $A_{t}$ , $B_{t}$ [∩ [ $A_{t'}$ , $B_{t'}$

[ $\neq ø, C_{t, t'}^{refT} = 1$ .

Otherwise 0.

X_{l, t}^{L^{i} T}

Fixed track assignment of trains. ∀t ∈ T^assign. If the track l_i is assigned to the train t, $X_{l, t}^{L^{i} T} = 1$ . Otherwise 0.

X_{p, m}^{PM}

Fixed route assignment of movements

∀ m ∈ M^assign. If the route p is assigned to the movement m, $X_{p, m}^{PM} = 1$ . Otherwise, 0.

3.3 ILP model

The optimization problem is formulated in Eqs. (1)–(8). The objective function is to minimize the number of conflicting trains, as expressed in (1).

3.2. Variables

$X_{l, t}^{L^{i} T}$

Track assignment of a train ∀t ∈ T^new

If the track l_i is assigned to the train t, $X_{l, t}^{L^{i} T} = 1$ . Otherwise 0.

X_{p, m}^{PM}

Route assignment of a movement. ∀m ∈ M^new. If the route p is assigned to the movement m, $X_{p, m}^{PM} = 1$ .

Otherwise, 0.

X_{m}^{CancelM}

Cancellation decision of a movement.

∀m ∈ M^new.

If m is cancelled, $X_{m}^{CancelM} = 1$ .

Otherwise 0.

X_{t}^{CancelT}

Cancellation decision of a train.

∀t ∈ T^new

If t is cancelled, $X_{t}^{CancelT} = 1$ .

Otherwise 0.

Constraint (2) confirms the consistency of cancellation decisions between owner train and its movements. Constraint (3) assures that each train t is only assigned once to a track from its preference set. Similarly, constraints (4) ensure that at most one route is selected for each movement from its set of available routes. Constraint (5) addresses the connection between choice of routes for a movement and choice of track for its owner train t. The track $l_{i} \in L_{l_{e}}^{i}$ is accessible to the section l_e. The route p ∈ P^(l_i,l_e) is accessible to the section l_e and the track l_i. At the same time, Constraints (3)(4) and (5) also ensure that trains and movements cancelled are not allocated with track and routes. Constraints (6) and (7) are only applied on pairs of trains and movements with potential time-space conflicts in order to avoid conflicts on tracks and crossing routes. Constraints (8) specify sign restrictions on binary variables. $min \sum_{t \in T^{new}} X_{t}^{CancelT}$ (1) $\begin{matrix} X_{m}^{CancelM} = X_{t}^{CancelT} \\ \forall t \in T^{new}, \forall m \in M^{t} \end{matrix}$ (2) $\begin{matrix} \sum_{l_{i} \in L_{t}^{Pref}} X_{l, t}^{L^{i} T} + X_{t}^{CancelT} = 1 \\ \forall t \in T^{new} \end{matrix}$ (3) $\begin{matrix} \sum_{p \in P^{m}} X_{p, m}^{PM} + X_{m}^{CancelM} = 1 \\ \forall m \in M^{new} \end{matrix}$ (4) $\begin{matrix} \sum_{p \in P^{(l_{i}, l_{e})}} X_{p, m}^{PM} + X_{m}^{CancelM} ⩾ X_{l_{i}, t}^{L^{i} T} \\ \forall t \in T^{new}, \forall l_{e} \in L^{e}, \forall m \in M^{l_{e}} \cap M^{t}, \forall l_{i} \in L_{l_{e}}^{i} \end{matrix}$ (5) $\begin{matrix} X_{p, m}^{PM} + X_{p^{'}, m^{'}}^{PM} ⩽ 1 \\ \forall m \neq m^{'} \in M, \forall p^{'} \in P^{m^{'}} \end{matrix}$ $s . t . [α_{m}, β_{m} [\cap [α_{m^{'}}, β_{m^{'}} [\neq ø, Y_{p, p^{'}}^{P} = 1$ (6) $\begin{matrix} X_{l, t}^{L^{i} T} + X_{l, t^{'}}^{L^{i} T} ⩽ 1 \\ \forall t \neq t^{'} \in T, \forall l \in L_{t}^{Pref} \cap L_{t^{'}}^{Pref} \end{matrix}$ (7) $s . t . [A_{t}, B_{t} [\cap [A_{t'}, B_{t'} [\neq ø$ $X_{l, t}^{L^{i} T}, X_{p, m}^{PM}, X_{m}^{CancelM}, X_{t}^{CancelT} \in {0, 1}$ (8)

4 Calculation process

This section introduces the calculation process, as shown in Fig 4, to solve the real-time routing and platforming problem. The inputs are station timetable, station layout, arrival and departure time.

The process has three steps:

Update sets and parameters according to the current traffic and station layout.

Check the feasibility of station timetable before preparing an inbound route for a new train..

If conflicts are detected, solve an optimal station timetable with routes and track assignment.

Fig. 4

Calculation process.

4.1 Step 1: Update

The station layout considered in our problem is dynamic. If equipment is breakdown or back to normal, the sets of tracks, routes, switches are recalculated. When a new skylight is delivered, relevant tracks and switches cannot be used during skylight. The station layout should be updated.

When a train nearly arrives at the station, the arrival time is update according to the distance and speed curve. The train is a new train with flexible route and track assignment, t ∈ T^new. While the inbound route is prepared for it, the train is no more a new train but a train with fixed route and track assignment, t ∈ T^assign.

For the trains on track, we update the departure time according to the process of train operations on tracks.

In our method, the station dispatcher set the problem scale. We could solve the routing and platforming problem in a whole day or within three hours. The problem scale define the train and movement set T and M.

The dynamical sets and parameters are summarized in Table 4.

Table 4
Sets and parameters update occasion

Occasion Update sets or parameters

Dynamic station layout Lⁱ, $L_{l^{e}}^{i}$ , $L_{t}^{Pref}$ , S, P, P^m, P^(l_i,l_e)

Dynamic network and station traffic [α_m, β_m [, [A_t, B_t [, $C_{m, m^{'}}^{M}$ , $C_{t, t^{'}}^{T}$

T^new, T^assign, M^new, M^assign, T, M

Occasion	Update sets or parameters
Dynamic station layout	Lⁱ, $L_{l^{e}}^{i}$ , $L_{t}^{Pref}$ , S, P, P^m, P^(l_i,l_e)
Dynamic network and station traffic	[α_m, β_m [, [A_t, B_t [, $C_{m, m^{'}}^{M}$ , $C_{t, t^{'}}^{T}$
	T^new, T^assign, M^new, M^assign, T, M

4.2 Step II: Feasibility check

While preparing an inbound route for a new train, the feasibility of current station timetable is rechecked. In the ILP model, all trains and movements have the fixed assignment of tracks and routs. Only the cancellation decisions of new trains are variables. If conflicts are detected in the station timetable, we go to the step III to reschedule the station timetable.

4.3 Step III: Generation of an optimal station timetable

By solving ILP model, the station timetable is rescheduled to the optimal solution. If the station timetable is feasible without conflicting trains, we update the current station timetable. If the optimal station timetable is still infeasible, the conflicting trains are pointed out.

5 Computational results

The experimental instances are generated based on the full-day timetable within real-world railway station which receives always the overload of trains’ activities. Set of tracks in preference order of trains are calculated with three different lengths (short, medium, long) and 16 types of trains which are described in terms of their directions and characters. As shown in Fig. 5, this station has 16 tracks, 10 sections and 144 routes.

Fig. 5

Topology of railway station.

Our resolution methods are implemented in commercial solver CPLEX C++ version12.6 to solve the integer linear programming model. The computation time is calculated in CPU seconds on this testing computer. Computational experiments have been conducted on a 64 bits computer under Linux with Intel i5-2520M CPU at 2.5 GHz and 8GB memory RAM.

This method is tested on 320 instances. We randomly choose a group of successive trains in a real timetable. The 320 instances include 16 different scenarios from 5 to 249 trains. The first column in Table 5 indicates the number of trains in each scenario. We generate 20 test cases for each scenario. From the second column GAP, we can see that all cased are solved to the optimal solution. The third column is the average number of conflicting trains. The infeasible cases can be handled. The average computational time of each scenario is resumed in the last column. The full-day problems of 249 trains are solved in 1.26 s. The efficiency of this method meets the time-critical nature of RT-TRPP.

Table 5

Computational results

Trains	GAP	Conflicting trains	Comp. time
5	0.00%	0	0.01
15	0.00%	0	0.04
25	0.00%	0.6	0.09
35	0.00%	0.9	0. 15
45	0.00%	1.5	0.17
55	0.00%	1.8	0.28
65	0.00%	2.1	0.28
75	0.00%	3.5	0.37
85	0.00%	3.1	0.43
95	0.00%	3.5	0.49
105	0.00%	4.5	0.45
115	0.00%	6.0	0.54
125	0.00%	5.2	0.60
135	0.00%	4.9	0.62
145	0.00%	6.3	0.76
249	0.00%	8.5	1.26

As described in Reference [5], if the layout of the railway station is fixed, then the safety optimization problem can be solved by a dynamic programming approach in an amount of time that is polynomial in the number of trains. In our problem, the layout of the railway station is dynamic. We divide and conquer the problem by three steps:

Update station layout.

Check feasibility.

Generate an optimal station timetable.

The dynamic station layout is updated in the first step. In the following step, the station layout is fixed. As shown in Fig. 6, the computation time is polynomial in the number of trains.

Fig. 6

Computational results.

If the current station receiving ability meets the traffic situation, our method provides an optimal routes and tracks assignment on real-time. If the station receives the overload of trains’ activities, our method points out the conflicting trains. Station dispatchers focus on solving the conflicting trains.

6 Conclusion

This paper deals with real-time trains routing and platforming problem faced by railway station manager to check the feasibility of station operating plan. The infeasibility is caused by the unreliable arrival times of freight trains, flexible shunting operations and dynamic station layout caused by equipment failure. Our goal is to maximize the number of trains passing through railway stations. If the conflicts are solvable, an optimal track and route assignment is given in a rather short time. If the conflicts are unsolvable, the conflicting trains are pointed out in order to ensure the rest of trains passing through stations on time. Station dispatchers concentrate on rescheduling the conflicting trains. An integer linear programming model is proposed to formalize this problem. A dynamic calculation process is designed to meet the real-time occasion. Computational results on different sizes of problem show that the optimal decision can be found in rather a short time. This method can be used both of on-line and off-line occasion to check the feasibility of station timetable.

In future works, we try to insert the conflicting trains into the station timetable. The rescheduling methods need to be explored.

Footnotes

Acknowledgments

This work was supported by the China Railway Joint Funds of the National Natural Science Foundation of China (Grant no. U1834211) and Science Foundation for Key Scientific research project of CARS (Grant no. 2020YJ040).

References

D’Ariano

, Pacciarelli

and Pranzo

, A branch and bound algorithm for scheduling trains in a railway network, European Journal Operational Research183(2) (2007), 643–657.

D’Ariano

, Pranzo

and Hansen

, Reordering and local rerouting strategies to manage train traffic in real time, Transportation Science42(4) (2008), 405–419.

Schrijver

and Steenbeek

, Dienstregeling ontwikkeling voor Railned (Timetable development for Railway station), C.W.I. Amsterdam, Netherlands, 1994.

Caimi

, Algorithmic decision support for train scheduling in a large railway network, Ph.D. Dissertation, ETH Zurich, 2009.

Kroon

, Romeijn

and Zwaneveld

, Routing trains through railway stations: Complexity issues, European Journal of Operational Research98 (1997), 485–498.

Kroon

and Zwaneveld

, STATIONS: Final report of phase 1, ERASM Management Report Series 201, Erasmus University Rotterdam, Rotterdam, Netherlands, 1995.

Carey

and Carville

, Scheduling and platforming trains at busy complex stations, Transportation Research Part A37(3) (2003), 195–224.

Serafini

and Ukovich

, Mathematical model for periodic scheduling problems, SIAM Journal on Discrete Mathematics, 2.

Zwaneveld

, Kroon

and Ambergen

, A decision support system for routing trains through railway stations, in Proceedings of Comp Rail 96, Computational Mechanics Publications, Southampton, Berlin, 1996, pp. 217–226.

10.

Zwaneveld

, Kroon

and Hoesel

S.V.

, Routing trains through a railway station based on a node packing model, Operational Research128 (2001), 14–33.

11.

Goverde

and Hansen

, Performance indicators for railway timetables, in Proceedings of IEEE international conference on intelligent rail transportation: ICIRT2013, Beijing, China, 2013, pp. 301–306.

12.

Watson

, The effects of railway privatization on train planning, Transport Reviews21(2) (2001), 181–193.

A real-time train routing and platforming problem in complex railway stations

Abstract

Keywords

1 Introduction

2 General description of the problem

2.1 Station layout

Table 3 Train activities and resource demand Train activities Resources Occupation duration Inbound movement Inbound route (switches) Track [ α m , β m [ Operation Track [ A t net , B t net [ Outbound movement Outbound route (switches) Track [ α m ′ , β m ′ [

2.4 Feasibility-checking

2.5 Network timetable & station timetable

3.1 Notation: Sets and parameters

3.3 ILP model

Table 4 Sets and parameters update occasion Occasion Update sets or parameters Dynamic station layout L i , L l e i , L t Pref , S, P, P m , P(l i ,l e ) Dynamic network and station traffic [α m , β m [, [A t , B t [, C m , m ′ M , C t , t ′ T T new , T assign , M new , M assign , T, M

4.3 Step III: Generation of an optimal station timetable

5 Computational results

Footnotes

Acknowledgments

References

Table 3
Train activities and resource demand

Train activities Resources Occupation duration

Inbound movement Inbound route (switches) Track [ $α_{m}$ , $β_{m}$ [

Operation Track [ $A_{t}^{net}$ , $B_{t}^{net}$ [

Outbound movement Outbound route (switches) Track [ $α_{m^{'}}$ , $β_{m^{'}}$ [