Coupling Mathematical Optimization and Machine Learning for the Aircraft Landing Problem
Résumé
The Aircraft Landing Problem (ALP) consists in sequencing aircraft on available runways, and scheduling their landing times taking into consideration various operational constraints. It is an NP-hard problem and an ongoing challenge for both researchers and air traffic controllers. A straightforward solution widely used in practice consists in scheduling aircraft using the simple “First-Come First-Served” (FCFS) sequence. However, it rarely provides optimal solutions, especially in large congested airports.In this work, we propose a heuristic approach based on optimistic planning to solve the problem. We model the ALP as an environment of states, actions, transitions and costs, then explore the resulting search tree so as to identify a near-optimal sequence of actions within a limited time budget. In a previous contribution, we used the “First-Come First-Served” (FCFS) rule in the computation of the costs, to estimate the cost of the cheapest path (sequence of actions) from a given state. Now, we investigate a baseline model based on linear regression, and two different machine learning (ML) models trained on a large number of optimized solutions. These models can quickly and accurately estimate the cheapest-sequence cost, which helps the search to identify a near-optimal branch more efficiently. Numerical experiments are performed on our publicly available data set, and show that using machine learning models in our heuristic search does not only ameliorate the previous results in terms of percentage improvement, but also reduces the optimality gap within a computation time that is compatible with on-line operations.
Origine : Fichiers produits par l'(les) auteur(s)
Loading...