Design of an optimal route structure using heuristics-based stochastic schedulers

The purpose of this study is to investigate the effects of efficient route structure in the extended terminal airspace area on arrival scheduling performance. This paper will provide reasonable guidelines for optimal route topology in the extended terminal area by considering the uncertainties present in real operations. In a previous study, a Mixed Integer Linear Programming (MILP)-based scheduling algorithm proved to generate more optimal scheduling results than a traditional First-come-First-Served (FCFS) scheduler. However, an expensive computational cost associated with extensive search process limited its usage to a small number of flights in a dense terminal environment. Heuristics based on FCFS scheduling were introduced to alleviate this computational limitation. However, that heuristic was not sufficient to accommodate the amount of traffic associated with dense terminal operations. In this study, we introduce a Genetic Algorithm (GA) as an alternative heuristic for queuing aircraft and route assignment to reduce the computational cost dramatically. To take into account realistic operations, a dynamic planner framework is constructed that integrates the GA heuristics-based scheduler with a stochastic trajectory simulator. Uncertainty quantification and propagation along the routes are implemented in the trajectory model. The trajectory model is simulated based on the Scheduled Times of Arrival (STAs) provided by the scheduler. As a practical application of the proposed scheduler to the dense terminal environment, a design of an optimal route structure is carried out for the terminal airspace represented in cartesian coordinates. The effects of airspace topologies on the scheduling performance are investigated and numerous route structures with different merge topologies are constructed. An optimal merge topology is identified by comparing their scheduling performances and the resulting optimal route structure is validated by the dynamic planner framework. Finally, the sensitivities of the scheduling performance with respect to the uncertainty quantification and propagation modeling are discussed.