## 4 Route Planning Algorithm
### Conflict Detection and Resolution
The take-off sequence is fixed by a DMAN based on elements that XRP does not take into account and  
Figure 5: De-conflicting strategy. shall not be modified. Compliance with the take-off sequence implies, thus, that no aircraft may be allowed by XRP to take off, either after the following or before the preceding aircraft in the sequence. The compliance of the modified timed taxi route to these conditions shall be enforced with a tolerance of \(\Delta\), which yields:  
\[\mathit{TSTAT},\mathit{TQBT}: \begin{bmatrix}\mathit{TSTAT}-\mathit{TQBT}&\geq \Delta\\ \mathit{TTOT}-\mathit{TOTOT}_{\mathit{pmuca}}&\geq\Delta\\ \mathit{TOT}_{\mathit{pmuca}}-\mathit{TOT}&\geq\Delta\end{bmatrix}  \tag{3}\]  
In Equation (3), TSAT, TTOT and TOBT refer to the current aircraft, _i.e._, the one that is being deconflicted, whilst \(\mathrm{TTOT}_{\mathrm{precAC}}\) refers to the TTOT of the aircraft preceding the current one in the take-off sequence, and \(\mathrm{TTOT}_{\mathrm{follac}}\) refers to the TTOT of the aircraft following the current one in the take-off sequence. Equation (3) constrain the amount by which \(\mathrm{TSAT}_{\mathrm{Nom}}\) may be varied. Since Solution 1 modifies \(\mathrm{TSAT}_{\mathrm{Nom}}\) at steps of \(\Delta\)s, the amount of variation that can be applied to anticipate or delay an aircraft is given by:  
\[\mathit{TSTAT}-\mathit{TSTAT}_{\mathit{Nom}}= \begin{bmatrix}-N_{\mathit{Earth }}\cdot\Delta&\text{for an anticipated AC}\\ N_{\mathit{Delay}}\cdot\Delta&\text{for a delayed AC}\end{bmatrix}  \tag{4}\]  
where \(\mathrm{N}_{\mathrm{Early}}\) and \(\mathrm{N}_{\mathrm{Delay}}\) are the integer numbers of steps the aircraft being de-conflicted that have been anticipated and delayed, respectively. In fact, the de-conflicting logic may increase the amount of time an aircraft is anticipated or delayed, until either the conflict is solved or the aircraft cannot be further anticipated or delayed. This is equal to increasing the integer numbers, \(\mathrm{N}_{\mathrm{Early}}\) and \(\mathrm{N}_{\mathrm{Delay}}\). In order to evaluate if a certain aircraft can be further delayed or anticipated, conditions (3) shall be checked against the amount of anticipation or delay one wishes to apply for solving the conflict. Let us refer to the case of an aircraft being de-conflicted. Assume that anticipating this aircraft \(\mathrm{N}_{\mathrm{Early}}\) times and delaying it \(\mathrm{N}_{\mathrm{Delay}}\) times has not yet solved the conflict. We wish to check if we can further anticipate or delay this aircraft for solving the conflict. Consider first the anticipation case: this implies that we wish to check if the aircraft being de-conflicted can have a \(\mathrm{TSTAT}=\mathrm{TSAT}_{\mathrm{Nom}}-(\mathrm{N}_{\mathrm{Early}}+1)\)\(\Delta\). The first and the second of conditions (3) shall be verified for increasing \(\mathrm{N}_{\mathrm{Early}}\) to \(\mathrm{N}_{\mathrm{Early}}+1\). These can be combined in a Boolean flag, isE, which is a necessary condition for further anticipating the aircraft, _i.e._, \(\mathrm{N}_{\mathrm{Early}}=\mathrm{N}_{\mathrm{Early}}+1\), as follows:  
\[\mathit{isE}= \begin{bmatrix}\mathit{TSTAT}_{\mathit{Nom}}-\mathit{TQBT}\geq \left(N_{\mathit{Early}}+2\right)\cdot\Delta\end{bmatrix} \!\!\!\left\langle \mathit{AND}\right\rangle\!\!\left\llbracket\mathit{TOT}_{\mathit{Nom}}-\mathit{ TOTOT}_{\mathit{pmuca}}\geq\left(N_{\mathit{Early}}+2\right)\cdot\Delta\right\rfloor \tag{5}\]  
Consider, now, the delay case: this implies that we wish to check if the aircraft being de-conflicted can have a \(\mathrm{TSTAT}=\mathrm{TSAT}_{\mathrm{Nom}}+(\mathrm{N}_{\mathrm{Delay}}+1)\)\(\Delta\). Only the third condition in Equation (3) applies. A Boolean flag, isD, is introduced, also, in this case, being a necessary condition for further delaying the aircraft, _i.e._, \(\mathrm{N}_{\mathrm{Delay}}=\mathrm{N}_{\mathrm{Delay}}+1\), as follows:  
\[\mathit{isD}= \begin{bmatrix}\mathit{TTOT}_{\mathit{phAC}}-\mathit{TOT}_{ \mathit{Nom}}\geq\left(N_{\mathit{Delay}}+2\right)\cdot\Delta\end{bmatrix}  \tag{6}\]