Titre de la thèse: The multi-period electric vehicle routing problem: model and solution approaches
Cette thèse étudie l’optimisation du routage et de la programmation de la charge des véhicules électriques (VEs) sur un horizon de planification de plusieurs périodes dans le but de limiter la dégradation des batteries associée à ces opérations. Nous introduisons le problème qui en résulte sous le nom de « Multi-period Electric Vehicle Routing Problem » (MP-E-VRP). Nous définissons formellement le MP-E-VRP et développons des méthodes pour le résoudre.Pour tenir compte de l’impact des pratiques de charge et d’acheminement sur le vieillissement des batteries des VE, nous associons les coûts de dégradation aux opérations de charge et aux routes. Nous transformons la relation non linéaire entre les paramètres de fonctionnement et l’état de santé de la batterie en coûts linéaires par morceaux qui peuvent être facilement inclus dans le MP-E-VRP.Nous fournissons ensuite une formulation de programmation linéaire mixte en nombres entiers (PLNE) pour le MP-E-VRP, ci-après dénommée F1. Notre formulation modélise le temps sur une base continue et utilise des variables de suivi basées sur l’arc. En outre, elle utilise des modèles de flux pour tenir compte des contraintes de capacité du réseau électrique et de l’infrastructure de charge, et des modèles de combinaison convexe pour représenter le coût de dégradation des batteries et les fonctions de charge. Étant donné que le MP-E-VRP est un nouveau problème dans la littérature sur les E-VRP, nous présentons la procédure que nous avons suivie pour générer des instances basées sur des informations fournies par des entreprises utilisant des VE. Les résultats des calculs indiquent que, généralement, le modèle ne peut pas être utilisé directement pour résoudre des cas réalistes. Par conséquent, F1 nous permet d’avoir une idée de la difficulté du problème et de la pertinence de concevoir des stratégies plus complexes.Nous proposons ensuite une stratégie de décomposition dans laquelle nous générons d’abord un pool de routes de haute qualité, puis nous sélectionnons les routes du pool, nous leur attribuons des VEs et nous ordonnons les opérations de chargement. Nous proposons trois méthodes qui suivent cette stratégie de décomposition. Elles utilisent toutes une heuristique existante pour échantillonner l’espace des routes possibles. Pour résoudre le second sous-problème (la sélection de routes et l’affectation des VE), nous proposons une heuristique constructive, une formulation PLNE et une approche basée sur « local branching ». L’heuristique constructive, bien que simple, permet de trouver une solution réalisable en peu de temps. Pour chaque période, l’heuristique attribue la route ayant la plus grande consommation d’énergie au VE ayant la plus grande énergie disponible et poursuit l’attribution jusqu’à ce que toutes les routes de la période soient attribuées. En outre, l’heuristique vérifie la satisfaction des contraintes de l’infrastructure de recharge. La solution obtenue peut alors être fournie pour accélérer le processus de recherche dans les autres stratégies de décomposition.La méthode de décomposition basée sur une formulation PLNE s’appuie sur F1, ci-après dénommée F2m. Peu de modifications sont nécessaires dans F1 pour formuler le nouveau problème concernant l’affectation des VE aux routes et l’ordonnancement des opérations de chargement. Enfin, la matheuristique « local branching » est basée sur F2M et consiste à ajouter des inégalités linéaires à cette formulation, pour explorer l’espace de solution en effectuant des recherches locales sur des voisinages définis en vue de trouver des solutions de bonne qualité. La définition du voisinage et la stratégie de diversification sont modifiées pour tenir compte des caractéristiques du MP-E-VRP. Les résultats expérimentaux nous permettent d’identifier cette méthode comme la meilleure pour trouver des solutions pour des instances de grande taille.
Ma thèse en ligne: ici
Biographie, parcours
2021 – 2023 : postdoctorante au LVMT, Groupe Transversal Mobilités Urbaines Pédestres du Labex Futurs Urbains,