Solving vehicle routing problems with drones in urban logistics : an approach based on exact and approximate optimization methods

Les drones constituent un complément prometteur pour la logistique de livraison. Ils présentent des caractéristiques fondamentalement différentes de celles des véhicules classiques : des coûts d’utilisation plus faibles et des vitesses plus élevées, au détriment d’une autonomie et d’une capacité réduite. Pour les applications où ces contraintes sont acceptables, les drones peuvent remplacer entièrement les véhicules de livraison. Cependant, dans la plupart des cas, il est nécessaire de combiner stratégiquement ces types de véhicules complémentaires afin de tirer le meilleur parti de leurs atouts opérationnels respectifs. Cette thèse propose principalement des méthodes mathématiques d’optimisation exactes pour les problèmes de routage avec drones. Le premier chapitre propose une revue de littérature consacrée aux problèmes de routage avec drones dans le domaine de la recherche opérationnelle, en mettant l’accent sur les méthodes d’optimisation exactes. Nous soulignons la diversité des problèmes abordés par les chercheurs ainsi que la nécessité d’augmenter la taille des instances résolues à l’optimale. Le deuxième chapitre rappelle brièvement les concepts de programmation mathématique nécessaires à la compréhension des algorithmes de «branch-cut-and-price». Nous décrivons également l’algorithme utilisé dans cette thèse, en détaillant ses composantes avancées ainsi que l’algorithme de «labeling» employé pour résoudre les sous-problèmes. Le troisième chapitre traite du «Two-Echelon Vehicle Routing Problem with Drones». Nous proposons un nouveau modèle de partitionnement d’ensembles, dans lequel les chemins partiels correspondant aux mouvements des drones sont énumérés à l’aide d’un programme dynamique. Nous présentons également une adaptation des «rounded capacity cuts», spécialement conçue pour résoudre ce problème. Par ailleurs, nous développons une heuristique basée sur l’algorithme exact. Les expériences numériques montrent que l’algorithme exact augmente considérablement la taille des instances résolues de manière optimale. Pour évaluer le modèle, l’algorithme est ensuite étendu pour traiter le «Park-and-Loop Routing Problem». Le quatrième chapitre traite du «Truck-based Drone Delivery Routing Problem with Time Windows». Nous développons un algorithme exact de branch-cut-and-price ainsi qu’un algorithme de «labeling» pour résoudre le sous-problème. Nous comparons deux modèles de sous-problème alternatifs définis sur des graphes distincts et montrons qu’aucun des deux ne domine l’autre : le meilleur choix dépend des caractéristiques de l’instance considérée. Les expériences numériques démontrent l’efficacité des approches proposées. Nous introduisons également de nouvelles instances plus complexes, où la capacité des drones est augmentée. Le cinquième chapitre étudie une variante du «Vehicle Routing Problem with Time Windows», qui intègre deux caractéristiques pertinentes sur le plan opérationnel : des heures de départ flexibles depuis le dépôt et des limites strictes sur la durée des routes. Bien que plus générique, ce problème peut s’apparenter à un problème de routage de drones dans lequel la portée est limitée par la durée du trajet. Nous développons un algorithme de branch-cut-and-price, dont la composante principale est un algorithme de «labeling» bidirectionnel résolvant le sous-problème. Nous montrons également comment traiter le problème connexe de minimisation de la durée totale du trajet. Les expériences numériques confirment les performances de l’algorithme.