Constraint-Based In-Station Train Dispatching

Figure 1 provides an example structure of a railway station. A railway station can be represented as a graph, composed by a set of connected track segments, i.e., the minimal controllable rail units. Their status can be checked via track circuits, that provide information about occupation of the segment and about corresponding timings. Track segments can be divided into two classes, stopping points and interlocking. A stopping point is a track segment in which a train can stop: this is possible if there is a connected platform, i.e., a point in the station used to embark/disembark the train (in green in Figure 1), or at the entrance and the exit points of the railway station (indicated as E and W in the figure). Entry points are segments where the train stops before being allowed to enter into the station (or queues behind other trains); similarly, exit points allow the train to leave the station and enter the outside railway network.

Sequences of connected track segments are organised in itineraries: this is manually done by experts at the specific railway station. While track segments are the minimal controllable units of a station, itineraries describe paths that the trains will follow in order to move within the station. Semaphores are positioned in the station at specific points, and that are the only points at which trains are allowed to stop, usually signalling the beginning and the end of an itinerary. Intuitively, trains are only allowed to stop at the end of an itinerary, where semaphores are placed. For example, all trains in Figure 1 consists of two itineraries. The first one from the station entrance to the end of the platform in their direction and the second one, the first track segment after the end of the platform till the station exit.

A track segment can be occupied by a single train at the time. For safety reasons, a train is required to reserve an itinerary, and this can be done only if the itinerary is currently not being used by another train. While a train is navigating the itinerary, the track segments left by the train are released. This is done to allow trains to early reserve itineraries even if they share a subset of the track segments. A train occupies a track segment for a duration that depends on many variables; e.g., type of the train, length of the train, position of the segment within the itinerary, and weather. Based on historical data, when available, corresponding values can be estimated for planning purposes. A train going through the controlled railway station is running a route in the station, by reserving an itinerary and moving through the corresponding track segments.

Finally, a timetable is the schedule that includes information about when trains arrive at the controlled station, when they arrive at a platform, and the time when they leave a platform. Figure 2 shows a non-overlapping schedule of three trains moving across the station from Figure 1. We show temporal reservations for itineraries leading to and leaving from each platform. In this example, the orange train overtakes the red train via Platform 3. Currently, human train dispatchers rely on tools to visualise the conditions of the controlled station. When making re-scheduling decisions they use data such as occupied track segments (similar to Figure 2), timetable information and extensive communication with train drivers and personnel in the station. Dispatchers operate in real-time and mostly on a reactive basis, according to the arrival time of trains. They are guided by an intuitive understanding about the quality of potential decisions and their knock-on effects.

The in-station train dispatching problem can be characterised by the tuple $(T,E)$, where $T=\{1,2,\mathrm{\dots }\}$ is the set of trains and $E=\{1,2,\mathrm{\dots }\}$ is the set of track segments in the station. A train $t\in T$ is specified by its earliest start time ${\underset{¯}{s}}_t^T\in \mathbb{Z}$, and a set of possible routes $R_t\subseteq \mathbb{Z}$ through the station.

For the purposes of our model, we distinguish between four train types $y_t^T\in \{\text{std},\text{ori},\text{des},$ $\text{van}\}$. Here std is a standard train that enters and exits the station, to and from the external network; ori is an origin train that start at a platform from the beginning of the planning horizon and subsequently exits the station; des is a destination train that enters the station, terminates at a platform, and occupies the platform for the remaining planning horizon, and; van is a vanishing train that enters the station, terminates at a platform, and “vanishes” from the station after completing its stop. A vanishing train models the case when the train leaves the station into the train yard or side-track, which is assumed to always have enough capacity.

A route $r\in R_t$ of a train $t$ is a sequence of itineraries forming the path of the train through the station. Its grounded representation is modelled as a sequence of temporal reservation blocks $B_r=\{i,i+1,\mathrm{\dots },j\}$, where $i,j\in \mathbb{Z}$ and , and the integers represent the indices of the blocks. A block $b\in B_r$ of route $r$ specifies a track segment $e_b^B\in E$ and a reservation duration $d_b^B\in {\mathbb{Z}}_0^{+}$, excluding dwell time (defined below). A train occupies a block $b$ starting from the sum of the end time of its previous block in the sequence $B_r$ and a start offset time $o_b^B\in \mathbb{Z}$. If $b$ is the first block in the sequence, the start offset time is zero.

When moving through a platform, a train has a minimal dwell time ${\underset{¯}{l}}_r^R\in {\mathbb{Z}}_0^{+}=\{0,1,\mathrm{\dots }\}$. We note that even if a train does not take passengers at the station, it might be allowed to stop at the platform, e.g., waiting for a green signal or a passing of another train through a different platform. However, the minimal dwell time is zero. Similarly, we also define a minimal duration for a train to move through the station $d_r^R\in \mathbb{Z}$, excluding the dwell time. As dwell times are optional, we use a Boolean parameter $p_b^B\in \{\top ,\perp \}$ which is true ($\top$) if the block $b$ can contain a non-zero dwell time (i.e., if the train can stop at the block’s segment $e_b^B$) and false ($\perp$) otherwise; the parameter $t_b^B\in T$ refers to the corresponding train. We denote by $B$ the union of all blocks, i.e., ${\bigcup }_{t\in T}{\bigcup }_{r\in R_t}{B}_r$.

