# Train Scheduling with Deep Q-Network: A Feasibility Test
## 4 The Proposed Method
### MDP Formulation  
The subproblem consisting of an express train and its preceding local trains is essentially same as the original problem with smaller number of trains. Thus, it has the same MIP formulation as the original one, and its MIP formulation involves smaller number of variables and constraints than the original problem. In particular, integer variables only appear between a single express train and local trains at the overtaking stations. A key observation is that if we specify the overtaking stations at which the express train overtakes its immediate predecessor, we can determine the values of all integer variables in the MIP formulation of subproblem. In addition, an optimal solution with the corresponding set, say \(O\), of chosen overtaking stations can be represented as the increasing sequence of sets of overtaking stations which ends with \(O\). For example, an optimal solution with \(O=\{4,11,19\}\) can be represented as \((\mathcal{O},\{4\},\{4,11\},\{4,11,19\})\) and each schedule corresponding the subset of \(O\) in the sequence can be obtained by solving LP problem by fixing all integer variables. Based on these observations, we reformulate the subproblem as a sequential decision-making problem such that at each stage we determine the next overtaking station at which the express train overtakes its immediate predecessor. This sequential decision making problem can be modeled as a Markov decision process (MDP) in which the state space, the action space, the reward, and the transition function are defined as follows (also represented in Figure 1). Figure 1: The proposed Markov decision process (MDP) framework. * _State space_: A state represents the schedule of trains, that is, the arrival and departure times of trains at every station. Thus, a state can be represented by a vector \(s\in\mathbb{R}^{2\times|\mathcal{S}|\times|\mathcal{T}|}\). * _Action space_: At each time a decision is made, that is, at each state, the number of possible actions is equal to the number of overtaking stations plus 1. For each action corresponding to an overtaking station, a new state is determined by the transition function introduced later. These actions are called _overtaking actions_. A single additional action is reserved for the decision for stopping the further exploration of states or schedules, and it is called the _finishing action_. * _Transition function_: For each overtaking action, a new overtaking station is added to the current set of overtaking stations used by the current schedule. There are two cases: (1) a new overtaking station is either already chosen previously or just passed in the current schedule, and (2) a new feasible schedule is generated by using the resulting set of overtaking stations. For case (1), the current schedule is not changed, and therefore actions corresponding to this case are called the _infeasible actions_. The other actions are called the _feasible actions_. For each feasible action, a new set of overtaking stations is well defined and values for integer decision variables for the MIP formulation of the subproblem can be fixed. Thus, we can obtain linear programming (LP) model for the subproblem which is efficiently solvable. An optimal solution of LP can provide a new schedule of trains, i.e., a new state \(s^{\prime}\). When the finishing action is chosen, an agent stops exploring the states with declaring the current state or schedule is the final one. * _Reward_: For any state \(s\), feasible actions generate the rewards of zero but for an infeasible action small negative reward is given to the agent. For the finishing action, the difference of qualities between the initial schedule and the current schedule is given as the reward. Thus, if the final state or schedule is better than the initial schedule a positive reward is awarded and the magnitude of the reward represents the level of improvement. Figure 2 illustrates the process of the agent in the proposed MDP framework. Figure 2 describes four steps of the agent's decision-making.