2015-2019 e-VRO

Electric Vehicle Routing Optimization

ANR Jeune Chercheur

Electric Vehicle Routing Optimization - e-VRO (www.e-vro.info)

Les véhicules électriques (VEs) constituent une technologie prometteuse pour réduire la dépendance au pétrole et l’émission de gaz à effet de serre. Ceci est particulièrement vrai si l’on considère l’utilisation des VEs pour le transport de marchandises, qui serait responsable de 30% des émissions de CO2 de l’Union Européenne. Des entreprises comme La Poste, UPS, et Coca-Cola utilisent déjà des VEs dans leurs flottes, principalement dans les zones urbaines et pour les livraisons du dernier kilomètre. Cependant, l’utilisation massive des VEs pour le transport de marchandises est freinée par des contraintes techniques telles que l’autonomie limitée des batteries et de longs temps de recharge. Depuis plusieurs années, de nombreuses recherches ont visé (et visent encore) à relâcher ces contraintes via des avancées technologiques concernant la capacité et la vitesse de recharge des batteries, ainsi que la consommation électrique des véhicules. Cependant, un effort considérable reste nécessaire pour développer des outils permettant de gérer des flottes de VEs en tenant compte de ces contraintes particulières. L’un des champs dans lequel le besoin est critique est celui des techniques d’optimisation de tournées de véhicules électriques (e-PTV).

Les problèmes de tournées de véhicules (PTV) consistent à concevoir des tournées efficientes pour livrer (ou collecter) des marchandises, ou fournir des services à des clients à partir d’un dépôt en satisfaisant un certain nombre de contraintes. Durant les 50 dernières années, de nombreux travaux de recherche ont traité la résolution de différentes variantes de PTV. Malheureusement, la plupart des méthodes de résolution proposées sont difficiles, voire impossibles, à utiliser dans un contexte où les tournées sont effectuées par des VEs. En effet, les variantes classiques de PTV considèrent que les tournées sont effectuées par des véhicules thermiques, donc ayant une grande autonomie qui peut être rapidement et facilement restaurée (puisque les stations sont disponibles partout et que le temps nécessaire pour faire le plein est négligeable). Ainsi ces méthodes se focalisent sur la construction d’une (longue) tournée pour chaque véhicule, sans prévoir d’arrêts dans des stations service. En revanche, à cause de la faible autonomie des batteries des VEs, des longs temps de recharge, et du nombre limité d’infrastructures de recharge, les algorithmes d’optimisation pour les e-PTV doivent considérer i) des tournées multiples par véhicule (avec un rechargement de batterie entre chaque), ii) des détours par des stations de recharge, et iii) la coordination de l’accès des différents véhicules aux infrastructures de recharge. Depuis peu, afin de répondre à ces challenges, la communauté scientifique a commencé à développer des techniques spécifiques pour les e-PTV. Cependant, la plupart des problèmes soulevés plus haut restent ouverts, voire inexplorés. Le principal objectif de ce projet est de contribuer à cet effort en imaginant, implémentant, testant et disséminant des méthodes d’optimisation pour résoudre les e-PTV.

Il est à noter que le fait que la propriété de l’infrastructure de recharge soit privée ou publique a un impact sur les contraintes opérationnelles et les paramètres du problème. Afin de couvrir un maximum de problématiques, le projet est structuré en 3 blocs de tâches (BT), chacun traitant un type de propriété différent. Le premier BT est centré sur l’étude des problèmes apparaissant dans le cas d’infrastructures de recharge privées. Dans ce contexte, la flotte de véhicules et les stations de recharge appartiennent au planificateur de tournées. Le second BT concerne l’étude des e-PTV dans le contexte d’infrastructures de recharge publiques. Contrairement au premier scénario, le planificateur de tournées ne détient que la flotte de véhicules et doit partager les stations de recharge publiques avec d’autres utilisateurs. Le troisième BT traite de problèmes communs aux deux contextes.