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.