ABSTRACT. Résoudre un programme d’optimisation linéaire en variables entières par les outils de la programmation mathématique requiert une bonne formulation. Les technologies de reformulations étendues et de projections sont des outils permettant une bonne approximation linéaire pour des applications adaptées aux principes de décomposition. Nous proposons une revue unifiée des approches de décomposition de Dantzig-Wolfe et de Benders, énonçant les éléments algorithmiques spécifiques à leur implémentation. Nous introduirons également la plateforme logicielle open-source Coluna (Licence Mozilla) dont l’objectif est d’offrir une implementation générique de ces méthodologies dans l’environnement JuMP/Julia Opt.

ABSTRACT. Depuis longtemps les drones sont utilisés dans différents secteurs comme dans l'énergie, l'agriculture ou encore l'aide médicale d'urgence. Suite au succès de leur utilisation, leur rôle dans les systèmes logistiques a été de plus en plus pris au sérieux. Les grandes entreprises de livraison comme Amazon, UPS, DHL et Alibaba ont notamment lancé des projets ambitieux qui consistent à intégrer les drones dans leur système de livraison de colis.

Cette ambition a motivé les chercheurs à s'investir dans des projets académiques et industriels impliquant différentes possibilités d'utilisation de drones dans la livraison de produits. En particulier, le problème de tournées de véhicules avec drones (Vehicle Routing Problem with Drones (VRPD)) et le problème du voyageur de commerce avec drone (Traveling Salesman Problem with Drones (TSPD)) ont attiré l'attention des chercheurs. Dans cette problématique, le VRPD est une variante du problème de tournées de véhicules (VRP), ce dernier étant un problème classique en optimisation combinatoire.

Pour ce travail, nous nous intéressons à la résolution du VRPD et dans cet objectif, nous présentons un modèle mathématique et un algorithme de recherche à voisinage variable (Variable Neighborhood Search) (VNS). Afin de vérifier la performance de notre algorithme, nous avons effectué des tests numériques sur des données de différentes tailles. Les résultats sont comparés à ceux du solveur Gurobi. D'après les résultats numériques, non seulement notre algorithme fournit des solutions de très bonne qualité, mais il réussit aussi à résoudre des instances de grande taille, tandis que Gurobi n'en est pas capable.