News - Thesis announce

Date : Jan. 29, 2021, 3 p.m. - MBIADOU SALEU Raissa - Visio-conférence

Optimization of uraban deliveries with drones and vehicles in parallel
La croissance de la livraison du dernier kilomètre et de la demande de service rapide poussent la logistique au-delà de la gestion traditionnelle des transports et de l'analyse de la chaîne d'approvisionnement. Une évolution récente de la logistique urbaine implique l'utilisation de véhicules aériens sans pilote à bord ou drones dans le processus de livraison. La livraison par drones offre de nouvelles possibilités mais induit également de nouveaux problèmes de routage complexes.
Les propositions de scénario pour la livraison par drone varient considérablement, les drones étant utilisés indépendamment ou en conjonction avec la livraison par camions. Dans cette thèse, nous abordons un scénario de livraison camion-drone dans lequel un ou plusieurs drones travaillent en collaboration avec un ou plusieurs camions de livraison traditionnels pour distribuer des colis aux clients depuis un dépôt. Le(s) camion(s) et les(s) drone(s) servent différents groupes de clients en parallèle. Un camion sert un sous-ensemble de clients avec un tour unique partant du dépôt et retournant au dépôt tandis qu'une livraison par drone implique un arrêt unique, le drone faisant des allers-retours entre le dépôt et les emplacements des clients. L'objectif est de minimiser l'heure à laquelle tous les camions et drones sont de retour au dépôt, tous les clients ayant été servis. Ce problème est appelé Parallel Drone Scheduling Traveling Salesman Problem (PDSTSP) lorsqu'un seul camion est disponible pour livrer. Quand il y a plusieurs camions, le problème est intitulé Parallel Drone Scheduling Multiple Traveling Salesman Problem (PDSMTSP).
Nous proposons une heuristique itérative en deux étapes pour le PDSTSP. Une étape de codage transforme une solution en une séquence de clients et une étape de décodage décompose la séquence de clients en un tour pour le véhicule et un sous-ensemble de clients affectés aux drones. Le décodage est exprimé comme un problème de plus court chemin bicritère et est réalisé par la programmation dynamique. Des expériences menées sur des instances de référence triées de la littérature (de 10 et 20 clients) et de nouvelles instances plus grandes générées à partir de la TSPLIB confirment l'efficacité de l'approche et les résultats permettent une nette amélioration par rapport à la littérature existante.
Pour résoudre le PDSMTSP qui étend le PDSTSP en considérant plusieurs véhicules, nous proposons une méta-heuristique hybride combinant recherche locale itérée et programmation dynamique. Cette heuristique est inspirée de l'heuristique itérative en deux étapes développée pour le problème restreint à un véhicule. 20 instances (de 50 à 199 clients) sont sélectionnées dans la CVRPLIB pour des expériences. Les expérimentations comparant plusieurs variantes de la méta-heuristique hybride donnent un aperçu de ce système de livraison par drone.
Des formulations en Programme Linéaire en Nombres Entiers (PLNE) pour les deux problèmes sont également fournies et des algorithmes simples de type Branch-and-Cut sont développés.
 
Mots clés: livraison par drone, problème de tournées de véhicules, logistique urbaine, heuristiques, méta-heuristiques, MILP.
 
Jury :
Yasemin Arda - Professeur des Universités, HEC Liège - Rapporteur
Jorge Mendoza Gimenez - Professeur des Universités, HEC Montréal - Rapporteur
Christelle Guéret - Professeur des Universités, Université d’Angers - Examinateur
Jean-Philippe Gayon - Professeur des Universités, Université Clermont Auvergne - Examinateur
Dominique Feillet - Professeur des Universités, Mines Saint-Étienne - Directeur de thèse
Alain Quilliot - Professeur des Universités, Université Clermont Auvergne - Directeur de thèse
Laurent Deroussi - Maître de Conférences, Université Clermont Auvergne - Co-encadrant
Nathalie Grangeon - Maître de Conférences, Université Clermont Auvergne - Co-encadrante.