A dynamic subgraph-capacity model for multiple shortest paths and application to CO2/contrail-safe aircraft trajectories - Archive ouverte HAL Accéder directement au contenu
Pré-Publication, Document De Travail (Preprint/Prepublication) Année :

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

(1) , (1) , (1, 2) , (1)
1
2
Céline Demouge
  • Fonction : Auteur
  • PersonId : 1201898
Marcel Mongeau
Daniel Delahaye

Résumé

Finding a shortest path with various constraints and cost functions is a common problem in operations research. This paper deals with the special case of the problem of computing multiple shortest paths with capacity constraints on a subgraph that evolves over time. Multiple shortest paths is understood as paths for each vehicle considered. The static special case is modeled as a Mixed Integer Linear Programming (MILP) problem, 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. This study is 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 the impact. The proposed methodology takes into account a network point of view where airspace (subgraph) capacities evolve as well as the traffic itself over time. Encouraging numerical results on the CO2 /contrail-safe aircraft trajectories application are obtained and show that the environmental impact can be reduced while maintaining safety by guaranteeing the respect of airspace capacities.
Fichier principal
Vignette du fichier
Subgraph_capacity_constraint_preprint.pdf (9.53 Mo) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-03900872 , version 1 (15-12-2022)

Identifiants

  • HAL Id : hal-03900872 , version 1

Citer

Céline Demouge, Marcel Mongeau, Nicolas Couellan, Daniel Delahaye. A dynamic subgraph-capacity model for multiple shortest paths and application to CO2/contrail-safe aircraft trajectories. 2022. ⟨hal-03900872⟩
0 Consultations
0 Téléchargements

Partager

Gmail Facebook Twitter LinkedIn More