# Train Scheduling with Deep Q-Network: A Feasibility Test
## 3 Problem Description
### MIP Formulation  
For a more precise description of our scheduling problem and later use for its LP relaxation, we introduce a mixed integer programming (MIP) model. The model uses the following decision variables.  
* \(A_{i,s}\): the arrival time of train \(i\) at station \(s\) for all \(i\in\mathcal{T}\) and \(s\in\mathcal{S}\)
* \(D_{i,s}\): the departure time of train \(i\) at station \(s\) for all \(i\in\mathcal{T}\) and \(s\in\mathcal{S}\)
* \(Y_{i,j,s}\): the binary variable of which value is 1 if train \(i\) arrives at station \(s\) earlier than train \(j\), and 0 otherwise for all \(i,j\in\mathcal{T}\) and \(s\in\mathcal{S}\)
* \(Z_{i,j,s}\): the binary variable of which value is 1 if train \(i\) departs from station \(s\) earlier than train \(j\), and 0 otherwise for all \(i,j\in\mathcal{T}\) and \(s\in\mathcal{S}\)  
To define objective function and constraints, the planned arrival and departure times (or the target arrival and departure times) are needed, and we use \(\bar{A}_{i,s}\) and \(\bar{D}_{i,s}\) to denote these parameters, respectively.  
The objective function is  
\[\min\ \ \sum_{i\in\mathcal{T}}\sum_{s\in\mathcal{S}}|\bar{A}_{i,s}-A_{i,s}|+| \bar{D}_{i,s}-D_{i,s}| \tag{1}\]  
which represents the total difference with the target schedule.  
Regarding (E1)-(E4) and other operational considerations, we consider the following constraints.  
* The departing order at the initial station given by \(\pi\) should be observed: \[D_{i,1}\geq D_{j,1},\ \ \ \text{for all $i\
eq j$, $i,j\in\mathcal{T}$ such that $\pi^{-1}(i)>\pi^{-1}(j)$}\] (2)
* The departure times of a train at stations should be later than the planned departure times. \[D_{i,s}\geq\bar{D}_{i,s},\ \ \ \text{for all $i\in\mathcal{T}$ and $s\in\mathcal{S}$}\] (3)
* The trains which stops at stations should dwell at least \(d\) time units. \[D_{i,s}-A_{i,s}\geq d,\ \ \ \text{for all $i\in\mathcal{T}_{l}$ and $s\in\mathcal{S}$}\] (4) \[D_{i,s}-A_{i,s}\geq d,\ \ \ \text{for all $i\in\mathcal{T}_{e}$ and $s\in\mathcal{S}$}\] (5)
* Each train cannot move faster than its maximum speed. \[A_{i,s+1}-D_{i,s}\geq l_{ss+1}^{l},\ \ \ \text{for all $i\in\mathcal{T}_{l}$ and $s\in\mathcal{S}\setminus\{S\}$}\] (6) \[A_{i,s+1}-D_{i,s}\geq l_{ss+1}^{e},\ \ \ \text{for all $i\in\mathcal{T}_{e}$ and $s\in\mathcal{S}\setminus\{S\}$}\] (7)
* The arrival headway between two trains at the same station should be observed. \[A_{j,s}-A_{i,s}\geq hY_{i,j,s}-M\times(1-Y_{i,j,s}),\ \ \ \text{for all $i\
eq j\in\mathcal{T}$ and $s\in\mathcal{S}$}\] (8)
* The departure headway between two trains at the same station should be observed. \[D_{j,s}-D_{i,s}\geq hZ_{i,j,s}-M\times(1-Z_{i,j,s}),\ \ \ \text{for all $i\
eq j\in\mathcal{T}$ and $s\in\mathcal{S}$}\] (9)
* The arrival sequences of two trains of the same type at all stations should be same as those in \(\pi\). \[A_{i,s}\geq A_{j,s},\ \ \ \text{for all $i\
eq j\in\mathcal{T}_{l}$ and $s\in\mathcal{S}$ such that $\pi^{-1}(j)<\pi^{-1}(i)$}\] (10) \[A_{i,s}\geq A_{j,s},\ \ \ \text{for all $i\
eq j\in\mathcal{T}_{e}$ and $s\in\mathcal{S}$ such that $\pi^{-1}(j)<\pi^{-1}(i)$}\] (11)
* The departure sequences of two trains of the same type at all stations should be same as those in \(\pi\). \[D_{i,s}\geq D_{j,s},\ \ \ \text{for all $i\
eq j\in\mathcal{T}_{l}$ and $s\in\mathcal{S}$ such that $\pi^{-1}(j)<\pi^{-1}(i)$}\] (12) \[D_{i,s}\geq D_{j,s},\ \ \ \text{for all $i\
eq j\in\mathcal{T}_{e}$ and $s\in\mathcal{S}$ such that $\pi^{-1}(j)<\pi^{-1}(i)$}\] (13)
* For any trains \(i\in\mathcal{T}\) and \(j\in\mathcal{T}\), train \(i\) arrives at station \(s\) either before train \(j\) or after train \(j\). \[Y_{i,j,s}+Y_{j,i,s}=1\] (14)
* For any trains \(i\in\mathcal{T}\) and \(j\in\mathcal{T}\), train \(i\) departs station \(s\) either before train \(j\) or after train \(j\). \[Z_{i,j,s}+Z_{j,i,s}=1\] (15)