As an example, let’s say that the three next planes are arriving in the following order: SHS. Under the FCFS scheme, the minimum time from when the first plane lands until the last one can land is 352 seconds, about six minutes. If we could switch the ordering to SSH, the time would be 192 seconds, about 3 minutes. Assuming all of the planes showed up at the same time, this choice of ordering saves 160 seconds, enough time to land a fourth plane of size L or larger.

This paper examines five different sequencing schemes and compares the outputs to that of a sixth scheme, FCFS, to judge improvements or degradations. The six schemes are FCFS, passenger delay minimization, vehicle (or flight) delay minimization, vehicle throughput maximization, airline fairness maximization, and weight class grouping. Each was run with data from one day at LaGuardia airport. LaGuardia was chosen because it is a fairly congested airport and also has only one runway which simplified the model building.

One of the first issues we knew that we would run into was that of dimensionality. With over 500 flights in one day, the state space of the problem is simply too large for modern computers to solve in a reasonable amount of time. However, the problem has a nice structure in that flights landing at 0800 have little to do with flights landing at 1700. We broke the data into smaller overlapping windows and ran sequential optimizations over one window at a time. With this simplification, we were able to sequence the entire day’s flights within a couple of hours.

For the FCFS model we found that the average flight delay for the whole day was 4.9 minutes with standard deviation of 4.7 minutes. The average passenger delay was 4.7 minutes. Approximately 85% of all flights incurred some delay and 39% were delayed by more than five minutes.

Using the Passenger Delay model we found that we could reduce the average passenger delay to 2.7 minutes, a 43% reduction over FCFS. This occurred because we bumped many smaller flights back and allowed the larger aircraft to land sooner.

In running the Vehicle Delay model, we found that we were able to reduce the average vehicle delay to 4.3 minutes, a 9% improvement over FCFS. While this produced some gains, the average passenger delay increased slightly to 5.0 minutes.

The Vehicle Throughput model produced no particular improvement. This model tried to minimize the time of landing for the very last plane. However, as we did not allow planes to land earlier than they were scheduled to arrive, when looking at the whole day, the last plane landed as early as possible in all models. When looking at the schedule on an hour by hour basis, there were changes of only one or two flights per hour. This is likely due to LaGuardia’s homogenous mixture of planes which is 90% L, 7% B757, and 3% S.

The Airline Fairness maximization looked at the 17 airlines that had more than 200 passengers per day and attempted to equalize the average per passenger delay. For FCFS, the average per passenger delay for this subgroup was 5.0 minutes with a standard deviation of 2.0 minutes and a range of 7.4 minutes. The per passenger delay for this Airline Fairness model was worse at 5.9 minutes, but both the standard deviation and range were smaller at 1.9 minutes and 6.5 minutes, respectively.

Finally, the Weight Class Grouping model was a heuristic technique that creates groups of aircraft of the same weight class and land them in batches. The idea was to have a technique that could produce better results than FCFS but without the computational complexity of an optimization routine. The average passenger delay was 4.2 minutes with a standard deviation of 5.7 minutes. The average vehicle delay was 4.5 minutes with a standard deviation of 5.7 minutes.

While the Passenger Delay model gave the single biggest improvement, it heavily penalizes small flights to achieve those gains. Commuter flights which are scheduled for an hour would often take one and a half hours, something that would not be favorable with the passengers or airlines. Additionally, these results are highly data dependant. Data from another airport with a more heterogeneous mixture of planes may yield a very different set of results. However tempting it may be, given this information, it is unwise to crown a winner.

Future work on this problem should consider implementing dynamic window sizes for the optimizations as this would likely allow large gains in performance and possibly produce better results if those given here are suboptimal. Additional analysis on other airports with more heterogeneous flight mixtures would be useful to see if any gains were to be had. Additionally, the models could be modified to handle small advances of flights, i.e. landing early.


DOCUMENTS

Proposal		Presentation			Paper