Train Scheduling with Hybrid Answer Set Programming^††thanks: This is a substantially extended and revised version of (Abels et al. 2019).^††thanks: This work was partially funded by DFG grants SCHA 550/9 and 11.

The train scheduling problem can essentially be divided into three distinct tasks: routing, conflict resolution and scheduling.

First, train lines are routed through a railway network. One such network is given in Figure 1. By and large, it is a directed graph containing nodes 1 through 12 with edges in between, for instance, $(2,3)$ and $(10,12)$. Given this directed graph, we assign paths through the network to three train lines, viz. $t_{1}$, $t_{2}$ and $t_{3}$. Each train line is assigned an acyclic subgraph capturing its travel trajectory. In our example, the subgraphs for $t_{1}$, $t_{2}$ and $t_{3}$ are indicated by solid, dotted and dashed edges, respectively. Note that $(10,12)$ belongs to the subgraph of both $t_{1}$ and $t_{3}$. We see that $t_{1}$ has several different start nodes, viz. 1 and 2, and end nodes, viz. 11 and 12, whereas $t_{2}$ and $t_{3}$ have no alternative routes. One possible solution to the routing task in Figure 1 is represented by edges colored blue, red and green marking valid paths for $t_{1}$, $t_{2}$ and $t_{3}$, respectively

Second, edges in the network are assigned resources representing, for example, the physical tracks or junctions that can only be passed by a single train at once. Whenever two train lines share edges assigned the same resource, a decision has to be made which train line passes first. In our example, we assume that each edge is assigned a resource representing the physical track. Furthermore, we have two junctions, $\mathit{sw}_{1}$ and $\mathit{sw}_{2}$, that are assigned five edges each. More precisely, $\mathit{sw}_{1}$ is assigned to $(1,3),(2,3),(3,5),(3,6)$ and $(4,3)$, and $\mathit{sw}_{2}$ to $(8,10),(9,10),(10,11),(10,12)$ and $(10,7)$. The junctions highlight a common structural property of train scheduling instances on which we rely heavily to reduce the amount of decisions that have to be made to resolve resource conflicts. Let us focus on $\mathit{sw}_{2}$ and the resource conflicts of the three train lines in edges $(8,10),(9,10),(10,7),(10,11)$ and $(10,12)$. Instead of deciding each pair of edges with shared resources individually, we can decide which train line enters a set of edges assigned $\mathit{sw}_{2}$ first. More precisely, we decide in which order $t_{1}$, $t_{2}$ and $t_{3}$ enter $\{(8,10),(10,11),(10,12)\}$, $\{(10,7)\}$ and $\{(9,10),(10,12)\}$, respectively. This is possible because train lines using the same resource cannot overtake each other once they are within these sets of edges. We call such sets resource areas. Note that while it is obvious in our example what said areas are (they are equal to the full set of assigned edges for each resource and train line), this may not be the case in general. For instance, there are many alternative paths in complex train stations, and thus shared resources might be visited several times enabling train lines to overtake one another.

Finally, a schedule has to be created that assigns each train line an arrival time at all nodes in its path. A valid schedule has to respect a variety of timing constraints, ranging from earliest and latest arrival times at nodes, traveling and waiting times on edges, resource conflicts between train lines, to connections between train lines.

Figure 2 shows the earliest and latest arrival times for nodes of the valid paths of Figure 1. This is indicated by the light blue, red and green areas for train lines $t_{1}$, $t_{2}$ and $t_{3}$, respectively. For instance, $t_{2}$ may arrive at node 10 at the earliest at time point 0 and at the latest at time point 360 or $t_{1}$ at node 5 between 360 and 660. Furthermore, Figure 2 shows a valid schedule for train lines $t_{1}$, $t_{2}$ and $t_{3}$ as indicated by the blue, red and green lines, respectively. This schedule results from the decisions that $t_{2}$ and $t_{3}$ enter $\mathit{sw}_{1}$ before $t_{1}$ and, conversely, that $t_{1}$ enters $\mathit{sw}_{2}$ before $t_{3}$. Each resource conflict is resolved by a timing constraint indicating that the following train line enters the resource only after the preceding train line has left it plus a safety period. In our example, this safety period, as well as the travel time for each edge, is 60 seconds. This is reflected in the schedule since $t_{2}$ starts at 0 in node 10 and proceeds to node 7 at 60, and $t_{1}$ only enters $\mathit{sw}_{1}$ at node 2 a minute after $t_{3}$ has left it at node 6.

