Tournées de véhicules électriques avec flotte mixte et chargement partiel

Session : LTSS6 / LTSS6 : Tournées de véhicules électriques
Jeudi 11 février 15:00 - 16:20 Salle : GI042
Oulad Kouider Tayeb, Ramdane Cherif-Khettaf Wahiba et Oulamara Ammar

Nous proposons dans cette communication de résoudre un problème industriel de tournées de véhicules électriques par une approche constructive et d’évaluer plus particulièrement plusieurs méthodes d’insertion de bornes de recharge. Une première famille de méthodes consiste à insérer une station donnée dans une tournée en construction si et seulement si l’insertion d’un nœud i (client ou station) dans la tournée nécessite le rechargement du véhicule. Dans ce cas, un score est calculé pour toutes les stations qui appartiennent au voisinage V(i) du sommet considéré i, où V (i) est l’ensemble de tous les sommets appartenant au cercle défini par son centre i et son rayon α (α est la distance maximale qui peut être parcourue par le véhicule électrique avec son état de charge). Une deuxième famille de méthodes consiste à prendre en compte le besoin d’énergie à posteriori. Cette méthode fonctionne en deux phases. Dans la première phase, une séquence de clients est construite en relaxant la contrainte d’énergie et la contrainte de capacité. Cette séquence est découpée en tournées dans la deuxième phase, où les contraintes relaxées précédemment sont réinjectées. Ce découpage en tournées utilise la méthode Split [6], que nous avons généralisée pour prendre en compte les contraintes de notre problème. Les résultats de l’évaluation de ces deux familles de méthodes seront présentés lors de la conférence.

Mots clés : Optimisation combinatoire, tournées de véhicules électriques, heuristiques