UC Santa Cruz PhD Thesis: Aircraft Push Back Scheduling Optimization

UNIVERSITY OF CALIFORNIA SANTA CRUZ OPTIMIZATION OF RAMP AREA AIRCRAFT PUSH BACK TIME WINDOWS IN THE PRESENCE OF UNCERTAINTY A dissertation submitted in partial satisfaction of the requirements for the degree of DOCTOR OF PHILOSOPHY in COMPUTER ENGINEERING by WILLIAM JEREMY COUPE March 2017 The dissertation of William Jeremy Coupe is approved: ————————————————– Professor Dejan Milutinović, Chair ————————————————– Professor Ricardo Sanfelice ————————————————– Waqar Malik, Ph. ————————————————– Yoon Jung, Ph. ————————————————– Tyrus Miller Vice Provost and Dean of Graduate Studies Copyright c by William Jeremy Coupe 2017 Table of Contents List of Figures. vi List of Tables .1 Objective (1): Stochastic Model of Ramp Area Aircraft Tra- jectories and Sampled Conflict Points .2 Objective (2): Validation of Stochastic Model .3 Objective (3): Conservative Scheduling Approach .4 Objective (4): Optimization of Push Back Time Windows .2 Queuing Model For Airport Surface .3 Collaborative Decision Making (CDM).

20 3 A Data Driven Approach for Characterization of Ramp Area Push Back and Ramp-Taxi Processes 22 3.2 Data Collection Methodology and Raw Collected Data .3 Statistical Testing of Collected 1-D Time Distributions .4 Sampled Ramp Area Trajectories and Sampled Conflict Distributions 33 3.5 Statistical Testing of Sampled Two-Dimensional Conflict Distributions 37 3. 44 4 Integration of Uncertain Ramp Area Aircraft Trajectories and Gen- eration of Optimal Taxiway Schedules at Charlotte Douglas Airport (CLT) 46 4.3 CLT Airport Surface Operations .5 Sampled Trajectories and Conflict Distributions .6 Mixed Integer Linear Program (MILP) .7 MILP Example Solutions. 65 5 Optimization of Push Back Time Windows That Ensure Conflict Free Ramp Area Aircraft Trajectories 66 5.3 Mixed Integer Linear Program (MILP) .4 MILP Optimal Time Window Solutions .5 Computational Performance of the MILP .6 Conclusion and Future Work. 84 6 A Mixed Integer Linear Programming Approach for Computing the Optimal Chance-constrained Push Back Time Windows 86 6.3 MILP for Computing Optimal Chance-constrained Push Back Windows 95 iv 6.4 Analysis of MILP for Optimal Chance-constrained Time Windows .1 Runtime of MILP .2 Improving the Runtime of the MILP Approach .5 Discussion and Future Work.

109 7 A GPU Approach for Computing the Optimal Chance-constrained Push Back Time Windows 111 7.1 GPU Implementation of Chance-constrained Push Back Time Windows111 7.2 GPU Computational Time. 113 8 A Mixed Integer Linear Program for Real-time Computing the Optimal Push Back Time Windows 117 8.3 Reducing the Number of Constraints Passed to the MILP .1 Clustering of Conflict Points .2 Conflict Cluster Linear Boundaries .4 MILP for Real-Time Computing the Optimal Time Windows .5 Analysis of Objective Function .6 Conclusions and Future Work. 142 9 Concluding Remarks 144 Bibliography 150 A Stochastic Hybrid Automaton Model 164 v List of Figures 3.1 a) CLT airport surface. b) Zoomed in view of CLT south sector and illustration of the experiment set up.

Data was collected by observer located in the ramp tower.2 The processed data is illustrated using histograms. The x-axis rep- resents the time spent in seconds to complete each process and the y-axis represents the number of aircraft within each bin. Data from all gates is shown in the first column, data from the middle gates B6- B12 and C7-C13 is shown in the second column and data from the back gates B2-B4 and C3-C5 is shown in the second column. Data that was collected over all three days is shown in the first row, data collected on the first day is shown in the second row, data collected on the second day is shown in the third row and data collected on the third day is shown in the fourth row.3 Analysis of collected data from all gates over all days.

The push back data is in the first row, the stop data the second row, and the taxi data the third row. The first column shows the histogram of data and the fitted distributions, the second column show the results of the three different statistical tests assessing the goodness-of-fit of the gamma distribution to the collected data, and the third column show the results of the three different statistical tests assessing the goodness-of-fit of the log-normal distribution to the collected data.4 Analysis of collected data from middle gates B6-B12 and C7-C13. The push back data is in the first row, the stop data the second row, and the taxi data the third row. The first column shows the histogram of data and the fitted distributions, the second column show the results of the three different statistical tests assessing the goodness-of-fit of the gamma distribution to the collected data, and the third column show the results of the three different statistical tests assessing the goodness-of-fit of the log-normal distribution to the collected data.5 Sampled trajectories from the stochastic model that was described in Section 3.

The sampled trajectories from gate B10 are shown in the first row and the sampled trajectories from gate B14 are shown in the second row. In the first column we illustrate the evolution of trajecto- ries in time and in the second column we show the distribution of the different discrete states push back, stop and taxi. The distributions of push back, stop and taxi are color coded to represent the relation- ship to the middle and front gate distributions of Fig. The sample distributions of stop and taxi were accepted by both the K-S test and the kernel 2 sample test when analyzed for goodness-of-fit.