In our example, there are three connections. Our concept of connections captures transfer of passengers and cargo in various contexts, as well as the transfer of physical trains between train lines. The latter enables us to express cyclic train movements as can be seen with the connection of $t_{2}$ to $t_{3}$ on edges $(4,3)$ and $(3,6)$. We call such a connection collision-free since resource conflicts are disregarded on all connected edges that share the same resource, and the connection furthermore requires both train lines to arrive at node 3 at the exact same time point. This connection expresses that the same physical train is used for train line $t_{2}$ and $t_{3}$ and seamlessly transitions at node 3.²²2For simplicity, we assume that collision-free connections are already given with a transitive closure of all adjacent edges of the same resource and all possible other collision-free connections of other trains of that resource. The results are reflected in the connected paths in Figure 1 and the same arrival time at node 3 in Figure 2. The two other connections from $t_{1}$ to $t_{3}$ on either edges $(10,11)$ and $(10,12)$ or $(10,12)$ and $(10,12)$, on the other hand, capture a possible transfer of passengers or cargo from train line $t_{1}$ to $t_{3}$. The connection requires $t_{3}$ not to arrive at 12 before $t_{1}$ has arrived by at least one minute at 10 so that a transfer is possible. Since this connection does not disable resource conflicts, this can only be achieved if $t_{1}$ precedes $t_{2}$ through $\mathit{sw}_{2}$ which makes $t_{2}$ wait between nodes 6 and 9 until $t_{1}$ has left.

After obtaining a valid routing and scheduling, the solution is evaluated regarding the delay of the train lines and the quality of the paths they have taken. The former is calculated by summing up the delay of each train line at each node in their paths. For that purpose, a time point is defined after which the train line is considered delayed at a node. In Figure 2, these time points are indicated by lines $d_{t_{1}},d_{t_{2}}$ and $d_{t_{3}}$. For instance, $t_{3}$ is delayed at nodes 9, 10 and 12, thus accumulating a penalty of $120+120+120=360$. For the quality of the routes, penalties are assigned to edges and accumulated for every train line traveling that edge. Such penalties may indicate tracks that can manage less workload, are in need of maintenance, or are known to be a detour, and therefore to be avoided if possible. In our example, only edge $(1,3)$ is assigned a penalty of one, other edges are assumed to have a penalty of zero, therefore our routing is optimal and accumulates no routing penalties.

We formalize the train scheduling problem as a tuple $(N,T,C,F)$ having the following components:

• •

  $N$ stands for the railway network $(V,E,R,m,a,b)$, where

  • –

    $(V,E)$ is a directed graph,

  • –

    $R$ is a set of resources,

  • –

    $m:E\rightarrow\mathbb{N}$ assigns the minimum travel time of an edge,

  • –

    $a:R\rightarrow 2^{E}$ associates resources with edges in the railway network, and

  • –

    $b:R\rightarrow\mathbb{N}$ gives the time a resource is blocked after it was accessed by a train line.

• •

  $T$ is a set of train lines to be scheduled on network $N$.

  Each train in $T$ is represented as a tuple $(S,L,e,l,w)$, where

  • –

    $(S,L)$ is an acyclic subgraph of $(V,E)$,

  • –

    $e:S\rightarrow\mathbb{N}$ gives the earliest time a train may arrive at a node,

  • –

    $l:S\rightarrow\mathbb{N}\cup\{\infty\}$ gives the latest time a train may arrive at a node, and

  • –

    $w:L\rightarrow\mathbb{N}$ is the time a train has to wait on an edge.

  Note that all functions are total unless specified otherwise and we use seconds as time unit.

