The Figure below provides the layout of Dallas Fort Worth (DFW) airport surface where NASA Ames Spot and Runway Departure Advisor (SARDA) has been implemented to help controllers achieve the following operational goals: maintain a smooth, uninterrupted flow of aircraft moving towards the departure runway; keep the departure queue at a minimum; and maintain maximum runway throughput. The SARDA is designed to aid ground and local controllers in managing aircraft surface operations based on two optimization algorithms, the Spot Release Planner (SRP) and the Runway Scheduler. The SRP provides sequence and timing advisories to the ground controller for releasing departure aircraft into the Federal Aviation Administration (FAA) taxiway to reduce taxi delay while achieving maximum throughput. The Runway Scheduler provides take-off and arrival runway crossing sequences to the Local controller to maximize runway usage.

During time periods of heavy traffic, SARDA advises departing aircraft to remain at the gate with engines off until just before their scheduled spot release time, and when cleared, they can proceed straight from the taxiway spot to the departure runway queue $without$ slowing down or stopping for other traffic. This technique has the effect of significantly reducing fuel burn and engine emissions. Recent studies have estimated as much as 18% of fuel consumption during taxi operations was due to stop-and-go activity

The main idea of the SRP is to provide taxiway spot release advisories to the ground controller in order to achieve a small queue at the runway and achieve an overall reduction in airport taxi times. The calculation of the optimal spot release involves a two stage algorithm. In the first stage, an optimal runway schedule for the set of aircraft (take-off times for departures and crossing times for arrivals) is generated. For each aircraft, its weight class, and earliest available time at the runway are the main inputs to the algorithm. The optimization problem of this first stage, formulated as a mixed integer linear program, is given by:

Where $\mathbb{F}$ is the set of flights, $z_{ij}$ is a binary variable for relative sequencing of aircraft $i$ and $j$ at the runway, $\hat{t}_i$ is a continuos variable for the runway usage time for aircraft $i$. The parameter $a_i$ is the earliest available time at the runway for aircraft $i$ and $\Delta_{ij} = \max[ \Delta_{ij}^r , \delta_{ij}]$ is the required separation. The parameter $\Delta_{ij}^r$ is the minimum required separation between the time that aircraft $j$ can $use$ the runway after aircraft $i$. Runway $use$ is defined as: a departure take-off, an arrival landing, or an aircraft crossing the runway. The parameter $\delta_{ij}$ is the minimum required separation to ensure safe separation within the ramp area and is estimated from the conflict distributions.

At the DFW airport, once aircraft leave the taxiway spots they have specific set of taxi routes to the departure runway. Previous SARDA tests considered East side operations at DFW in south flow configuration with one departure runway (17R) and two arrival runways (17C and 17L). Arrivals landing on 17C or 17L cross 17R at one of the five runway crossing points. Moreover, arrivals can cross runway 17R forty seconds after a departure and they take twenty-one seconds to clear the runway. If two arrivals cross the runway consecutively, the minimum temporal separation between them is five seconds if they are at different crossings, or twenty seconds if they are at the same crossing. The minimum wake vortex separation requirements, $\Delta_{ij}^r$ for all given pairs of departure aircraft weight class that use runway 17R, are provided in the Table below.

The objective is defined to $minimize$ the maximum runway usage time of all aircrafts, i.e. to maximize throughput. The first constraints provide for the relative sequencing among aircrafts $i$ and $j$ and ensures either $i$ comes before $j$ or vice versa. The second constraint is only relevant if $z_{ij}=1$ and reduces to stating that aircraft $j$ must follow $i$ by a minimum of $\Delta_{ij}$ seconds. The third constraint states that the runway usage time for aircraft $i$ can not be scheduled prior to the earliest available time at the runway. The fourth constraint defines the variable $z_{ij}$ as a binary decision variable. The final constraint defines the variable we are interested in computing $t_i$ as a continuos real number.

The second stage of the SRP determines optimal times $t_i$ to release aircraft $i$ from the assigned taxiway spot to meet the departure schedule calculated in the first stage and can be calculated using, \begin{align} t_{i}= \hat{t}_i - \tau_i , \,\,\,\,\,\,\,\,\,\,\,\,\,\,\, \,\,\,\,\,\,\,\,\,\,\,\,\,\,\, \,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\forall i,j \in \mbox{departures} \end{align} where $\tau_i$ is the unimpeded taxi time for the $i^{th}$ aircraft.

To solve the above problem we need to estimate the conflict distributions. Applying the stochastic model we sampled the ramp area trajectories seen below and estimated the conflict distributions and the minimum-time separation constraints $\delta_{ij}$ for all pairs of aircraft.

To compute solutions within the DFW Terminal C ramp area we consider 3 aircraft that are parked at gates A, B and C. The aircraft that occupies gate B is considered to be able to push back with either a left or right push back maneuver. We randomly sample a weight class for each aircraft $i$ and then we sample a value defined on the domain $\alpha_i \sim \mathcal{U}(0,100)$ for the earliest available runway time. Using the gate, weight class, and push back ready times as inputs to the modified SARDA MILP we can compute the following: the optimal time that each aircraft should arrive at the taxiway spot, a window in time to push back each aircraft that is defined by the earliest and latest push back bounds, and the optimal left / right decision to push back aircraft B.

In order to compute the optimal left / right push back decision we build a family of linear programs, one for each decision, and solve them independently of each other. The optimal left / right decision is taken as the solution with the minimum value within the family of linear programs. Two different example solutions are provided below where we show the value of each of the linear programs associated with the left / right decision.

For the given input of example 1 we find that there is no savings in optimizing the left / right push back decision. For the input of example 2 we find that pushing back aircraft B with a left maneuver achieves a savings of 19 seconds over the alternative of pushing back with a right maneuver. This implies that optimizing the left / right push back maneuvers of aircraft can lead to an increase of throughput within the ramp area.