Using A* for Optimal Train Routing on Moving Block Systems

Classically, railway networks are separated into fixed blocks. To detect the status of a given block, tracks are equipped with Trackside Train Detection (TTD) hardware, e.g., axle counters. A train may only proceed into the next section if the entire block is unoccupied.

Trains equipped with a Train Integrity Monitoring (TIM) system can safely report their position. In that case, trains can follow each other at absolute braking distance without the need for any block sections²²2At the same time, we allow the existence of some TTD sections. They can be used to, e.g., provide basic flank protection around switches.. Moving Block control systems make use of this concept and are already implemented on some metro networks.

This work considers time-optimal train routing on railway networks equipped with a Moving Block control system. For this, we are given general timetable requests. Routing is the task of deciding on which specific track to use and when trains are moving; all constraints of the signaling system need to be fulfilled. In particular, we consider the tasks on a microscopic level. In theory, many different objectives are possible. We aim to optimize the respective travel time.

A* is an informed search algorithm (classically designed to find shortest paths on directed graphs). It functions similarly to Dijkstra’s algorithm but expands toward the destination more quickly by making use of a heuristic approximation of the remaining distance.

Let $G=(V,E,c)$ be a weighted graph, $s_0\in V$ an initial vertex (also called state in this context), as well as a set of terminal states $𝒯\subset V$. The task is finding the shortest path from $s_0$ to any vertex in $𝒯$. A* explores the graph starting from $s_0$. For every vertex $s\in V$, it keeps track of the shortest path from $s_0$ to $s$ found so far. We denote the length of this path by $g(s)$. Dijkstra would expand on the vertex with the smallest $g(\cdot )$. However, A* uses a different evaluation function. For every $s\in V$, we apply an efficiently computable heuristic function $h(s)$ approximating the shortest (remaining) distance from $s$ to $𝒯$. A* then explores the neighbors $\mathrm{\Gamma }(s)$ of the vertex with the smallest combined value $f(s):=g(s)+h(s)$. By doing this, the exploration is guided toward goal states.

In theory, we can use any heuristic function $h$. However, A* is only guaranteed to return optimal values if the heuristic meets certain conditions, namely, that $h$ never overestimates the actual cost. If $h$ satisfies a triangle-like inequality, A* can safely be terminated as soon as the first terminal vertex is explored (as specified in Algorithm 1).

Hart et al. [9] show Theorem 6 for the case of $\delta$-graphs, i.e., if there exists a $\delta >0$ such that $c(e)\ge \delta$ for every $e\in E$. However, this condition is only used to show termination in a weaker case, when $h$ is just admissible but not consistent. It is easy to verify that Algorithm 1 is optimal even for arbitrary (including negative⁴⁴4Note that $G$ cannot have negative cycles if there exists a consistent heuristic.) edge weights, see, e.g., [2, Theorem 2.9].

To use search algorithms, it does not suffice to encode only terminal states. Instead, we must also encode partial solutions that might lead to feasible solutions encoded by terminal states.

In contrast to terminal states (i.e., fully specified movements), $u_{out}^{({tr}_i)}\notin e_{k_i}^{({tr}_i)}$ and ${\widehat{m}}_i\ne m_i$ are possible. When simulating, it is assumed that, in such a case, trains stop at the end of their last specified edge and end their journey on the network. In the objective, the exit time of ${tr}_i$ is replaced by the time it reaches the end of $e_{k_i}^{({tr}_i)}$ with velocity 0. The state space, i.e., the “vertices” of the graph used in Section 2.3, is then given by the set of all (partial) solutions.

It remains to define transitions between states, i.e., the “edges” of the graph used in Section 2.3. Naturally, the initial state is given by the empty state, i.e., no train enters the network, with objective value 0. The target states $𝒯$ are all fully specified states corresponding to feasible train movements that respect all timetable requests.

The main idea is to traverse the state space edge by edge. Given any (partial) state $s$, we obtain possible successor states $s^{+}\in \mathrm{\Gamma }(s)$ by one of the following:

1. 1.

   Any single train stops at its current route end (if the respective edge is part of the next scheduled station).

