# Deep Q-Network Approach for Train Timetable Rescheduling Based on Alternative Graph
## 2 Materials and Methods
### MDP Formulation
In short, state \(s_{t}\) at step \(t\) is defined as  
\[s_{t}=\big{(}NT,\{(PN_{ij})\}_{i\in\mathcal{B},j\in\mathcal{B},\{(I_{b},OI_{b },NI_{b},UD_{b},DD_{b},OB_{b},OE_{b},ID_{b},OD_{b})\}_{b\in\mathcal{B}},AC\} \big{)}. \tag{6}\]  
The size of state \(s_{t}\) is \(|\mathcal{B}|^{2}+9|\mathcal{B}|+2\), where \(|\mathcal{B}|\) is the total number of blocks in the railway network. For a given state \(s_{t}\) at step \(t\), the action \(a_{t}\) chosen by the agent is interpreted as the choice of the alternative arc. More specifically, the choice of the alternative arc is defined as the choice of blocks that satisfies the following condition. Whenever the agent is requested, he/she chooses one of the available blocks, say \(b\), which is currently occupied by a train, i.e., \begin{table}
\begin{tabular}{c c c} \hline \hline
**Features** & **Dimension** & **Type** \\ \hline The number of total trains (\(NT\)) & \(1\) & Static \\ Physical network (\(PN\)) & \(|\mathcal{B}|\times|\mathcal{B}|\) & Static \\ Junction indicator (\(JI\)) & \(|\mathcal{B}|\) & Static \\ Occupation indicator (\(OI\)) & \(|\mathcal{B}|\) & Dynamic \\ Next occupation indicator (\(NI\)) & \(|\mathcal{B}|\) & Dynamic \\ Upward direction (\(ID\)) & \(|\mathcal{B}|\) & Dynamic \\ Downward direction (\(DD\)) & \(|\mathcal{B}|\) & Dynamic \\ Occupation beginning time (\(OB\)) & \(|\mathcal{B}|\) & Dynamic \\ Occupation ending time (\(OE\)) & \(|\mathcal{B}|\) & Dynamic \\ AG node in-degree (\(ID\)) & \(|\mathcal{B}|\) & Dynamic \\ AG node out-degree (\(OD\)) & \(|\mathcal{B}|\) & Dynamic \\ AG cost (\(AC\)) & 1 & Dynamic \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Components of a state. \(OI_{b}=1\), and the next block \(b^{\prime}\) of train \(f_{t}^{-1}(b)\) is not occupied by any trains, i.e., \(NI_{b^{\prime}}=1\). This means that the agent decides to move the train \(f_{t}^{-1}(b)\) forward from block \(b\) to its next block \(b^{\prime}\). Note that only one train can be selected to move at each step. If there is no available block for the action, then the agent selects the dummy action denoted by 0, and the episode is terminated. Therefore, the size of the possible action is \(|B|+1\). We proceed further with the alternative graph to select an action \(a_{t}\) for the transition from the current state \(s_{t}\) to the next state \(s_{t+1}\). Whenever the agent is requested, he/she chooses one of the available blocks occupied by a train, i.e., \(OI_{b}=1\), and the next block of \(f_{t}^{-1}(b)\) not occupied by any trains, i.e., \(NI_{b}=1\). Let \(A(s_{t})\) be the available action set at \(s_{t}\). Action \(a_{t}\in A(s_{t})\) means that the agent decides to move the train \(f_{t}^{-1}(a_{t})\) forward from the current block \(a_{t}\) to its next block \(a_{t}^{\prime}\). Note that only one train is selected to move at each time step. If there is no available block, then the agent selects the dummy action denoted by 0 and the episode is terminated. Therefore, \(|A(s_{t})|\) is at most \(|\mathcal{B}|+1\). Once the agent determines the action \(a_{t}\), we first find the corresponding train \(f_{t}^{-1}(a_{t})\) and the next block \(a_{t}^{\prime}\); the train moves forward. If \(a_{t}^{\prime}\) is used only by the train \(f_{t}^{-1}(a_{t})\), \(\mathcal{G}(S)\) does not change, but the occupancy information of the next state \(s_{t+1}\) only changes when the train \(f_{t}^{-1}(a_{t})\) moves forward one block. If the next block \(a_{t}^{\prime}\) is commonly used by more than one train, we can specify the alternative arcs that determine the occupancy order with other trains using \(a_{t}^{\prime}\) in common. Then, the alternative arcs are added to selection \(S\) and the updated alternative graph \(\mathcal{G}(S)\) is used for the next state \(s_{t+1}\). More specifically, dynamic features are updated as follows: \(OB_{b}=l^{S}(0,(f^{-1}(b),b))-(D_{b}^{f^{-1}(b)}-A_{b}^{f^{-1}(b)})\), \(OE_{b}=l^{S}(0,(f^{-1}(b),b))\), and \(AC=l^{S}(0,n)\). The reward function plays the role of directing the agent's behavior toward the optimal policy.