A Robust Two-Stage Model for the Urban Air Mobility Flight Scheduling Problem

Thanks to recent technical progress, it is now possible to consider air mobility for people at the scale of a city. In this work, we focus on a robust strategic planning problem in an urban air mobility context. For this purpose, we model this problem as a two-stage robust optimization problem in which we aim at computing a schedule that is the least costly, from the user’s point of view, to repair in its worst case scenario. The problem is solved with the adversarial Benders method. The subproblem obtained by this method is then solved by three different heuristics. The first one is based on a local search that relies on a scenario dominance rule that allows to significantly reduce the search space. The different parameters involved in this local search have been selected following an experimental analysis. The two others heuristics are based on a more constrained variant of the subproblem. These heuristics are then compared experimentally.