Electric vehicle routing and charging problem
Planification de la recharge et optimisation des tournées dans le cas de flottes captives
Résumé
Electric Vehicles may decrease transportation-related emissions and provide for less dependence on foreign oil. However, electric vehicles are still facing many weaknesses related to the high purchase prices, limited battery range and scarce charging infrastructure. The deployment of electric vehicles must then involve the design and the deployment of charging infrastructures.
Within this study, the overall objective is to provide enhanced optimization methods and decision tools for electric vehicles assignment, charging and routing that are relevant to different real-world constraints. Firstly, we propose to study the joint scheduling and optimal charging of electric vehicles problem. This problem consists in assigning a set of already constructed routes to the available electric and conventional vehicles and in, simultaneously, optimizing the electric vehicles charging costs while ensuring that all constraints are satisfied. The objective of this problem is to maximize the use of EVs and to minimize charging costs. Secondly, we propose different extensions to our baseline problem and we vary the objective functions and the considered constraints. Moreover, our problem can be seen as a fixed interval scheduling problem with complementary constraints of energy. We propose then to study the complexity and the approximability of many variants of this new problem. Finally, we consider a new variant of the electric vehicle routing problem with a heterogeneous fleet of vehicles and we propose different heuristics and metaheuristics to solve it. We test the different solving methods on benchmark instances and we evaluate the efficiency of each method
Le véhicule électrique est actuellement au coeur des alternatives énergétiques qui permettent de faire face à la croissance du coût du carburant et au réchauffement climatique. En revanche, l’autonomie limitée des batteries des véhicules électriques et l’indisponibilité d’un nombre suffisant de bornes de recharge représentent des enjeux majeurs auxquels se trouvent confrontés les utilisateurs. Le déploiement des véhicules électriques doit alors passer par la conception et l’expérimentation des outils d’aide à la décision pour gestion optimisée et adaptée de l’écosystème du véhicule électrique. C’est dans ce contexte que s’inscrit cette thèse qui vise à fournir des outils d’aide à la décision pour l’optimisation des usages, de la recharge et des tournées des véhicules électriques dans le cadre industriel.
Dans un premier temps, nous proposons d’étudier le problème d’optimisation conjointe de l’affectation et de la recharge des véhicules électriques. L’objectif de ce problème est de maximiser l’usage des véhicules électriques et minimiser les coûts de recharge tout en prenant en compte les contraintes d’ordre opérationnel et technique. Pour résoudre ce problème, nous proposons une méthode exacte et deux heuristiques. Nous comparons les performances de ces méthodes sur des instances réelles et d’autres aléatoires. Nous exposons ensuite plusieurs extensions au problème de base en intégrant de nouvelles fonctions objectif et de nouvelles contraintes. Nous étudions par la suite notre problème de point de vue ordonnancement et nous proposons une étude de complexité et des algorithmes d’approximation avec garantie de performance pour le problème d’ordonnancement d’intervalles sous contraintes d’énergie. Finalement, nous nous intéressons à un nouveau problème de construction de tournées pour une flotte mixte de véhicules électriques et thermiques. Pour résoudre ce problème, nous proposons des heuristiques et des méta-heuristiques hybrides et nous comparons les performances des différentes méthodes sur des instances généralisées de la littérature
| Origine | Fichiers produits par l'(les) auteur(s) |
|---|