Exact methods for the traveling salesman problem with drone

Roberti, R., & Ruthmair, M. · 2021

full-text

Des travaux qui ont repoussé les limites d'une méthode exacte pour la tournée d'un camion et d'un drone. La phrase « résolu jusqu'à trente-neuf clients » ne peut pas être remplacée par « résolu une ville ». La fiche est là pour empêcher cette substitution.

Le résumé publié indique qu'ils transposent des récurrences de programmation dynamique dans une méthode de branch-and-price appliquée à une formulation de partitionnement d'ensembles, en utilisant une relaxation ng-route et un branchement hiérarchique à trois niveaux. Ce branch-and-price, écrivent-ils, résout à l'optimum des instances comptant jusqu'à trente-neuf clients, soit plus du double de la taille jugée alors gérable. Leurs scénarios indiquent aussi qu'un drone, s'il est assez rapide, peut réduire significativement le délai d'achèvement d'une tournée.

Trente-neuf est un nombre de clients dans une instance. Le vent, l'espace aérien interdit, le vieillissement des batteries et l'autorisation réglementaire ne sont pas au cœur de la méthode exacte. « Significativement » est leur terme, sous leurs hypothèses de vitesse, et non un nombre de minutes pour une ville nommée. Le texte intégral n'a pas été redémontré pour cette fiche.