# Train Scheduling with Deep Q-Network: A Feasibility Test
## 2 Literature Review  
Train scheduling in metro systems has been studied for a long time. These studies can be broadly categorized into macroscopic and microscopic levels. The former considers the arrival and departure times of trains at stations ignoring some detailed information such as signaling systems and routing within stations [3]. On the contrary, at the microscopic level, more detailed information such as routing in a station is taken into account [4]. Another categorization can be made with respect to the variables representing the times (arrival/departure times of trains). In the discrete-time train scheduling, times are discretized and train schedules are defined on the time-space network where nodes represent the locations of a train at specified times [5,6]. In the continuous-time train scheduling, however, continuous variables are used to represent the arrival and departure times of trains [7,8]. Due to the intractability of the problem, both the exact algorithms and heuristics have been proposed to solve the train scheduling problem. Many of these approaches rely on mixed integer linear/nonlinearprogramming formulations. Some of them are solved via efficient enumeration schemes such as branch-and-bound and branch-and-cut algorithms [8; 9]. Various metaheuristics have been also proposed. For example, [PERSON] and [PERSON] [10] and [PERSON] and [PERSON] [11] proposed a genetic algorithm to solve the train scheduling problem. In particular, [PERSON] and [PERSON] [10] combine an artificial neural network (ANN) into the genetic algorithm so that ANN is trained to mimic the decision behavior of train dispatchers. As a relatively new approach, approximate dynamic programming (ADP), or reinforcement learning (RL), has also been used to solve train scheduling problems. This approach relies on formulating the problem as Markov decision processes (MDPs). To obtain an MDP formulation, it is necessary to recast the problem as a multi-stage decision process. There are two types of train scheduling problems to which ADP or RL approach has been applied: timetabling and rescheduling problem. Essentially, these two types of problems want to decide the optimal values of the same decision variables such as arrival/departure times of trains at stations. However, two problems lie in the different stages in the planning process. Timetabling is solved in the basic planning process introduced in Section 1. On the other hand, rescheduling problem arises when the planned schedule resulted from solving timetabling problem is infeasible due to unplanned train delays or infrastructure failures. Thus, both problems can have different objectives and requirement for solution approaches. [PERSON] [12] and [PERSON], [PERSON], [PERSON], and [PERSON] [13] consider the timetabling problems at a macroscopic level. [PERSON] [12] considers the timetabling problem for bidirectional railway lines and therefore track allocations need to be also considered as well as arrival/departure times for trains at stations. The goal is to minimize the total priority-weighted delay. [PERSON] et al. [13] consider the timetabling problem for energy-efficient management of subway trains. It considers train headway for safety, train passenger loads, and the energy consumption along the subway line simultaneously. In the rescheduling problem, both macroscopic [14; 15] and microscopic [16; 17] approaches exist. [PERSON], [PERSON], [PERSON], [PERSON], and [PERSON] [14] and [PERSON], [PERSON], [PERSON], [PERSON], and [PERSON] [15] want to minimize the inconvenience of passengers due to train delays, measured by waiting times of passengers at stations. In the case of [PERSON] et al. [15], minimizing the energy consumption is additionally considered as well as the waiting times of passengers. On the other hand, [PERSON] and [PERSON] [16] and [PERSON], [PERSON], [PERSON], [PERSON], and [PERSON] [17] try to minimize the train delays which are determined by the difference between the planned arrival/departure times of trains and the rescheduled arrival/departure times.