• •

  $C$ contains connections requiring that a certain train line $t^{\prime}$ must not arrive at node $n^{\prime}$ before another train line $t$ has arrived at node $n$ for at least $\alpha$ and at most $\omega$ seconds.

  More precisely, each connection in $C$ is of form $(t,(v,v^{\prime}),t^{\prime},(u,u^{\prime}),\alpha,\omega,n,n^{\prime})$ such that $t=(S,L,e,l,w)\in T$ and $t^{\prime}=(S^{\prime},L^{\prime},e^{\prime},l^{\prime},w^{\prime})\in T$, $t\neq t^{\prime}$, $(v,v^{\prime})\in L$, $(u,u^{\prime})\in L^{\prime}$, $\{\alpha,\omega\}\subseteq\mathbb{Z}\cup\{\infty,-\infty\}$, and either $n=v$ or $n=v^{\prime}$, as well as, either $n^{\prime}=u$ or $n^{\prime}=u^{\prime}$.

• •

  Finally, $F$ contains collision-free resource points for each connection in $C$.

  We represent it as a family $(F_{c})_{c\in C}$.

  Each resource point in $F_{c}$ is of form $(t,(v,v^{\prime}),t^{\prime},(u,u^{\prime}),r)$ and expresses that two train lines $t$ and $t^{\prime}$ are allowed to share the same resource $r$ on edges $(v,v^{\prime})$ and $(u,u^{\prime})$. Connections removing collision detection are used to model splitting (or merging) of trains, as well as reusing the whole physical train between two train lines. More importantly, this allows us to alleviate the restriction that subgraphs for train lines are acyclic, as we can use two train lines forming a cycle that are connected via such connections. This can be observed in Figure 1, where $t_{2}$ and $t_{3}$ are connected like so.

  We suppose the following conditions

  	$\displaystyle(t,(n,v),t^{\prime},(u,u^{\prime}),r)$	$\displaystyle\in F_{c},\text{ if }(n,v)\in L\cap a(r),$
  	$\displaystyle(t,(v^{\prime},n^{\prime}),t^{\prime},(u,u^{\prime}),r)$	$\displaystyle\in F_{c},\text{ if }(v^{\prime},n^{\prime})\in L\cap a(r),$
  	$\displaystyle(t,(v,v^{\prime}),t^{\prime},(m,u),r)$	$\displaystyle\in F_{c},\text{ if }(m,u)\in L^{\prime}\cap a(r),\text{ and}$
  	$\displaystyle(t,(v,v^{\prime}),t^{\prime},(u^{\prime},m^{\prime}),r)$	$\displaystyle\in F_{c},\text{ if }(u^{\prime},m^{\prime})\in L^{\prime}\cap a(r).$

  These assumptions ensure that adjacent edges sharing the same resource are always collision-free resource points for that connection, because otherwise the connections could not be made if resources span over several edges. To illustrate this, consider two trains lines $t_{a}=(\{1,2\},\{(1,2)\},e,l,w)$ and $t_{b}=(\{2,3,4\},\{(2,3),(3,4)\},e^{\prime},l^{\prime},w^{\prime})$ that reuse one physical train. All edges have a minimal travel time of six seconds and the same resource $r$ with a block time of ten seconds. To facilitate a seamless transition from one train line to another, a connection $(t_{a},(1,2),t_{b},(2,3),0,0,2,2)$ is used where both train lines blend into each other. As both train lines ought to use the same physical train, a collision-free point $(t_{a},(1,2),t_{b},(2,3),r)$ is needed to allow the connection at the given edges. This collision-free point alone is not sufficient, since $t_{b}$ would have to wait for four seconds at edge $(3,4)$ for the release of the resource $r$, blocked by $t_{a}$ at edge $(1,2)$. This is due to the fact that the blocked time of ten seconds is larger than the minimal travel time of six seconds. Therefore, the collision-free point $((t_{a},(1,2),t_{b},(3,4),r))$ is necessary to correctly execute the connection as intended, that is, modeling one physical train among multiple train lines.

