Determinstic and Stochastic Optimization for Aircraft Arrival Sequencing and Scheduling under Uncertainty

Abstract

As the demand for air transportation increases, air traffic congestion is becoming a critical issue in the current air traffic control system. In particular, many researchers have recognized the need for decision support tools for human air traffic controllers in the terminal area, where incoming arrivals and outgoing departures are concentrated in a limited airspace surrounding airports. Although uncertainty comes from various sources in the terminal area, only a few existing works consider uncertainty with respect to the aircraft sequencing and scheduling problem.

In this dissertation, two different robust optimization approaches for aircraft arrival sequencing and scheduling are presented that consider the uncertainty of fight time. First, robust optimization based on deterministic programming is proposed, which has a two-level hierarchical architecture. At the higher level, an extra buffer is introduced in the aircraft safe separation constraint by adopting the typical deterministic programming. The extra buffer size is analytically derived based on a deterministic robust counterpart problem. However, robust solutions obtained at the higher level can only be implemented in restricted situations where the magnitude of uncertainty is less than a predetermined constant value. Therefore, at the lower level, to compensate for the effects of unexpected situations under a dynamic environment, robust solutions obtained at the higher level are adjusted by using a heuristic adjustment with a sliding time window.

Second, two-stage stochastic programming based on Particle Swarm Optimization (PSO) is proposed to determine less conservative robust solutions than the robust optimization based on deterministic programming. First and second stage decision problems are defined as aircraft sequencing and scheduling, respectively. PSO is utilized for a randomized search to make the first stage decision under incomplete information about uncertain parameters. A random key representation is adopted to apply PSO to a discrete aircraft sequencing problem because PSO has a continuous nature. Next, the second stage decision is made by solving a mixed integer linear programming problem after the realization of uncertain parameters.

The performances of the two proposed robust optimization methodologies are verified through numerical simulations with historical flight data. Monte Carlo simulations are also performed for randomly generated air traffic situations.