The sample distribution of push back were accepted by the K-S test and rejected for the kernel 2 sample test.6 a) Sampled conflict distribution estimated from the conflict ratio de- fined by the relative taxiway schedule tB14 −tB10. b) Two-dimensional conflict distributions for different values of the relative schedule rang- ing from tB14 − tB10 = −20 to tB14 − tB10 = 250. The shape and structure of the conflict distributions appear to be different for differ- ent values of the conflict ratio.7 Analysis of two-dimensional conflict distributions. The first row ana- lyzes the sampled distribution tB14 − tB10 = −20 and the second row assesses the goodness-of-fit to the sampled distribution tB14 − tB10 = 20.

The first column assesses the goodness-of-fit of a multi-variate dis- tribution, the second column assesses the goodness–of-fit of a Gaus- sian Copula, and third column assess the goodness-of-fit of a t-Copula.8 Analysis of the sampled conflict points (red) with the samples from the parametric distribution (blue) and the edges of the MST that do not include cross matches (green). The first row analyzes the sampled distribution tB14 − tB10 = −20 and the second row assesses the goodness-of-fit to the sampled distribution tB14 − tB10 = 20. The first column analyzes a multi-variate distribution, the second column analyzes a Gaussian Copula, and third column analyzes a t-Copula.1 Center alley of the CLT airport. The gates under consideration are highlighted in red and include gates B6, B8, B10, C7, C9 and C11.

Departing aircraft push back from their gates, enter into an uncertain stopped period, and then taxi to the merge node P1. Arriving aircraft are released from the merge node P2 and taxi to their assigned gates.2 Distribution of time spent in discrete states for departing trajectories. The time spent in push back, wait, and taxi is shown in red, green, and blue, respectively.3 Sampled departure trajectories. For each gate, we generate a family of feasible departure trajectories.

For each gate, the family of tra- jectories contains uncertainty within both the spatial path taken and trajectory duration.4 Sampled arrival trajectories. For each gate, we generate a family of feasible arrival trajectories. For each gate, the family of trajectories contains uncertainty within both the spatial path taken and trajectory duration.5 Conflict distributions computed using Algorithm 2. Left: Conflict distribution for CLT departure from gate B6(i) VS.

CLT departure from gate B8(j). The terminal time of departing aircraft i is fixed at time ti = 0 and the terminal time for departing aircraft j is given by the value on the horizontal axis. Right: Conflict distribution for CLT departure from gate C9(i) VS. CLT arrival from gate B6(j).

The terminal time of departing aircraft i is fixed at time ti = 0 and the release time for arriving aircraft j is given by the value on the horizontal axis.6 Top: Example scenario 1, 2, and 3 from left to right. Bottom: Exam- ple scenario 4, 5 and 6 from left to right. The average hold time for various departing (blue) and arriving (red) aircraft operating within the CLT center alley. Each sub figure is defined by fixing a different scenario of three departing and two arriving aircraft.

The earliest available time αi or βi that aircraft i is available to initiate their tra- jectory is sampled from the uniform distribution defined as U(0, 100).1 A) Layout of Dallas-Fort Worth International Airport (DFW) with ramp area outlined in green. Departing aircraft push back from their gates and taxi to the departure queue via the taxiway spot. B) Zoomed in view of the green Terminal C ramp area. The depar- ture trajectories from the gate to the taxiway spot (blue) that were sampled from the stochastic model of aircraft trajectories are shown.2 a) Conflict distributions with select cross sections color coded.

b) Plot of conflicts between aircraft A(i) and BR(j) for schedules ranging from tBR − tA = −70 to tBR − tA = 40 at a resolution of 10 seconds. For the scheduled difference tBR − tA = −60 two conflict free sub- windows are shown in black solid(dotted) lines.3 a) The cost function in objective (5.3) is a function of 4 variables (tSi , tFi , tSj , tFj ). The minimum edge length of the blue combination of time windows is equal to the minimum edge of the orange combination of time windows. By adding the extra term Σi,j tFi/j − tSi/j in the cost function we can distinguish between the two rectangles and the orange rectangle is selected as optimal.

b) Set of 4 constraints that ensure the optimal combination of push back sub-windows is either above, below, left or right of any single conflict point κ = (P B BR , P B A ).4 a) Optimal combination of push back sub-windows for the scheduled spot time difference tj − ti = 23[s]. b) Optimal combination of push back sub-windows for the scheduled spot time difference tj − ti = −39[s].5 a) Minimum time separation at the taxiway spot using the conser- vative conflict separation constraints. b) Minimum time separation at the taxiway spot using the optimal combination of push back sub- windows. Here we assume that the minimum push back time window that we are willing to accept is given by δmin = 25.6 a) Average computation time in seconds of the MILP and the brute force algorithm for problems with variable domain area and variable number of points.

b) Contour plot of the difference between the com- putation time of the brute force algorithm and MILP. A positive value implies that the brute force algorithm took longer to execute than the MILP.7 Computation time of solutions for taxiway spot schedules of n = 4, 5, 6 aircraft.1 a) DFW conflict distribution with select cross sections colored. b) Plot of combinations of push back times (red points) resulting in conflicts between aircraft i and i for schedules ranging from tj − ti = −70 to tj − ti = 40 at a resolution of 10 [s]. The y-axis represents the push back time of aircraft i and the x-axis represents the push back time of aircraft j.

If we do not account for conflicts the green rectangle represents the feasible push back domain. For the schedule tj − ti = −60 two feasible push back sub-windows are plotted in black solid and dotted lines.2c show the optimal time window solution on the “easy” domain allowing 0, 3, and 10 points inside the time window respectively. The red (blue) points are color coded to illustrate which points are outside (inside) the optimal time window.