Redundant constraints are additions to a model that do not change the solution space, but which might provide additional propagation for a CP solver. A potential weakness of our model are the non-overlapping constraints (1), for which the start time variables are optional when the train has multiple routes through the station. To introduce redundant constraints we observe that railway stations have a “regular” pattern (e.g., tracks are parallel, “parallel” track segments have similar length and similar position in their itinerary). We model these “parallel” track segments using the global constraint $\mathrm{𝖼𝗎𝗆𝗎𝗅𝖺𝗍𝗂𝗏𝖾}$ [1]. For instance, Figure 3 shows a possible separation of track segments by vertical lines. These vertical lines split the station in 13 columns, for which one can impose a redundant constraint for each. We note that a segment can be part of multiple columns.

Let $C$ be the set of columns, $E_c^C\subseteq E$ a set of segments in the column $c$ and $T_c^C\subseteq T$ the set of trains that have at least one route through the column. Then, we model the redundant constraints as follows for a column $c\in C$ with $|T_c^C|>|E_c^C|$.

Constraint (21) creates one mandatory “master” task with the start time variable ${𝐬}_t^c$ and duration variable ${𝐝}_t^c$ for each train $t\in T_c^C$ passing through the column $c$ by linking both variables to their corresponding blocks’ optional start time variables and duration variables from the different routes of the train $t$. The global constraint $\mathrm{𝖺𝗅𝗍𝖾𝗋𝗇𝖺𝗍𝗂𝗏𝖾}$ is used, which ensures that at most one of the blocks’ optional start time variable is present in a solution and, if so, then ${𝐬}_t^c={𝐬}_{b^{\prime }}^B$ and ${𝐝}_t^c={𝐝}_{b^{\prime }}^B$ where $b^{\prime }$ is the “present” block (i.e., the block belonging to the chosen route); otherwise, ${𝐬}_t^c$ is absent. In our case, ${𝐬}_t^c$ is present, which forces that exactly one of the blocks’ start time variable is present. Constraint (22) imposes a minimum duration on the “master” task duration, but it might be redundant to (21) if the solver natively supports the global constraint $\mathrm{𝖺𝗅𝗍𝖾𝗋𝗇𝖺𝗍𝗂𝗏𝖾}$. Constraint (23) ensures that at most $|E_c^C|$ trains use one of the segments in $E_c^C$ at any time by setting a task with a start variable ${\widetilde{𝐬}}_t^c$, duration variable ${\widetilde{𝐝}}_t^c$, and a resource requirement of $1$ for each train $t$. These variables are then connected to their “master” task’s variables ${𝐬}_t^c$ and ${𝐝}_t^c$ in the constraints (24–26) depending whether the train can have a stop in the column and its train type similar to the constraints (2–4) on page 2.

So far, we characterise a column $c$ via its set of “parallel” segments $E_c^C$, but we did not specify how we determine this set because it may not contain all “parallel” segments. There are cases in which “parallel” segments belong to different columns because there is no overlap in trains using these “parallel” segments. We determine the set of columns by computing the connected components in an undirected graph for each set of “parallel” segments, where a node represents one “parallel” segment and two nodes are connected if there exists a train having two routes using the corresponding “parallel” segments. Such a partitioning of “parallel” segments leads to stronger redundant constraints.

While the planning method in [6] is tailored to only provide a good first solution and cannot be easily adapted to an optimisation method, for limits of both modelling and solving phases, our model is flexible in this sense, and we can explore different objectives while using the same constraint-based model. We explore three distinct objectives.

satis

first solution subjected to (1–20) and the redundant constraints (21–26) for columns under consideration

makespan

$\min {\max }_{t\in T}({𝐬}_t^T+d_{{𝐫}_t^T}^R+{𝐰}_t^T)$ subjected to (1–20) and the redundant constraints (21–26) for columns under consideration

endtimes

$\min {\sum }_{t\in T}({𝐬}_t^T+d_{{𝐫}_t^T}^R+{𝐰}_t^T)$ subjected to (1–20) and the redundant constraints (21–26) for columns under consideration

While the objective satis is the same as the planning method, makespan optimises the trains at the end of the planning horizon so that all trains exit the station as earliest as possible with less interference to the next planning horizon, and endtimes optimises the total amount of end times, which relates to minimising the total amount of delay. We highlighted that we only need to change one line of MiniZinc to change the solution objective. Thus, it would be easy to explore more objectives, e.g., minimising delays and the lexicographical optimisation of minimising the makespan and then the sum of end times.

In CP, search strategies can have a significant impact on the solution quality and the solving efficiency. We explore different search strategies only over all the decision variables. For readability, we describe the strategies in the MiniZinc language as search annotations, in which the MiniZinc arrays start, route, and dwell contain the start time (${𝐬}_t^T$), the route (${𝐫}_t^T$), and the dwell time (${𝐰}_t^T$) variables for all trains $t$, respectively.

