GPU-based Parallelization for Schedule Optimization with Uncertainty

Abstract

This paper presents an application of Graphics Processing Units (GPU) technology for speeding up a schedule optimization problem under uncertainty and provides a fast decision support algorithm to solve an air traffic management problem. In terminal airspace, integrated departure and arrival operations using shared resources have the potential to increase operations efficiency. However, results and benefits from integrated operations might be sensitive to flight time uncertainty. In previous work, a scheduling algorithm was proposed for a model of the Los Angeles terminal airspace. Uncertainty was introduced in the flight times and the uncertainty cost computation was handled by Monte Carlo simulations. The original implementation was carried out on sequential processors, but a 30-minute scenario ran in 6.5 hours, which prohibits applying the algorithm in real-time. This paper presents a GPU-based implementation of the scheduling optimization with uncertainty achieving a 637x speedup in Monte Carlo simulations and a 154x speedup for the entire algorithm compared to a sequential implementation. The runtime of the GPU-based code for the same 30-minute scenario is about 2.5 minutes. This significant speedup allows a large range of experiments to be explored and hundreds of simulations to be run. Two types of experiments are designed and they explore different values of traffic densities and arrival-to-departure ratios. The results demonstrate that there exist trade-off solutions between computed delays and number of controller interventions. The variation of total number of aircraft showed a larger impact on the controller’s workload than the variation of arrival-to-departure ratios. When the traffic density is increased, compromise solutions can be identified to reduce the number of controller interventions and achieve low delays.