Programmation dynamique pour résoudre leproblème d’optimisation d’une route fixepour un aéronef hybride électriqueAnthony Deschênes (Université Laval),
Raphaël Boudreault (Thales),Vanessa Simard (NQB.ai),
Jonathan Gaudreault & Claude-Guy Quimper (Université Laval)

Contexte
AVS-FLX France• Mobilité aérienne du futur• Autonomie des Mobilités Aériennes du Futur (AMAF)o L’objectif du projet AMAF est de structurer l’autonomie de nouvelles solutions à la mobilité aérienneau Québec:✓ Réduire la charge pour les opérateurs avec des outils de planification et d’assistance✓ Démontrer les capacités de détection autonome et de navigation sur des aéronefs UAS-100Partenaires

3Mobilité aérienne avancéeDans tous les cas, l’utilisation de modes de propulsion électrique ouhybride électrique nécessite la planification de l’utilisation de l’énergie pourobtenir des vols faisables, sécuritaires, économiques et écologiques

MICRO AIR MOBILITYREGIONAL AIR MOBILITYURBAN AIR MOBILITY

INTERCONTINENTAL AIR MOBILITY

1234

Fixed Route Hybrid Electric Aircraft Charging Problem

4?L? kWh• Combien de carburant doit-on prendre à chaque terminal?

?s?%• Combien d’électricité doit-on prendre à chaque terminal?

A?%• Combien de temps devons-nous attendre à chaque terminal?
• Quelle distance faire en électrique/carburant sur chaque segment?

?%
?%
?%
?s?%

ObjectifC

Minimiser les coûts totaux: Coûts de carburant Coûts d’électricité Coûts d’horaire?L? kWh?%

B?%
?s?%

?L? kWhIntrants – Description d’un plan multivols (multi-flight plan)• Chaque vol est décrit par un terminal d’origine et de destination• Typiquement, des aéroports comportant les stations de recharge• Chaque vol est défini par un itinéraire (route) formé de plusieurs points (waypoints)
décrivant les étapes de vol (legs)

56Cessna S550 Citation II▌Physique▌Batterie

Poids à vide: 3656 kg

Capacité: 216 kWhVitesse maximale: 890 km/h

Poids1 : 600 kg

Charge utile maximale: 8 passagers + 2employés (800kg)

Marges (minimal/maximal SoC): 10% - 95%
1. Finger et al., 2020. A Comparison of Hybrid-Electric Aircraft SizingMethods▌Carburant
Capacité : 3260 L
Type (masse) : Jet A1 (0,819 kg/L)
Marge (carburant minimal): 163 L (5%)
Vitesse de ravitaillement: 1086 L/min.

Intrants et suppositions• État initial (Temps de début, énergie initale)• Caractéristiques des vols•••

Charge utile
Horaire planifié (heure de départ, heure d’arrivée, temps d’attente minimal)
Origin/destination taxi phases (duration, speed, allowed energy types)• Caractéristiques des terminaux•Coûts (carburant, électricité, horaire sur l’départ/arrivée)✓ Les coûts d’horaire sont calculés en fonction de l’horaire prévue et sont linéaire en fonction dutemps•

Énergie✓ Les caractéristiques du terminal sont implicitement encodées dans les modèles d’énergie• Caractéristiques des segments••

Physique (distance, vitesse, altitude, angle de la trajectoire)Contraintes énergétiques (obliger l’utilisation du carburant et/ou de l’électricité)Fonctions nécessaires pour obtenir une solution• OpenAP[1] prédit la consommation decarburant ainsi que la consommationélectrique• Poids (incluant le poids du carburant)• Distance• Temps de recharge [2][1] Sun et al., 2020. OpenAP: An open-source aircraft performance model for
air transportation studies and simulations.

[2] Deschênes et al., 2020. The fixed route electric vehicle charging problem
with nonlinear energy management and variable vehicle speed.

8

Algorithme – Programmation dynamique (DP)•Inspiré d’un modèle déjà développé pour résoudre un problème similaire (the Fixed Route ElectricVehicle Charging Problem with NonLinear Energy Management (FRVCP-NLEM)) [1]•••9Utilise une récurrence pour résoudre des problèmes de plus en plus gros
Le problème est encodé sous forme de graphe dans lequel des décisions sont prises à chaqueterminal et point de cheminement

Résout successivement le problème suivant:Définition (Programmation dynamique)
Étant au point de cheminement (ou terminal) 𝑤 avec s kWh de batterie, quelle est laquantité minimale de carburant nécessaire pour se rendre à un terminal en
respectant toutes les contraintes?
•••

Décide en fonction des solutions calculées aux points de cheminement 𝑤+1, 𝑤+2, ...
Teste différent taux d’hybridation
La charge (s) est déterminée en fonction de l’horaire[1] Deschênes et al., 2022. Dynamic Programing for the Fixed Route Electric Vehicle Charging Problem with NonLinear Energy
Management.

10

Programmation dynamique - récurrence
Définition (Programmation dynamique)
Étant au point de cheminement (ou terminal) 𝑤 avec s kWh de batterie, quelle est laquantité minimale de carburant nécessaire pour se rendre à un terminal en
respectant toutes les contraintes?

Marge de carburant

Si nous sommes à un terminal
Sinon= Consommation d’électricité sur le segment
d’hybridation= Consommation de carburant sur le segment
d’hybridationétant donné le tauxétant donné le taux