standard

The standard search (Listing 1) assigns all start time variables before assigning the route and dwell time variables. The search incentivises the earliest start of all trains while keeping the route and dwell time flexible by selecting the train with the earliest possible start time in ${𝐬}_t^T$ and assigning this time to the variable.

fixed-order

The fixed-order search (Listing 2) groups the three decision variables of a train together and assigns them first in the order of start time, route, and dwell time before fixing the variables of the next train. The trains are sorted in non-descending order of the trains’ earliest start time ${\underset{¯}{s}}_t^T$. Compared to the standard search, it fixes all variables of train, meaning that all corresponding block start time variables become present, and a solver can perform stronger propagation of the non-overlapping constraints earlier in the search. However, the fixed order of the trains does not incentivise the earliest start of all trains as the standard search.

priority

The priority search (Listing 3) combines the standard and fixed-order search by grouping the train’s decision variables as in the fixed-order search and selecting the train with the earliest possible start time in ${𝐬}_t^T$. However, the priority search [11] is not part of MiniZinc distribution and is only supported by Chuffed among the four considered solvers.

free

The “free” search is a solver-specific generic search, which differs between solvers. For some solvers, it can be combined with a user-defined search at the solver’s discretion (e.g., Chuffed [9, 10] switches between both searches when restarting).

restart

For learning solvers as, e.g., Chuffed, a search can be combined with a restart policy, in which the solver restarts the search after a given number of failures are encountered in the search. We explore a geometry restart policy with a factor $1.5$ and a base $100$, in which the first restart is triggered after $100$ failures and the $n$-th restart after $100\cdot {1.5}^{n-1}$.

Tables 2 and 1 show the results of different combinations of solvers and search strategies, and different options for using redundant constraints. Table 1 lists the results for the objective makespan while Table 2 for endtimes. If a search strategy has the postfix “+” then it was combined with the restart policy restart. For each combination (a row in the table), we highlight the best performing option for the redundant constraints in italic, where an option is better than another one if it finds solutions for more instances (i.e., the sum of optimal and suboptimal solutions) or its average runtime is faster in the case of a tie. If this combination is also the best performing across all search strategies for a solver, then it is shown in bold. We test these five options for redundant constraints: (none) no redundant constraints, (border) only redundant constraints on columns bordering the external railway network, (platform) only redundant constraints on columns with track segments at platforms, (b+p) options (border) and (platform), and (all) redundant constraints on all columns.

The planner [6] applies a dedicated search heuristic method for finding a first solution with a minimal flow-on impact beyond the station. First, we compare the planner to the best solver combination on the quality of the first solution found regarding their makespan and their sum of end times, and then to the best solution found within the runtime limit.

For the first comparison, the solvers used the solution objective satis, and these solver combinations: Chuffed and CP-SAT with fixed-order search and no redundant constraints, and CP Optimizer and Gurobi with free search and no redundant constraints. Figure 4 shows the cumulative differences between the best known objective value for the makespan (Figure 4(a)) and the sum of end times (Figure 4(b)) and the solvers’ first solution. While the planner does not find a solution for 13 instances, when it found a solution it was always so good as the solutions of other solvers and better than the other solutions for some instances in terms of the makespan and the sum of end times. Unsurprisingly, Chuffed and CP-SAT using the fixed-order search, which incentivised scheduling trains as earliest as possible, are competitive to the planner. While CP Optimizer and Gurobi first solution quality are understandingly much worse. Overall, Chuffed performs the best in comparison to the other solvers and planner, because it quickly finds a solution for each instance while incurring sometimes a small cost in the solution quality compared to the planner. We note that when only considering the instances for that CP-SAT does not terminate in an error, CP-SAT is the best performing solver.

The considered planner, as all systems solving PDDL+ planning instances, works in satisfying mode, i.e. it terminates after finding the first solution. It cannot be easily modified to operate in the so-called anytime mode, where better solutions are found over time. In our approach, we only have to change the solution objective to one of the two minimisation objectives to find better solutions over time. We used the best solver combinations identified in the previous section, which are highlighted in bold in Tables 1 and 2. In addition to these combinations, we also use Gurobi’s option to warm start their search by passing in the first solution found by Chuffed using the search strategy fixed-order and no redundant constraints to overcome Gurobi’s difficulty to finding a solution for all instances. Figure 5 shows plots of the cumulative differences between the best known objective value for the makespan (Figure 5(a)) and the sum of end times (Figure 5(b)) for the solvers’ best found solution within five minutes. It is clear that providing more solving time, all solvers find much better solutions than the planner on the harder instances. This highlights that a significant reduction of train delays can be made when the search continues after a first solution is found. Warm starting Gurobi with Chuffed’s first solution has not only solved the issue with finding a solution for all instances, but also significantly increased its performance so that it is the best performing solver for both objectives. For minimising the makespan (the sum of end times) it optimally solved 146 (137) instances and found a feasible solution for the remaining 4 (13) instances while having an average runtime of $18$ ($36$) seconds.