A time-dependent subgraph-capacity model for multiple shortest paths and application to CO2/contrail-safe aircraft trajectories

Céline Demouge (1) , Marcel Mongeau (1) , Nicolas Couellan (1, 2) , Daniel Delahaye (1)

1 OPTIM - ENAC - Equipe Optim
2 IMT - Institut de Mathématiques de Toulouse UMR5219

This paper proposes a study motivated by the problem of minimizing the environmental impact of air transport at the level of a complete air network, considering thereby several aircraft. Both CO2 and non-CO2 effects are taken into account to calculate this impact. The proposed methodology takes into account a network point of view where airspace capacities evolve as well as the traffic itself over time. Finding a shortest path with various constraints and cost functions is a common problem in operations research. This particular study deals with the special case of computing multiple shortest paths with capacity constraints on a time-dependent subgraph. Multiple shortest paths is understood as one shortest path for each vehicle considered. The static special case is modeled as a Mixed Integer Linear Program (MILP), so that it can be solved directly by a standard commercial solver. The time-dependent nature of the problem is then modeled thanks to a sliding-window approach. Encouraging numerical results on the CO2/contrail-safe aircraft trajectories application are obtained and show that the environmental impact can be significantly reduced while maintaining safety by satisfying the airspace capacity constraints.

Mots clés: Subgraph constrained time-dependent shortest path problem; Contrails; Air transportation; Mixed Integer Linear Programming

Domaines: Informatique [cs]; Mathématiques [math]

Céline Demouge, Marcel Mongeau, Nicolas Couellan, Daniel Delahaye. A time-dependent subgraph-capacity model for multiple shortest paths and application to CO2/contrail-safe aircraft trajectories. 2023. ⟨hal-03900872v2⟩