Programmation dynamique - Complexité• Augmentation linéaire de la complexité en fonction du nombrede point de cheminement (N)• Nombre de discrétisation de la charge• Nombre de distance testée pour l’hybridation

11

Définition – Indépendance des sous-problèmes

12

Définition (Indépendance des sous-problèmes)Tous les sous-problèmes sont indépendants si la quantité de carburant d’arrivée et la charge
d’arrivée sont aux marges dans la solution optimale.

• Implique minimalement:• Les coûts de carburant sont les mêmes à chaque terminal• Entre deux terminal consécutif, la solution optimale consomme la totalité du carburant et del’électricité• La solution retournée par la programmation dynamique est optimale
sous l’indépendance des sous-problèmes, la monotonie est fonctions
et des coûts électriques significativement plus petit que les coûts decarburant.

Programmation dynamique – Post traitement – Descente degradient (DP+GD)

13

Quand les coûts de carburant varient, la solution de la programmation dynamique perd sesgarantie d’optimalité• Cepandant, nous pouvons encoder la solution dans un graphe dirigé:
1.35$/L

1.45$/L

1.20$/L

1.60$/L

ABCD• L’action de transférer 𝑥 litres d’un terminal B à un terminal A correspond à:• Arriver au terminal B avec 𝑥 litres de plus tout en prenant en compte la non linéarité desfonctions et en corrigeant les taux d’hybridation au besoin• La Descente de gradient (GD) estime le gradient sur chaque arc, donc l’impact sur les coûts totaux
de faire l’action de transfert, puis transfère là où le gradient est le plus grand jusqu’à convergence• Nous démontrons que cela converge vers un minimum global sous les mêmes hypothèses(en permettant aux coûts de carburant de varier)14

Scénarios
Scénario# de points de# d’aéroports
cheminementCoûts del’électricité($/kWh)Coûts ducarburant($/L)

Paris-Nice4480.1397

1.46

Toulouse-Bordeaux

5260.1397

1.46

Montreal-Sept-Iles6

110.0533[1.16, 1.25]

Ottawa-Toronto

723[0.0533, 0.1140] [1.03, 1.28]

15Montréal – Sept-Îles
Durée
prévueHeure dedepartprévue

Heured’arrivée
prévueDate

OrigineDestination

Vol

Distance(km)20 avril 2023

Montréal (YUL)**

Québec (YQB)

P6343

233

0h43

11:18

12:01

20 avril 2023

Québec (YQB)

Gaspé (YGP)

P6477

178

1h28

12:58

14:26

20 avril 2023

Gaspé (YGP)Îles-de-la-Mad. (YGR)

P6477

109

0h47

14:30

16:17*

20 avril 2023

Îles-de-la-Mad. (YGR)

Bonaventure (YVB)

P6478

302

0h54

17:15*

17:09

20 avril 2023

Bonaventure (YVB)

Québec (YQB)

P66488

507

1h20

17:45

19:05

20 avril 2023

Québec (YQB)

Sept-Îles (YZV)

P66313

535

1h20

19:30

20:50

▌Détails
Horaire basé sur les vols FlightRadar24 du 20 avril 2023
- Heures d’arrivée prévues ajustées selon nos itinéraires de vol

Station électriquedisponible aux aéroports admettant plusd’un million de passagers annuellement1, à l’exception deQuébec (YQB)
1Selon Statistiques Canada, 2021 : https://www150.statcan.gc.ca/t1/tbl1/fr/tv.action?pid=2310025301*Fuseau horaire +1 (AST)**Habituellement YUH (Saint-Hubert), ajusté pour la génération d’itinéraire16Heuristique – Priorité-Carburant• Priorise l’utilisation du carburant
Prendre lemaximum decharge et decarburant àchaque station.
Faire chaqueétape 100%
essencelorsqu’autorisé

Corriger laquantitéd’essence pourarriver à laquantité minimale
permise​Corriger lescharges pourarriver à lacharge
minimale​

Attendrel’heure dedépart si
nécessaire, etpartir​

17

Heuristique – Priorité-Électrique• Priorise l’utilisation de l’électricité
Charger aumaximum àchaque station.
Faire chaqueétape 100%électrique​Est-ce quela charge
minimalepermise est
respectée?​Non• Brûle le carburant en premier• Respecte l’horaire

OuiPrendre juste assezde carburant pourrespecter la charge
minimale​Corriger lescharges pourarriver à lacharge
minimale​

Attendrel’heure dedépart si
nécessaire, etpartir​Détails

18• Simulation• Une simulation (sans approximation) est effectuée avant de calculer les métriques• Tous les algorithmes sont donc comparés sur la même base

• Post-traitement• Un post-traitement est réalisé pour certains algorithmes• La PD peut effectuer une descente de gradient (DG) lorsque les coûts du carburant varient
afin d’améliorer sa solution (et converger vers un minimum global sous certaines hypothèses)Résultats – Coûts totaux pour chaque instance et chaque algorithme

19

Résultats – Temps de calcul et consommation

Paris-Nice

ToulouseBordeauxMontrealSept-Iles

OttawaToronto

20Conclusion• Présenté un nouveau problème (FRHACP)• Proposé un nouvel algorithme de programmation dynamiquepour le résoudre à l’optimalité sous certaines hypothèses• Retourne la solution optimale en moins de 8 secondes sur tous les scénarios• Nous avons démontré qu’il est avantageux d’utiliser l’électricité• En moyenne permet une réduction des coûts de 19.4% sur nos 4 scénarios réalistes

21