# Deep Q-Network Approach for Train Timetable Rescheduling Based on Alternative Graph
## 1 Introduction  
When a train delay occurs on a complex railway network with high traffic density, this delay can be propagated to the entire railway network. This spread hinders the efficient use of railway networks and causes a decrease in the service quality of passenger or freight transportation. This study addresses train timetable rescheduling (TTR) (also called _train dispatching_ or _conflict detection and resolution_) in a high-density local area to minimize the knock-on train delays in cases of disturbances that make it impossible to comply with the pre-planned train schedule. Here, \"disturbance\" means a relatively small perturbation that can be dealt with only by modifying the timetable, different from \"disruption\", which requires a change in the duty of a rolling-stock or crew. The TTR problem has been intensively studied in various works, and an overview of the various models and algorithms for this purpose can be found in [1]. Except for some macroscopic models [2; 3], most of the models for TTR are microscopic models [4; 5; 6; 7; 8; 9; 10], which allow more-accurate runtime calculations by simulating train movement in detail, down to the microscopic level. One of the mathematical tools to describe these microscopic movements of trains is the _alternative graph_, used in most microscopic models, which graphically expresses the order in which the trains occupy a common block, as well as a sequence of blocks that each train traverses. For example, the decision variables of several integer programming models are the entry/exit times at the blocks in the alternative graph [7; 8; 9], and several heuristics are explicitly based on the alternative graph model [4; 5; 10]. TTR can be modeled as an integer programming model from which we can obtain the optimal solution using branch-and-bound methods or their variants (e.g., branch-and-cut, branch-and-price-and-cut, etc.). However, TTR arises in real-time problem settings in which the solution needs to be provided very quickly. This requirement is hardly satisfied with the existing exact approaches. To address this limitation, several heuristics have been proposed, but there is still a demand for research to find a compromise in the trade-off between the quality of the solution and the computation time. Recently, reinforcement learning has been applied to TTR, in which, instead of finding the arrival and departure times of trains as a solution, a policy or rule is learned such that any legitimate instances can be solved with this policy [11; 12; 13; 14; 15; 16]. Since the learned policy does not need to search large solution spaces, new train schedules are quickly provided, and previous studies showed that, if properly learned, the quality of the solution provided by reinforcement learning is compatible with the optimal one. Adopting reinforcement learning for TTR has been further extended to the setting of multi-agent reinforcement learning [17; 18], in which each train is regarded as an independent agent. In this paper, however, we are interested in the setting of single-agent reinforcement learning. [PERSON] et al. [11] proposed a reinforcement learning approach for TTR in which the state, the input of the policy, is defined as the train location over blocks; the action, the output of the policy, represents the go or stop signal installed at each block; the transitions of the state with respect to the selected action are made with a \"customized\" simulation tool. The proposed method was tested on a simple railway network with no junctions. In TTR, the schedule of a train is likely to affect those of other trains. Some previous studies [12; 14] considered this aspect by defining the state as the occupancy information of several or all blocks. More specifically, the occupancy information of each block is represented as the congestion level of that block computed using the number of trains running on the block.