Contexte du projet
IFPEN se focalise sur la décarbonation de la mobilité en optimisant les itinéraires pour tous types de véhicules afin de réduire la consommation énergétique. Nos recherches récentes portent sur l'optimisation de l'emplacement des infrastructures de recharge et la taille des batteries pour les véhicules électriques. Cette approche repose sur l’utilisation des méthodes d'optimisation sur graphes, notamment l'optimisation du plus court chemin sous contraintes, pour déterminer l'itinéraire optimal en tenant compte des caractéristiques physiques du véhicule et de l'état de charge de la batterie.
Description du projet
Plusieurs études ont révélé l'efficacité des algorithmes quantiques [1], mettant en lumière leur potentiel pour révolutionner divers domaines dont l'optimisation complexe. Ces recherches démontrent une amélioration significative de la vitesse de traitement par rapport aux solutions classiques. Dans ce projet, notre objectif est d’examiner la faisabilité de cette approche pour résoudre le problème du plus court chemin, enrichi par l'introduction de nouvelles contraintes spécifiques. Cette recherche vise à évaluer les performances et la valeur ajoutée des solutions quantiques dans la résolution de problèmes d’éco-routage sous contraintes sur les graphes. Après une revue bibliographique, le/la candidat(e) sera amené(e) à développer un algorithme qui intègre l'Algorithme d'Optimisation Quantique Approximative (QAOA) ainsi que des composants existants pour aborder un problème d'optimisation du chemin le plus court avec des contraintes spécifiques. Ce développement sera comparé à l'algorithme de Grover, considéré comme une approche exacte, afin d'évaluer et de déterminer les limitations respectives de chaque approche quantique. Les évaluations numériques des solutions proposées seront réalisées à l'aide des ressources informatiques disponibles au TGCC (QLM/Pasqal), permettant une analyse approfondie des performances et de l'efficacité des algorithmes en question. En outre, ces méthodes quantiques seront également comparées avec des approches classiques telles que l'algorithme de Bellman-Ford pour établir un benchmark complet et identifier les avantages spécifiques des méthodes quantiques.
[1] Dalyac, C., Henriet, L., Jeandel, E. et al. Qualifying quantum approaches for hard industrial optimization problems. A case study in the field of smart-charging of electric vehicles. EPJ Quantum Technol. 8, 12 (2021). https://doi.org/10.1140/epjqt/s40507-021-00100-3
