## 4 Route Planning Algorithm
### Conflict Detection and Resolution  
A conflict is detected when two aircraft cross the same graph node for a time of less than a given, pre-specified, tolerance, \(\Delta\), fixed to 30 s. The check is computed by iterating on all aircraft that movement on the ground of the airport during the planning time horizon. When a conflict between two aircraft is detected, priority is given to one of the two aircraft for determining which one shall be re-planned. The following rules are considered for flight prioritization, in order of importance:  
1. Aircraft in planning horizon _vs._ aircraft with frozen route;
2. User-assigned priority levels (0-2);
3. Inbound aircraft has priority over outbound aircraft;Between outbound aircraft, the one with the smallest value of TSAT-TOBT has priority;
5. Between inbound aircraft, the one that landed earlier has priority. Analyzing the conflicts between individual pairs of aircraft has the advantage that the possible resolution maneuvers can be screened with limited computational load, especially if compared to a global conflict resolution strategy attempting to solve all (or most, at least) conflicts concurrently. With this single-conflict approach, however, care must be exercised in selecting a resolution maneuver that does not generate new conflicts with other aircraft. This is done in the current algorithm, checking that the resolution maneuver decreases the number of total conflicts. Because the resolution maneuver solves the conflict between the two aircraft under analysis by definition, requiring the number of total conflicts to decrease assures that the number of conflicts with all other aircraft does not increase. The overall strategy for managing the single-conflict approach is shown in Figure 4. This flow diagram is based on assuming that a single-conflict resolution that is not increasing the number of other conflicts can always be found. This heuristic assumption imposes some specific requirements on the single-conflict resolution maneuver described in the next paragraph. Furthermore, the overall computational time is bounded by a pre-defined threshold, T, to cope with the previously discussed requirements. If this threshold is reached, a suboptimal solution will be output, in which only part of the conflicts are solved. Figure 4: Managing the single-conflict approach. Single-conflict resolution can be achieved by three alternative maneuvers of the aircraft with lower priority:  
1. Modifying its TSAT for outbound aircraft. Steps of \(\Delta\)s are selected up to the time that complies with both the TOBT and the take-off sequence defined by DMAN. Compliance is enforced with \(\Delta\)s tolerance. 2. Forbidding the vertex where the conflict occurs and re-computing the standalone solution;
3. Increasing the waiting time at holding points. Steps of \(\Delta\)s are selected also in this case. Solution 1 is preferable over the other two, because it does not increase the TXET, but only shifts the taxi route in time. Between Solutions 2 and 3, the one that induces the smaller increase is preferable. Solution 2 is executed only once and is checked for conflicts only after Solutions 3 with smaller delays is ascertained to yield a nuisance. Because of the overall conflict management, we assume that a single-conflict resolution that is not increasing the number of other conflicts can always be found by repeatedly applying Solution 3. In other terms, an aircraft may be asked to queue at a Holding Position (HP) until there is at least a \(2\Delta\) window between other aircraft crossing in front of the HP. The overall de-conflicting strategy is summarized in Figure 5. Solution 1, being the most complicated of the three, is further discussed in the following paragraphs. The conditions that allow modification of the TSAT from the nominal value, TSAT\({}_{\textit{Nom}}\), shall consider the compliance of the new TSAT both with the aircraft TOBT and with the take-off sequence.