Thèse Graphes et Programmation par Contraintes pour la Résolution de Problèmes de Rechargement de Véhicules Électriques H/F - Doctorat.Gouv.Fr

Établissement : Université de Tours École doctorale : Mathématiques, Informatique, Physique Théorique et Ingénierie des Systèmes - MIPTIS Laboratoire de recherche : Laboratoire d'Informatique Fondamentale et Appliquée de Tours Direction de la thèse : Emmanuel NERON ORCID 0009000781368323 Début de la thèse : 2026-10-01 Date limite de candidature : 2026-05-20T23:59:59 À la fois outil de modélisation et de résolution de problèmes combinatoires, les graphes ont toujours été au coeur de la recherche opérationnelle (RO), de l'intelligence artificielle (IA) et, à leur intersection, de la programmation par contraintes (PPC).
- En termes de résolution, ils sont depuis toujours au centre des mécanismes de propagation et de filtrage, typiquement des contraintes globales de cardinalité comme AllDiff [Régin, 1994 ; Le Bozec-Chiffoleau et al, 2025].
- Les graphes peuvent aussi apparaître directement dans la structure des problèmes. Les variables de graphe et leurs contraintes associées [Fages, 2014], offrent alors un cadre de modélisation élégant pour ces problèmes de RO, notamment de transport et de bioinformatique [Ahmed Sidi et al, 2025].

Dans cette thèse nous continuerons l'étude des interactions entre graphes et programmation par contraintes (modélisation, structures de données réversibles dédiées, ...). Nous chercherons en particulier quand et comment les algorithmes de graphe utilisés pendant le filtrage pourraient nous fournir des « explications », et ainsi renforcer le modèle au cours de sa résolution (génération de « nogoods »).

Les techniques développées dans le cadre de ces travaux seront mises en oeuvre pour résoudre efficacement un problème d'optimisation de tournées de véhicules électriques avec des opérations de recharge nocturnes au dépôt. Dans ces problèmes, récemment introduits dans [Yamin et al, 2025], un planificateur doit concevoir des tournées de collecte, de livraison ou de services pour une flotte de véhicules électriques ainsi que le plan de recharge de chaque véhicule pour la nuit qui précède la journée d'opération. La caractéristique principale de ces problèmes est que les infrastructures de recharge sont extrêmement limitées. Par exemple, les dépôts disposent souvent d'un nombre de bornes très inférieur au nombre de véhicules et la puissance maximale sur le site ne permet pas de faire fonctionner les chargeurs à pleine puissance. Comme en attestent les publications des deux équipes, l'équipe ROOT du LIFAT et le CIRRELT (Centre Interuniversitaire de Recherche sur les Réseaux d'Entreprise, la Logistique et le Transport), auquel est affiliée l'École Polytechnique de Montréal, possèdent une expertise commune pour concevoir des algorithmes de Recherches Opérationnelle appliqués aux graphes et partagent également les applications pour la résolution des problèmes de transport et en particulier les problèmes de planification de recharge de véhicules électriques.

Les deux équipes de recherche ont déjà travaillé ensemble à plusieurs reprises dans le cadre de programmes de recherche et des co-publications attestent de cette collaboration fructueuse. L'objectif de cette thèse est le développement d'outils de Programmation Par Contraintes spécifiques pour les graphes. Ces algorithmes se basent sur des algorithmes existants ou à proposer de la Recherche Opérationnelle. Ils seront utilisés pour la résolution de problèmes fortement combinatoires : les problèmes de planification de recharge de véhicules électriques. Les objectifs se déploient en trois points :
- la conception de nouveaux algorithmes, s'inspirant des outils de la Recherche Opérationnelle (méthodes de filtrage en particulier, contraintes globales) ;
- l'implémentation de ces contraintes dans un framework de programmation par contraintes - un framework ouvert sera privilégié ;
- l'utilisation de ce framework pour la résolution de problèmes combinatoires de planification de recharge électriques. Le travail sera organisé à partir d'un état de l'art combinant Programmation Par Contraintes, Recherche Opérationnelle et problèmes de transport (planification de recharges de véhicules électriques). Une étape de formalisation du cas spécifique du problème de recharge de véhicules électriques considéré sera indispensable. Des algorithmes et outils scientifiques seront ensuite proposés pour aller vers une résolution efficace du problème considéré. Enfin une attention particulière sera apportée à la production logicielle pour mettre à disposition de la communauté les outils développés.

Le candidat devra avoir des compétences reconnues en Recherche Opérationnelle, et en théorie des graphes. La connaissance des environnements de programmation par contraintes sera appréciée. De bonnes compétences en développement informatique sont nécessaires pour mener à bien ce projet. Une connaissance des problèmes de transport classiques sera également appréciée. Le candidat devra pouvoir communiquer ses travaux de recherche en français comme en anglais, à l'écrit comme à l'oral.