# Deep Q-Network Approach for Train Timetable Rescheduling Based on Alternative Graph
## 1 Introduction
### Preliminary TTR Based on Alternative Graph  
We considered a TTR problem on a single- or double-track unidirectional railway, where \(\mathcal{T}\) and \(\mathcal{B}\) are the sets of trains and blocks in the railway network, respectively. We assumed that every train has its own fixed route, that is a sequence of blocks from the entry point to the exit point, and also has its own planned arrival time and departure time at each block that it traverses. We denote the arrival time and departure time of train \(k\in\mathcal{T}\) at block \(b\in\mathcal{B}\) as \(A_{b}^{k}\) and \(D_{b}^{k}\), respectively. To develop an algorithm based on reinforcement learning for the TTR problem, we used the alternative graph formulation [4], a graphical methodology to deal with the job shop problem. In the alternative graph formulation for the TTR problem, a train is regarded as a job and a block that a train must traverse as a machine, and then, the operational rules and objectives of the TTR problem are expressed as the attributes of the alternative graph. In general, an alternative graph is defined as a triple \(\mathcal{G}=(\mathcal{N},\mathcal{F},\mathcal{A})\), where \(\mathcal{N}\) is the set of nodes, \(\mathcal{F}\) is a set of fixed directed arcs, and \(\mathcal{A}\) is a set of pairs of alternative directed arcs. In a TTR problem, \(\mathcal{N}\) is composed of nodes corresponding to operations representing the block occupancy of trains and two dummy nodes, denoted by \(0\) and \(n\), representing the network entry and exit of each train. Here, we denote the train and the block associated with the node \(i\) as \(T(i)\) and \(B(i)\), respectively. A fixed directed arc represents the block occupation order on the route of a train. For example, a fixed directed arc \((i,j)\in\mathcal{F}\) indicates that \(B(i)\) is the block just before block \(B(j)\) of train \(T(i)(=T(j))\). For a pair of nodes, \(x\) and \(w\), associated with two trains sharing the same block section \(B(x)(=B(w))\), let \(z\) and \(y\) be their previous operations, respectively. Then, the alternative arcs \((x,y)\) and \((w,z)\) are introduced to represent the order and spacing between two trains \(T(x)\) and \(T(w)\) to occupy \(B(x)\). Therefore, given a pair \([(x,y),(w,z)]\in\mathcal{A}\), only one arc of \((x,y)\) and \((w,z)\) must be alternatively selected to avoid the conflict of two trains trying to occupy the common block. Finally, if the entry time of the block corresponding to node \(i,j\) is \(t_{i},t_{j}\), respectively, arc \((i,j)\) also implies a precedence relation such as \(t_{j}\geq t_{i}+b_{ij}\), where \(b_{ij}\), the length of arc \((i,j)\), means the runtime on the block \(B(i)\) equal to \(D_{B(i)}^{T(i)}-A_{B(i)}^{T(i)}\) when \((i,j)\) is a fixed arc, and the setup time of block \(B(i)(=B(j))\) to ensure a minimum headway between two trains, \(T(i)\) and \(T(j)\), in the case of an alternative arc. Figure 1 shows a small railway network, with five blocks and two trains running in the same direction, and its alternative graph. In this situation, two trains share Blocks 3, 4, and 5, at which conflicts can occur. Fixed arcs and alternative arcs are indicated by solid arrows and dashed arrows, respectively. Figure 1: Example railway network, trains, and alternative graph. Given \(S\), a set of alternative arcs called a selection, \(\mathcal{G}(S)\) is defined as the graph \(\mathcal{G}(S)=(\mathcal{N},\mathcal{F}\cup S)\) in which \(\mathcal{N}\) and \(\mathcal{F}\cup S\) are sets of nodes and arcs, respectively. For a conflict- and deadlock-free schedule, \(S\) should be made up by choosing only one of two alternative arcs from every pair in \(\mathcal{A}\) in such a way that the graph \(\mathcal{G}(S)\) has no positive directed cycles. We denote the length of the longest path from node \(i\) to node \(j\) in \(\mathcal{G}(S)\) as \(l^{S}(i,j)\).