2. 2.

   Any single train moves to any succeeding edge on the network.

3. 3.

   Any single train enters the network from outside.

The respective TTD- and vertex-orders are induced by the order in which these transitions were chosen to reach $s^{+}$ from the initial state. If a TTD is entered, the train is appended to the respective TTD-order; analog for entry and exit vertices.

Following this strategy, many intermediate states are created, even if there is only one plausible decision to continue with. Note that trains cannot overtake or cross on single-track lines without turnouts. Hence, train movements of more than one edge can be safely assumed until the next switch is reached. Doing so can reduce the number of states explored by skipping unnecessary intermediate steps.

For any state $s$, we can simulate the movements of each train (Assumption 11). Let ${\overline{t}}_i$ be the time at which ${tr}_i$ either exits the network or reaches the end of its route as specified by the (partial) state $s$. We define

Note that for any terminal state $t\in 𝒯$, $g(t)$ coincides with the objective value of the corresponding feasible (but not necessarily optimal) solution to Problem 3. Furthermore, its value does not depend on specific state transitions but is the same regardless of which path was taken to reach a particular state, as all relevant information for simulation is contained in the state itself. We do not define the transition costs $c(s,s^{+})$ explicitly, but they are implicitly given by

Usually, $c(s,s^{+})>0$ will hold. However, for terminal $t\in 𝒯$, $c(s,t)\le 0$ is theoretically possible because the train is not forced to stop at the exit vertex in contrast to the end of partial routes in intermediate states. However, this is not a problem because we will handle this by choosing a sensible heuristic $h(s)$.

To guide the search algorithm, we need suitable edge weights and an optimistic heuristic estimating the lowest cost $g^{\ast }(s,𝒯)$ from any state $s$ to the nearest terminal. For this, we estimate the remaining time for every individual train ${tr}_i$ with $h_i(s)$. If a train has already reached its exit vertex, we have $h_i(s)=0$. Otherwise, let ${\tau }_i^{\ast }(p_1,p_2)$ be the minimal running time for ${tr}_i$ between any two points⁸⁸8not necessarily vertices on the railway network $𝒩$, ignoring headway constraints induced by other trains. Let ${\widehat{\tau }}_i(p_1,p_2)$ be an optimistic approximation, i.e., $0\le {\widehat{\tau }}_i(p_1,p_2)\le {\tau }_i^{\ast }(p_1,p_2)$, which still fulfills the triangle inequality

For $e=(u_0,u_1)\in E$ a natural and easy to compute choice is

i.e., assuming a train always moves at the maximum speed, disregarding constraints on acceleration and deceleration. In general, we can induce any ${\widehat{\tau }}_i(p_1,p_2)$ as the quickest path from $p_1$ to $p_2$ by using the edge timings ${\widehat{\tau }}_i(e)$ defined in Equation 4.

However, we do not use ${\widehat{\tau }}_i$ directly as a heuristic. Recall that $h_i(s)$ should estimate $g^{\star }(s,𝒯)$ and be optimistic. However, in state $s$, ${tr}_i$ might be forced to slow down because it has to stop at the end of its partially defined route. This is not the case in a terminal state $t\in 𝒯$, so the actual travel time difference can be less than ${\tau }_i^{\star }(s,t)$. However, this can easily be incorporated into the heuristic. Consider Figure 4(b) and assume that at point $p_0$ and time $t_0$, a train starts to decelerate only because it has to stop at the end of its partial route. While braking, it traverses vertices $u_1,u_2,\mathrm{\dots },u_j$ and finally stops at $u_j$ at time $t_j$. These values can be easily returned from the (black-box) simulator while determining $g(s)$ (Equation 1). In a terminal state, ${tr}_i$ might not be forced to slow down at $p_0$, but could potentially follow the orange speed profile in Figure 4(b). Because of this, it would reach $u_j$ earlier than $t_j$ in this terminal state, and the final exit time might be less than $t_j+{\tau }_i^{\star }(u_j,u_{out}^{({tr}_i)})$. We need to adjust for the time that $t{r}_i$ could reach $u_j$ earlier than $t_j$ in any terminal state reachable from $s$. This can be achieved by defining

