Approches quantiques pour le problème de plus court chemin sous contraintes

IFP Energies nouvelles (IFPEN) est un acteur majeur de la recherche et de la formation dans les domaines de l’énergie, du transport et de l’environnement. Depuis les concepts scientifiques en recherche fondamentale jusqu’aux solutions technologiques en recherche appliquée, l’innovation est au cœur de son action, articulée autour de quatre orientations stratégiques : climat, environnement et économie circulaire ; énergies renouvelables ; mobilité durable ; hydrocarbures responsables.

Dans le cadre de la mission d’intérêt général confiée par les pouvoirs publics, IFPEN concentre ses efforts sur l’apport de solutions aux défis sociétaux et industriels de l’énergie et du climat, au service de la transition écologique. Partie intégrante d’IFPEN, IFP School, son école d’ingénieurs, prépare les générations futures à relever ces défis.

Approches quantiques pour le problème de plus court chemin sous contraintes

Dans le cadre de la transition énergétique et de la promotion de la mobilité durable, l'optimisation des trajets des véhicules électriques (VEs) ainsi que le placement optimal des stations de recharge jouent un rôle clé dans la réduction de la consommation d'énergie et des émissions de gaz à effet de serre.

À IFPEN, nous développons des outils avancés, notamment le planificateur optimal d'itinéraire pour reposant sur des méthodes d'optimisation sur graphes. Ces outils intègrent les caractéristiques spécifiques des VEs, telles que les capacités des batteries et les niveaux de charge, ainsi que le positionnement stratégique des stations de recharge pour maximiser leur accessibilité tout en minimisant les coûts et les impacts environnementaux.

Ce type de problème peut être modélisé comme une recherche du chemin minimal entre deux nœuds d’un graphe, en prenant en compte les poids associés aux arêtes (par exemple, la distance, le temps de parcours ou la consommation énergétique).

Cependant, lorsqu'on y ajoute des contraintes supplémentaires (comme des restrictions sur les ressources, des limitations de parcours ou des besoins énergétiques spécifiques), ce problème devient NP-difficile. Cela complique considérablement son traitement par des méthodes classiques, qui peuvent nécessiter des temps de calcul prohibitifs, notamment pour des graphes de grande taille.

Pour résoudre ces problèmes complexes d’optimisation combinatoire, les algorithmes quantiques, tels que le QAOA (Quantum Approximate Optimization Algorithm), offrent des perspectives particulièrement prometteuses. Ces algorithmes ont démontré leur efficacité pour résoudre des problèmes liés aux graphes, comme le Max-Cut, ou des variantes du problème du plus court chemin. Cependant, nos travaux précédents ont mis en évidence que l’efficacité du QAOA dépend fortement du choix des paramètres de pénalisation des contraintes dans l’hamiltonien et de l'initialisation des paramètres du circuit quantique (les angles), qui influencent directement la complexité du problème et la pertinence des solutions obtenues.

Une mauvaise initialisation, combinée à des contraintes complexes, peut considérablement dégrader les résultats. De plus, l'effort nécessaire pour améliorer ces points initiaux peut engendrer des calculs supplémentaires, prolongeant ainsi significativement les temps de calcul. Il est donc essentiel de développer des méthodes efficaces pour déterminer des points initiaux optimaux, afin de garantir un compromis équilibré entre la qualité des résultats et les performances globales de l’algorithme.

Objectifs

Ce stage vise à surmonter ces limitations en explorant les axes suivants :

Optimiser les stratégies d’initialisation pour le QAOA, afin d’améliorer la convergence et la qualité des solutions.
Étudier des méthodes alternatives, comme le recuit quantique (via des plateformes telles que D-Wave), pour comparer leurs performances avec celles du QAOA.

Intégrer des approches distribuées, permettant d’accélérer les calculs et d’améliorer la scalabilité des solutions proposées.