A Heuristic Approach for the Robust Flight Level Assignment Problem

The paper studies the flight level assignment (FLA) problem and its robust variant. Our goal is reducing the total cost (and more specifically the flight delay) induced by airspace congestion through an appropriated FLA taking account of uncertainties such as weather condition, flight velocity, flight departure time, etc. Among these uncertainties, we assume that the flight departure time, which follows a Mixture Gaussian Distribution, is certainly one of the main uncertainty factors worthy to deal with. The deterministic FLA problem is formulated through an Integer Linear Programming (ILP) model, which becomes trickier when the uncertainty aspect is considered. The FLA problem is strongly NP-hard and solving it exactly is out of reach even for moderate realistic instances. Hence, we propose an approximated optimization approach to solve the robust FLA problem. The main idea is to decompose the problem by levels and solving it separately while handling the connecting constraints between levels. Numerical results illustrate our findings.