# Deep Q-Network Approach for Train Timetable Rescheduling Based on Alternative Graph
## 2 Materials and Methods
### MDP Formulation  
An alternative graph enables the detection of train conflict on a microscopic level, in addition to the ability to explicitly model the operation constraints such as the minimum speed, stop, and departure, and connections. As explained previously, the MDP model we propose interprets the train conflict resolution as sequential decision-making, in which an alternative arc is selected at each stage. Therefore, for each step \(t\), it is required for the decision-maker, the agent in the MDP, to have information on all nodes and fixed arcs and the alternative arc up to step \(t\). The size of the alternative graph changes, however, depending on the number of trains and their routes. Since the dimension or size of the state  
Figure 2: Overview of framework for reinforcement learning. is assumed to be fixed, it is challenging to manage two different instances with different numbers of trains on the same railway network with a single policy. This suggests that we need a way to design the state of the MDP independent of the number of trains. To address this challenge, we introduce a mapping from train to block, denoted by \(f_{t}:\mathcal{T}\rightarrow\mathcal{B}\) at decision step \(t\). For each block \(b\in\mathcal{B}\), let \(f_{t}^{-1}(b)\) be the train on block \(b\) at decision step \(t\). Recall that the state space depicts the information given to the agent as the basis for decision-making regarding which action to select. In this respect, the state \(s_{t}\) at decision step \(t\) is designed to consist of 12 features, as shown in Table 1.  
The components of the state are categorized into two types: static and dynamic. The number of total trains (\(NT\)), the physical network (\(PN\)) represented as a 0-1 adjacent matrix, and the junction indicator (\(JI\)) are of the static type. The physical network \(PN_{ij}\) is 1 if blocks \(i\) and \(j\) are connected, or 0 otherwise. Junction indicator \(JI_{b}\) is 1 if block \(b\) has a junction, or 0 otherwise. For the dynamic type, occupation indicator \(OI_{b}\) is 1 if block \(b\) is occupied by any train, or 0 otherwise. The next occupation indicator \(NI_{b}\) is 1 if train \(f_{t}^{-1}(b)\) could be moved to its next block at the next time step, or 0 otherwise. The upward (downward) direction \(UD_{b}\) (\(DD_{b}\)) is 1 if the direction of the train \(f_{t}^{-1}(b)\) is upward (downward), and is 0 otherwise. \(OB_{b}\) and \(OE_{b}\) are the beginning and ending time of occupation for a block \(b\) by train \(f_{t}^{-1}(b)\), respectively. Next, the in-degree and out-degree of the alternative graph denoted by \(ID_{b}\) and \(OD_{b}\) with respect to block \(b\) is defined as the number of incoming or outgoing arcs to the nodes associated with block \(b\) in the alternative graph \(\mathcal{G}(S)\), which can be computed as \(\sum_{\{i:B(i)=b\}}\sum_{\{i:\{j,(j,i)\in\mathcal{P}\cup\mathcal{S}\}}}\delta _{ji}\) and \(\sum_{\{i:B(i)=b\}}\sum_{\{i:\{j,(i)\in\mathcal{P}\cup\mathcal{S}\}}}\delta_{ij}\), respectively, where \(\delta_{ij}\) or \(\delta_{ji}\) equals 1 if arc (\(i\), \(j\)) or (\(j\), \(i\)) is contained in the alternative graph, and is 0 otherwise. Finally, \(AC\) is defined as the longest path cost of the alternative graph \(\mathcal{G}(S)\), denoted by \(l^{5}(0,n)\). The values of the non-binary state are normalized to lie in \([0,1]\). More specifically, for each block \(b\in\mathcal{B}\), we update \(OB_{b}\), \(OE_{b}\), \(ID_{b}\), \(OD_{b}\), and \(AC\) to \(\frac{OB_{b}}{\max_{b\in\mathcal{B}}\{OB_{b}\}}\), \(\frac{OE_{b}}{\max_{b\in\mathcal{B}}\{OB_{b}\}}\), \(\frac{ID_{b}}{\max_{b\in\mathcal{B}}\{DB_{b}\}}\), \(\frac{OD_{b}}{\max_{b\in\mathcal{B}}\{DB_{b}\}}\), and \(\frac{AC}{M}\), respectively, where \(M\) is a sufficiently large positive constant.