For our example in Figure 1 and Figure 2, the train scheduling problem is defined as

• •

  $V=\{1,\dots,12\}$,

  • –

    $E=\{(1,3),(2,3),\dots,(10,11),(10,12)\}$,

  • –

    $R=\{\text{$\mathit{sw}_{1}$},\text{$\mathit{sw}_{2}$}\}\cup\{r_{e}\mid e\in E\}$,

  • –

    $m(e)=60$ and $a(r_{e})=\{e\}$ for $e\in E$,

  • –

    $a(\mathit{sw}_{1})=\{(1,3),(2,3),(4,3),(3,5),(3,6))\}$,

  • –

    $a(\mathit{sw}_{2})=\{(8,10),(10,7),(9,10),(10,11),(10,12)\}$,

  • –

    $b(r)=60$ for $r\in R$,

• •

  $T=\{t_{1},t_{2},t_{3}\}$ with

  • –

    $t_{1}=(S_{1},L_{1},e_{1},l_{1},w_{1})$,

  • –

    $t_{2}=(S_{2},L_{2},e_{2},l_{2},w_{2})$,

  • –

    $t_{3}=(S_{3},L_{3},e_{3},l_{3},w_{3})$,

  where $(S_{1},L_{1})$, $(S_{2},L_{2})$ and $(S_{3},L_{3})$ are nodes of edges and edges themselves that are solid, dotted or dashed in Figure 1, respectively, and

  • –

    $e_{1},l_{1},e_{2},l_{2},e_{3},l_{3}$ give the upper and lower coordinates of the colored areas in Figure 2,

  • –

    $w_{1}(e)=w_{2}(e)=w_{3}(e)=0$ for $e\in E$,

• •

  $C=\{c_{1},c_{2},c_{3}\}$ with

  • –

    $c_{1}=(t_{2},(4,3),t_{3},(3,6),0,0,3,3)$,

  • –

    $c_{2}=(t_{1},(10,12),t_{3},(10,12),60,\infty,10,12)$,

  • –

    $c_{3}=(t_{1},(10,11),t_{3},(10,12),60,\infty,10,12)$,

  and

• •

  $F=(F_{c_{1}},F_{c_{2}},F_{c_{3}})$ where $F_{c_{1}}=\{(t_{2},(4,3),t_{3},(3,6),\mathit{sw}_{1})\}$ and $F_{c_{2}}=F_{c_{3}}=\emptyset$.

A solution $(P,A)$ to a train scheduling problem $(N,T,C,F)$ is a pair consisting of

1. 1.

   a function $P$ assigning to each train line the path it takes through the network, and

2. 2.

   an assignment $A$ of arrival times to each train line at each node on their path.

A path is a sequence of nodes, pair-wise connected by edges. We write $v\in p$ and $(v,v^{\prime})\in p$ to denote that node $v$ or edge $(v,v^{\prime})$ are contained in path $p=(v_{1},\dots,v_{n})$, that is, whenever $v=v_{i}$ for some $1\leq i\leq n$ or this and additionally $v^{\prime}=v_{i+1}$, respectively.

A path $P(t)=(v_{1},\dots,v_{n})$ for $t=(S,L,e,l,w)\in T$ has to satisfy:

where $\mathit{in}$ and $\mathit{out}$ give the in- and out-degree of a node in graph $(S,L)$, respectively. Intuitively, conditions (1) and (2) enforce paths to be connected and feasible for the train line in question and Condition (3) ensures that each path is between a possible start and end node.

An assignment $A$ is a partial function $T\times V\rightarrow\mathbb{N}$, where $A(t,v)$ is undefined whenever $v\not\in P(t)$. Given path function $P$, an assignment $A$ has to satisfy the conditions in (4) to (8):

for all $t=(S,L,e,l,w)\in T$ and $P(t)=(v_{1},\dots,v_{n})$ such that $1\leq i\leq n,1\leq j\leq n-1$,

either

