Optimisation des livraisons urbaines avec drones et véhicules en parallèle

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 tiré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.The growth of last-mile delivery and demand for next- and same-day service is pushing logistics beyond traditional transportation management and supply chain analytics. One recent evolution in urban logistics involves the usage of unmanned aerial vehicle (UAV) or drones in the delivery process. Delivery by drones offers new possibilities, but also induces new challenging routing problems. Proposals for drone delivery vary widely, with drones being used independently or in conjunction with delivery by trucks. In this thesis we address a truck-drone delivery scenario in wich one or several drones work in collaboration with one or several traditional delivery trucks to distribute parcels to customers from a depot. Truck(s) and drone(s) serve different sets of customers in parallel. A truck serves customers with a single tour starting from the depot, visiting a subset of customers and returning back to the depot, while a drone delivery involves a single stop with the drone departing from and returning to the depot (a drone travels back and forth between the depot and the customer locations). The objective is to minimize the completion time i.e., the time at which all the trucks and drones are back to the depot, with the service of all customers carried out. This problem is called Parallel Drone Scheduling Traveling Salesman Problem (PDSTSP) when a single truck is available for delivery. When there are several trucks the problem is coined Parallel Drone Scheduling Multiple Traveling Salesman Problem (PDSMTSP). We propose an iterative two-step heuristic for the PDSTSP. A coding step transforms a solution into a customer sequence, and a decoding step decomposes the customer sequence into a tour for the vehicle and a subset of customers assigned to drones. Decoding is expressed as a bicriteria shortest path problem and is carried out by dynamic programming. Experiments conducted on benchmark instances from the literature (which are instances of 10 and 20 customers) and new larger instances generated from the TSPLIB3 confirm the efficiency of the approach and the results permit a clear improvement over the existing literature. To solve the PDSMTSP which extends the PDSTSP by considering several vehicles, we propose a hybrid metaheuristic combining Iterated Local Search and Dynamic Programming. This heuristic is inspired from the iterative two-step heuristic developed for the same problem restricted to a single vehicle. 20 instances of sizes varying from 50 customers to 199 customers are selected from the CVRPLIB for experiments. Computational experiments comparing several variants of the hybrid metaheuristic give some insights on this drone delivery system. Mixed Integer Linear Programming (MILP) formulations for both problems are also provided and straightforward Branch-and-Cut algorithms are developped