Finally, we combine these individual heuristics into the final $h$ used in Algorithm 1:

The heuristic presented in Section 4.3 can be further extended to approximate the remaining time more accurately by using more information provided by Problem 3. Note that the train has to visit a specified list of stations before leaving the network, so it might not be possible for a train to take the quickest route anyway. Assume that in state $s$, ${tr}_i$ has not stopped in stations ${𝒮}_l,\mathrm{\dots },{𝒮}_{m_i}$ yet, i.e., ${\widehat{m}}_i=l-1$ in Definition 9, then we can update Equation 7 to

where

is the natural extension of ${\widehat{\tau }}_i$ to distances between sets.

Moreover, Problem 3 provides information on the earliest departure times. Since the train is not allowed to leave before that time, we can already incorporate this into the heuristic. For this, set

For any future station, we can already incorporate the earliest departure times of the previous station by

and, finally,

For simplicity, we use a time discretization of $\mathrm{\Delta }t:=6\mathrm{s}\text{/}$, which seems to be the standard time between two consecutive train position reports [3, Section 7.5.1.143]. For every time step $t\in \{0,6,\mathrm{\dots }\}$, we keep track of the velocity $v_t^{(tr)}\in [0,v_{max}^{tr}]$ and position⁹⁹9The position refers to the front of the train. The rear end can be directly induced from its length. $x_t^{(tr)}$ of each train. In between, we assume linear movement; hence,

Assume that at time $t$, the signaling system allows a train to move at most a distance ${\overline{x}}_t^{(tr)}$ (moving authority). Using basic laws of motion, the braking distance of a train at speed $v$ is given by $\frac{v^2}{2\ast d_{max}^{(tr)}}$, hence,

and, thus,

In general, we will set $v_{t+\mathrm{\Delta }t}^{(tr)}=\nu (v_t^{(tr)},{\overline{x}}_t^{(tr)})$ by Assumption 7 unless there are further constraints on the maximal velocity (see Section 5.3).

There are four main reasons why the moving authority may be restricted. They are exemplarily depicted in Figure 6(a).

A train may only advance to the rear of a preceding train, its next scheduled stop position, or the beginning of a TTD section, which the preceding train has not fully cleared yet. In order to enforce speed constraints on future edges (that are not reachable within one timestep¹⁰¹⁰10refer to Section 5.3 in that case), we restrict the moving authority by the point at which the train would stop if it decelerates at full rate just after entering the edge at its speed limit.

Finally, there are some cases where it is more natural to restrict the speed directly instead of incorporating it into the moving authority, in which case we might not be able to set $v_{t+\mathrm{\Delta }t}^{(tr)}=\nu (v_t^{(tr)},{\overline{x}}_t^{(tr)})$. Naturally, the speed is restricted by the speed limit of the current edge (and any edge that can be reached within one timestep) as well as the train’s maximal velocity. Moreover, by maximal acceleration, $v_{t+\mathrm{\Delta }t}^{(tr)}\le v_t^{(tr)}+a\cdot \mathrm{\Delta }t$ The most complex restriction is to ensure that a train can leave the network at its target velocity, but only at a time $\ge {\underset{¯}{t}}_{out}^{(tr)}$. In that case, a train might need to slow down in order not to arrive at the exit too early but still have enough distance left to accelerate to the target exit velocity $v_{out}^{(tr)}$ before leaving the network. Assume that $v_{t+\mathrm{\Delta }t}^{(tr)}$ is fixed, then it is easy to calculate the maximal possible runtime to the exit node by assuming that the train decelerates until the point where it has to accelerate again to reach the target velocity at exit. Trying difference values for $v_{t+\mathrm{\Delta }t}^{(tr)}$, they can either lead to an exit at time $\ge {\underset{¯}{t}}_{out}^{(tr)}$ (green lines in Figure 6(b)), at time (orange lines) or the target velocity cannot be attained at exit (red lines). Using binary search, we choose the largest value for $v_{t+\mathrm{\Delta }t}^{(tr)}$ that still leads to an exit at time $\ge {\underset{¯}{t}}_{out}^{(tr)}$.