# Deep Q-Network Approach for Train Timetable Rescheduling Based on Alternative Graph
## 4 Conclusions and Discussion  
This paper considered a train timetable rescheduling problem at the microscopic level using an alternative graph model. The objective was to minimize the maximum consecutive delay, expressed as the cost of the longest path on an alternative graph. First, we developed a Markov decision process model with an alternative graph model. This enabled us to more explicitly handle various operational constraints without a train operation simulator. In addition, the state of the MDP was designed to be independent of train operation planning, which makes the proposed MDP more applicable to diverse instances. Then, the proposed model was tested on a simple, real-world railway network in the Seoul station area. By evaluating the performance of the DQN through numerical experiments, we concluded that the proposed DQN is comparable to exact methods based \begin{table}
\begin{tabular}{c c c c c c} \hline \hline \multirow{2}{*}{\((\textbf{U},\textbf{NT})\)} & \multicolumn{2}{c}{**MILP**} & \multicolumn{2}{c}{**DQN**} \\ \cline{2-6}  & **\# of Optimal** & **Avg. Runtime** & **\# of Optimal** & **Avg. Runtime** & **Avg. GAP** \\ \hline (300, 10) & 100 & 0.035 s & 82 & 4.582 s & 0.04 \\ (300, 12) & 100 & 0.043 s & 100 & 5.020 s & 0.00 \\ (300, 14) & 100 & 0.061 s & 100 & 6.268 s & 0.00 \\ (300, 16) & 100 & 0.077 s & 100 & 7.083 s & 0.00 \\ (300, 18) & 100 & 0.091 s & 100 & 8.005 s & 0.00 \\ \hline (600, 10) & 100 & 0.035 s & 75 & 4.543 s & 0.11 \\ (600, 12) & 100 & 0.042 s & 100 & 5.154 s & 0.00 \\ (600, 14) & 100 & 0.054 s & 98 & 5.818 s & 0.00 \\ (600, 16) & 100 & 0.069 s & 94 & 6.669 s & 0.01 \\ (600, 18) & 100 & 0.078 s & 100 & 7.498 s & 0.00 \\ \hline (900, 10) & 100 & 0.033 s & 58 & 4.278 s & 0.25 \\ (900, 12) & 100 & 0.044 s & 100 & 5.182 s & 0.00 \\ (900, 14) & 100 & 0.057 s & 93 & 5.957 s & 0.02 \\ (900, 16) & 100 & 0.067 s & 87 & 6.645 s & 0.05 \\ (900, 18) & 100 & 0.078 s & 98 & 7.354 s & 0.00 \\ \hline (1200, 10) & 100 & 0.031 s & 71 & 4.019 s & 0.23 \\ (1200, 12) & 100 & 0.044 s & 98 & 5.180 s & 0.01 \\ (1200, 14) & 100 & 0.051 s & 85 & 5.619 s & 0.10 \\ (1200, 16) & 100 & 0.063 s & 81 & 6.352 s & 0.07 \\ (1200, 18) & 100 & 0.073 s & 88 & 7.184 s & 0.06 \\ \hline \hline \end{tabular}
\end{table} 
Table 4: Average runtime and GAP values for instances at Seoul station. on the MILP model with respect to the quality of the solutions. However, the computation time needs to be further improved. Reinforcement learning issues arise in almost every area of railway operation: train timetabling, trajectory optimization, and control equipment such as the pantograph. MDP-based reinforcement learning using the alternative graph model is a potential area of study for train dispatch or conflict resolution algorithms. Obtaining actual train operation data is exceedingly challenging. Therefore, in order to generate training data using train operation simulators such as OpenTrack, significant costs and time are required, including the implementation of the APIs. We observed that the alternative graph model can potentially replace train operation simulators and facilitate the more-convenient collection of microscopic-level training data. The computational complexity of the proposed method is proportional to the size of the alternative graph and, more specifically, the number of alternative arcs. These findings suggest that timetable rescheduling requires an MDP model that implements immediate selection, as proposed by [4] for computational complexity. In this paper, similar to previous papers [11; 12; 13; 14; 15], the reinforcement learning model was assumed to be a DQN model. For future work, it would be interesting to find more proper alternative reinforcement learning models, such as the deep deterministic policy gradient (DDPG) employed by [28]. Conceptualization, K.-M.K. and Y.-H.M.; methodology, K.-M.K., Y.-H.M. and B.-H.P. ; software, K.-M.K. and Y.-H.M.; validation, B.-H.P. and H.-L.R. ; formal analysis, K.-M.K. and Y.-H.M.; investigation, Y.-H.M. and B.-H.P. ; resources, H.-L.R. ; data curation, H.-L.R.