Dates
on the December 15, 2020
Le15 decembre 2020 à 14h (via Teams)
Location
PolytechTours - Visio
Laura Echeverri Titre de la thèse: The multi-period electric vehicle routing problem: model and solution approaches
Résumé :
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 des tournées 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 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 de manière continue et utilise des variables de suivi basées sur les arcs. En outre, elle utilise des modèles de flot 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 bonne 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 » basée sur [F2m] consiste à ajouter des contraintes 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.
Abstract :
This thesis discusses the optimization of electric vehicle (EV) routing and charging scheduling over a planning horizon of multiple periods with the aim of mitigating the battery degradation associated with these operations. We introduce the resulting problem as the Multi-period Electric Vehicle Routing Problem (MP-E-VRP). We formally define the MP-E-VRP and develop methods for solving it. To account for the impact of charging and routing practices on EVs battery aging, we associate degradation costs with charging operations and routes. We transform the nonlinear relationship between operating parameters and battery health into piecewise linear costs that can be easily included in the MP-E-VRP. We then provide a Mixed integer linear programming (MILP) formulation for the MPE-VRP, hereinafter referred to as [F1]. Our formulation models time on a continuous basis and uses arc-based tracking variables. Moreover, it uses flow models to account for the power grid and charging infrastructure capacity constraints, and convex combination models to represent the battery degradation cost and charging functions. Since the MPE-VRP is a new problem in the E-VRP literature, we present the procedure we followed to generate instances based on some insights provided by companies using EVs. Computational results indicate that, generally, the model cannot be directly used to solve realistic instances. Therefore, [F1] allows us to have an idea about the difficulty of the problem and the relevance of designing more complex strategies. We then propose a decomposition strategy in which we first generate a pool of high-quality routes and then we select the routes from the pool, assign EVs to them, and schedule the charging operations. We propose three methods following this decomposition strategy. All of them use an existing heuristic to sample the space of feasible routes. To solve the second subproblem (routes selection, assignment of EVs, and scheduling of charging operations), we propose a constructive heuristic, a MILP formulation, and a local branching-based approach. The constructive heuristic, yet simple, allows finding a feasible solution in a short time. For each period, the heuristic assigns the route with the highest energy consumption to the EV with the most available energy and continues the assignment until all routes of the period are assigned. In addition, the heuristic checks for the satisfaction of the charging infrastructure constraints. The solution obtained can then be provided to speed up the search process in the other decomposition strategies. The decomposition method based on a MILP formulation is built upon [F1], referred to as [F2m]. Few modifications are needed in [F1] to formulate the new problem concerning the assignment of EVs to routes and the scheduling of the charging operations. Finally, the local branching matheuristic is based on [F2m] and lies in adding linear inequalities to this formulation, to explore the solution space by performing local searches on defined neighborhoods looking for good quality solutions. The neighborhood definition and the diversification strategy are modified to consider MP-E-VRP features. Computational experiments allow us to identify this method as the best for finding solutions in large-size instances.
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 des tournées 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 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 de manière continue et utilise des variables de suivi basées sur les arcs. En outre, elle utilise des modèles de flot 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 bonne 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 » basée sur [F2m] consiste à ajouter des contraintes 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.
Abstract :
This thesis discusses the optimization of electric vehicle (EV) routing and charging scheduling over a planning horizon of multiple periods with the aim of mitigating the battery degradation associated with these operations. We introduce the resulting problem as the Multi-period Electric Vehicle Routing Problem (MP-E-VRP). We formally define the MP-E-VRP and develop methods for solving it. To account for the impact of charging and routing practices on EVs battery aging, we associate degradation costs with charging operations and routes. We transform the nonlinear relationship between operating parameters and battery health into piecewise linear costs that can be easily included in the MP-E-VRP. We then provide a Mixed integer linear programming (MILP) formulation for the MPE-VRP, hereinafter referred to as [F1]. Our formulation models time on a continuous basis and uses arc-based tracking variables. Moreover, it uses flow models to account for the power grid and charging infrastructure capacity constraints, and convex combination models to represent the battery degradation cost and charging functions. Since the MPE-VRP is a new problem in the E-VRP literature, we present the procedure we followed to generate instances based on some insights provided by companies using EVs. Computational results indicate that, generally, the model cannot be directly used to solve realistic instances. Therefore, [F1] allows us to have an idea about the difficulty of the problem and the relevance of designing more complex strategies. We then propose a decomposition strategy in which we first generate a pool of high-quality routes and then we select the routes from the pool, assign EVs to them, and schedule the charging operations. We propose three methods following this decomposition strategy. All of them use an existing heuristic to sample the space of feasible routes. To solve the second subproblem (routes selection, assignment of EVs, and scheduling of charging operations), we propose a constructive heuristic, a MILP formulation, and a local branching-based approach. The constructive heuristic, yet simple, allows finding a feasible solution in a short time. For each period, the heuristic assigns the route with the highest energy consumption to the EV with the most available energy and continues the assignment until all routes of the period are assigned. In addition, the heuristic checks for the satisfaction of the charging infrastructure constraints. The solution obtained can then be provided to speed up the search process in the other decomposition strategies. The decomposition method based on a MILP formulation is built upon [F1], referred to as [F2m]. Few modifications are needed in [F1] to formulate the new problem concerning the assignment of EVs to routes and the scheduling of the charging operations. Finally, the local branching matheuristic is based on [F2m] and lies in adding linear inequalities to this formulation, to explore the solution space by performing local searches on defined neighborhoods looking for good quality solutions. The neighborhood definition and the diversification strategy are modified to consider MP-E-VRP features. Computational experiments allow us to identify this method as the best for finding solutions in large-size instances.
