Yue Su a soutenu sa Thèse le 5 juillet 2023

Résumé Composition du jury Laboratoire Partenaire

Yue Su, doctorante dans le projet HCM (Chaire Anthropolis) de l’IRT SystemX, a soutenu sa thèse de l’Université Paris-Saclay le 5 juillet 2023 à 10h à CentraleSupélec (l’Amphi IV au bâtiment Eiffel) sur le sujet suivant : « Algorithmes heuristiques et exacts pour résoudre le problème du dial-a-ride avec les véhicules électriques autonomes ».

Résumé de la thèse :

Cette thèse propose des algorithmes heuristiques et exacts efficaces pour résoudre le problème E-ADARP (Electric Autonomous Dial-A-Ride Problem), qui consiste à concevoir un ensemble d’itinéraires à coût minimum qui répond à toutes les demandes des clients pour une flotte de véhicules électriques autonomes (EAVs). L’E-ADARP présente deux caractéristiques importantes : (i) l’emploi des EAVs et une politique de recharge partielle; (ii) la fonction objectif de somme pondérée qui minimise le temps de trajet total et le temps de trajet total excédentaire de l’utilisateur. Dans cette thèse, nous proposons d’abord un algorithme de recuit déterministe (DA). La recharge partielle (i) est gérée par un schéma d’évaluation d’itinéraire exact de complexité temporelle linéaire. Pour aborder (ii), nous proposons une nouvelle méthode qui permet des calculs efficaces du temps de parcours minimal de l’utilisateur en introduisant une représentation fragmentée des chemins. Pour valider les performances de l’algorithme DA, nous comparons les résultats de notre algorithme aux résultats de l’algorithme Branch-and-Cut (B&C) sur les instances existantes. Notre algorithme DA fournit 25 nouvelles meilleures solutions et 45 solutions égales pour 84 instances existantes. Nous établissons de nouvelles instances avec jusqu’à 8 véhicules et 96 requêtes, et nous fournissons 19 nouvelles solutions pour ces instances. Ensuite, nous présentons un algorithme CG, qui est intégré dans le schéma Branch-and-price (B&P) pour résoudre exactement l’E-ADARP. Notre algorithme CG s’appuie sur un algorithme d’étiquetage efficace pour générer des colonnes avec des coûts réduits négatifs. Dans l’extension des étiquettes, le principal défi consiste à déterminer tous les horaires optimaux de temps de trajet en excès d’utilisateur. Pour résoudre ce problème, nous appliquons la représentation basée sur les fragments et proposons une nouvelle approche pour extraire les fragments des arcs tout en garantissant l’optimalité de l’excès de temps de parcours de l’utilisateur. Nous construisons ensuite un nouveau graphe qui préserve toutes les routes réalisables du graphe original en énumérant tous les fragments réalisables, en les extrayant en arcs et en les connectant les uns aux autres, aux dépôts et aux stations de recharge de manière réalisable. Sur le nouveau graphe, nous appliquons des règles de dominance fortes et des vérifications de faisabilité à temps constant pour calculer efficacement les chemins les plus courts. Dans les expériences, nous résolvons 71 instances sur 84 optimalement, améliorons 30 bornes inférieures et générons 41 nouvelles meilleures solutions sur des instances précédemment résolues et non résolues. Enfin, nous étudions le bi-objectif E-ADARP (BOEADARP), qui traite le temps de trajet total et le temps de trajet total de l’utilisateur excédentaire comme des objectifs distincts. Pour aborder le BO-EADARP,
nous introduisons deux algorithmes de recherche dans l’espace de critères et un algorithme de recherche dans l’espace de décision ( l’algorithme BOBP). Nous appliquons ces algorithmes pour résoudre le BO-EADARP sur des instances de petite à moyenne taille avec différentes restrictions de batterie minimales. Parmi les trois algorithmes, l’algorithme BOBP s’avère être le plus efficace. Nous analysons ensuite les solutions efficaces sous différentes contraintes énergétiques. Nos observations révèlent une augmentation notable des temps de trajet totaux pour les solutions efficaces obtenues avec des restrictions d’énergie plus élevées, tandis que les temps de trajet excédentaires totaux correspondants restent stables. Pour chaque niveau de restriction d’énergie, les solutions efficaces obtenues offrent des informations managériales pour les fournisseurs de services rentables et non rentables: un objectif peut être amélioré significativement avec une légère augmentation de l’autre.

Composition du jury :

• An Caris  (Hasselt University, Belgique). Rapporteur
• Fabien Lehuede  (IMT Atlantique, France). Rapporteur
• Sophie Parragh (Johannes-Kepler Universität Linz, Autriche ). Examinateur
• Claudia Archetti (ESSEC Business School, France ). Examinateur
• Oualid Jouini (CentraleSupélec France). Président
• Jakob Puchinger, (EM Normandie & Université Paris Saclay, CentraleSupélec, France). Directeur de thèse

Laboratoire Partenaire :

LGI, CentraleSupélec