for all $r\in R,\{t,t^{\prime}\}\subseteq T,t\neq t^{\prime},(v,v^{\prime})\in P(t),(u,u^{\prime})\in P(t^{\prime})$ with $\{(v,v^{\prime}),(u,u^{\prime})\}\subseteq a(r)$ whenever for all $(t,(x,x^{\prime}),t^{\prime},(y,y^{\prime}),\alpha,\omega,n,n^{\prime})\in C$ such that $(x,x^{\prime})\in P(t),(y,y^{\prime})\in P(t^{\prime})$, we have $(t,(v,v^{\prime}),t^{\prime},(u,u^{\prime}),r)\not\in F_{c}$,

and finally

for all $(t,(v,v^{\prime}),t^{\prime},(u,u^{\prime}),\alpha,\omega,n,n^{\prime})\in C$ if $(v,v^{\prime})\in P(t)$ and $(u,u^{\prime})\in P(t^{\prime})$.

Intuitively, conditions (4), (5) and (6) ensure that a train line arrives at nodes neither too early nor too late and that waiting and traveling times are accounted for. Furthermore, Condition (7) resolves conflicts between two train lines that travel edges sharing a resource, so that one train line can only enter after another has left for a specified time span. This condition does not have to hold if the two trains use a connection that defines a collision-free resource point for the given edges and resource. Finally, Condition (8) ensures that train line $t$ connects to $t^{\prime}$ at node $n$ and $n^{\prime}$, respectively, within a time interval from $\alpha$ to $\omega$. Note that this is only required if both train lines use the specific edges specified in the connections. Furthermore, note that it is feasible that $n$ and $n^{\prime}$ are visited but no connection is required since one or both train lines took alternative routes.

For our solution in Figure 2, we have

• •

  $P(t_{1})=(2,3,5,8,10,11)$, $P(t_{2})=(10,7,4,3)$, and $P(t_{3})=(3,6,9,10,12)$, and

• •

  $A(t_{1},2)=300,\dots,A(t_{1},11)=600$,

  $A(t_{2},10)=0,\dots,A(t_{2},3)=180$, and

  $A(t_{3},3)=180,A(t_{3},6)=240,A(t_{3},9)=660,\dots,A(t_{3},12)=780$.

To determine the quality of a solution, both the aggregated delay of all train lines as well as the quality of the paths through the network are taken into account. For that purpose, we consider two functions: the delay function $d$ and route penalty function $\mathit{rp}$. Given a train line $t=(S,L,e,l,w)\in T$ and a node $s\in S$, $d(t,s)\in\mathbb{N}$ returns the time point after which the train line $t$ is considered late at node $s$. Note that $e(s)\leq d(t,s)\leq l(s)$. Given an edge $e\in E$, $\mathit{rp}(e)\in\mathbb{N}$ is the penalty a solution receives for each train line traveling edge $e$. With this, the quality of a solution $(P,A)$ is determined via the following pair:

Since delay is the more important criteria, optimization of the quality amounts to lexicographic minimization considering delay first and route penalty second. As mentioned, our example has an accumulated delay of 360 and 0 route penalty and therefore a quality of $(360/60,0)=(6,0)$.

We present two techniques that reduce the complexity of the problem at hand. While resource subsumption detects redundant resources that can safely be removed, resource areas are used to simplify conflict resolution on resource conflicts.

A train scheduling problem $(N,T,C,F)$ with $N=(V,E,R,m,a,b)$ is represented by the facts

for each $t=(S,L,e,l,w)\in T$ and $(v,v^{\prime})\in L$.

For every $s\in S$, we add

Additionally, either

is added, if $\mathit{in}(s)=0$ or $\mathit{out}(s)=0$ in $(S,L)$, respectively. We assign unique terms to each train line for identifiability.

For example, the facts

express that train line t1 may travel between nodes 1 and 3 taking at least 60 seconds, waiting on this edge for 0 seconds, and arrives between time points 240 and 540 at node 1, which is a possible start node.

Furthermore, we add

for $r\in R$ and $(v,v^{\prime})\in a(r)$. Akin to train lines, resources are assigned unique terms to distinguish them.

For example, facts

