# Deep Q-Network Approach for Train Timetable Rescheduling Based on Alternative Graph
## 3 Experimental Results
### Results for Seoul Station  
The performance of the RL was tested in the Seoul station area, as shown in Figure 6. This area consists of 49 blocks, containing 29 junctions and 14 platforms, making it currently the most-complex area in Korea. The network was considered with microscopic detail, considering switches, signals, etc. In the actual train timetable, there are 12 trains driving on this network between 7 a.m. and 8 a.m. Therefore, the DQN was trained using these 12 trains with uniform entry delay time [0, 600]. The DQN was tested on these instances, varying the maximum entry delay time and the number of trains, denoted as \(U=\{300,600,900,1200\}\) and \(NT=\{10,12,14,16,18\}\), respectively. We generated 100  
\begin{table}
\begin{tabular}{c c c c c c} \hline \hline \multirow{2}{*}{\(\mathbf{U}\)} & \multicolumn{2}{c}{**MILP**} & \multicolumn{2}{c}{**DQN**} \\ \cline{2-5}  & **\# of Optimal** & **Avg. Runtime** & **\# of Optimal** & **Avg. Runtime** & **Avg. GAP** \\ \hline
300 & 100 & 0.005 s & 100 & 0.740 s & 0.00 \\
600 & 100 & 0.005 s & 93 & 0.747 s & 0.01 \\
900 & 100 & 0.005 s & 80 & 0.744 s & 0.14 \\
1200 & 100 & 0.005 s & 71 & 0.770 s & 0.25 \\ \hline \hline \end{tabular}
\end{table}
Table 3: Average runtime and GAP values for instances of a simple network.  
Figure 5: Training results with respect to the cumulative number of episodes with \(U=600\).  
instances for each category, denoted (\(U\), \(NT\)). Therefore, a total of 2000 instances were tested. Note that we forced our DQN to face novel scenarios by increasing the number of trains with different departure times or destination platforms compared with those of previous trains.  
Figure 7 shows the alternative graph with a feasible selection obtained by the DQN for an instance with (300, 12). The fixed arcs generated by 12 trains are indicated as black bold arrows, and 125 alternative arcs are indicated as blue dashed arrows. Lastly, red dashed arrows indicate edges connected to two dummy nodes: entry and exit.  
Table 4 summarizes the comparisons of MILP and the DQN with respect to three dimensions: number of instances that succeed in finding an optimal solution, average runtime, and average GAP values. Tested on instances with \(U=300\), the MILP model finds optimal solutions for all instances, and the average CPU times tend to increase with respect to the number of trains. The DQN also succeeds in finding an optimal solution for all instances except for \(NT=10\).  
Figure 6: Seoul station railway network.  
Figure 7: Feasible selection and its alternative graph obtained by the DQN for an instance with (300, 12).  
Tested on instances with \(U=600\), the MILP model showed similar results for the instances with \(U=300\). The DQN failed to find the optimal solutions for all instances except for \(NT=12\) and \(NT=18\). However, the GAP values were less than \(0.11\), which shows that the quality of solutions was comparable to that of the exact method. Tested on instances with \(U=900\) and \(U=1200\), the GAP values obtained by the DQN were maintained under \(0.10\) for all instances except for \(NT=10\). However, by increasing the value of \(U\), the average number of instances to obtain the optimal solution decreased from \(96.7\) in \(U=300\) to \(88.5\) in \(U=1200\).  
Overall, the experiments carried out using real-world cases showed that the performance of the exact method was superior to that of the proposed DQN with respect to the quality of solutions and the computation time. However, the increasing rate of the computation time of the DQN was significantly less than that of MILP with respect to the increase in the number of trains. One of the advantages of the DQN is that it shows great scalability. Furthermore, considering the extension and generalization of the problem, such as including nonlinear terms in the objective and/or constraints, the proposed DQN represents a practical method to replace the exact method based on the MILP model on complex railway networks with high traffic density.