assign resource sw1 to edges $(1,3)$ and $(4,3)$ and the resource is blocked for 60 seconds after a train line has left it.

Finally, we add

for all $(t,(v,v^{\prime}),t^{\prime},(u,u^{\prime}),\alpha,\omega,n,n^{\prime})\in C$, where $c$ acts as an identifier, and

for all $(t,(v,v^{\prime}),t^{\prime},(u,u^{\prime}),r)\in F_{c}$.

For instance, the transfer of the physical train from train line t2 to t3 at node $3$ is encoded by connection(1,t2,(4,3),t3,(3,6),0,0,3,3). This requires both train lines to be at node 3 at the exact same time. Thus, we have to additionally provide the fact free(1,t2,(4,3),t3,(3,6),sw1) to allow for a shared use of the resource, so that the train lines can connect. This can be done safely since in reality only one train exists for both train lines, which rules out collisions.

For a resource area $A\in\mathcal{A}^{t}_{r}$, we generate facts

for $(v,v^{\prime})\in A$, resource $r\in R$ and train line $t=(S,L,e,l,w)\in T$. We assign a unique term $a$ to distinguish resource areas for the same resource and train line. Furthermore, for every resource area $A\in\mathcal{A}^{t}_{r}$, we add

where $e=min\{e(v))\mid(v,v^{\prime})\in A\}$ and $l=max\{l(v^{\prime})\mid(v,v^{\prime})\in A\}$ to represent the earliest entry and latest exit times for that resource area. In our example, the earliest entry time for resource area $\{(1,3),(2,3),(3,5)\}^{t_{1}}_{\mathit{sw}_{1}}$ is 0, while the latest exit time is 660.

Given delay and route penalty functions $d$ and $\mathit{rp}$, we add

for $t=(S,L,e,l,w)\in T,s\in S,m\in L$ with $\{u,p\}\subseteq\mathbb{N},d(t,s)<u\leq l(t,s)$ to evaluate a solution.

The collection of facts for our example instance can be found in A in Listing 9.

In the following, we describe the general problem encoding. We separate it into three parts handling path constraints, conflict resolution and scheduling.

The first part of the encoding in Listing 1 covers routing. First, exactly one valid start node is chosen for each train line to be visited (Line 1). From a node that is visited by a train line and is not an end node, an edge in the relevant subgraph is chosen as the next route (Line 3). The new route in turn leads to a node being visited by the train line (Line 4). This way, each train line is recursively assigned a valid path. Since those paths begin at a start node, finish at an end node and are connected via edges valid for the respective train lines, conditions (2) and (3) are ensured.

The next part of the encoding shown in Listing 2 detects and resolves resource conflicts. Basically, a resource conflict exists, if two train lines each have an edge in their respective subgraph that is assigned the same resource, and time intervals overlap in which the train lines enter and leave the edges in question, extended by the time the resource is blocked. We improve upon this edge-centric conflict resolution via resource areas. In lines 5–14, we first compute entry and exit nodes leading in and out of a resource area (depending on the chosen route). A conflict is possible, if two train lines each have a resource area in their respective subgraph that is assigned the same resource, and the time intervals overlap in which the train lines may enter and leave the areas in question, extended by the time the resource is blocked (lines 21–25). We resolve the conflict by making a choice which train line passes through this area first (lines 27 and 29).

As a collision-free resource point $(t,(v,v^{\prime}),t^{\prime},(u,u^{\prime}),r)$ does not trigger a resource conflict, we prevent the involved resource areas $A^{t}_{r}$ and $A^{t^{\prime}}_{r}$ with $(v,v^{\prime})\in A^{t}_{r}$ and $(u,u^{\prime})\in A^{t^{\prime}}_{r}$ from creating conflicts by deriving collision-free resource areas in lines 16–19. It is safe to do so, as it is necessary for a collision-free connection that all edges adjacent to $(v,v^{\prime})$ or $(u,u^{\prime})$ with the same resource are also collision-free resource points (recall Section 3.2). We exclude these areas from the conflict resolution in Line 22.