Exact methods for the traveling salesman problem with multiple drones

Cavani, S., Iori, M., & Roberti, R. · 2021

full-text

Un article qui retient le fait que passer d'un drone à plusieurs crée une difficulté différente pour le modèle exact. Il empêche le contresens selon lequel davantage d'aéronefs signifierait qu'un problème à l'échelle d'une ville a été résolu.

Le résumé indique qu'ils traitent le problème du voyageur de commerce avec plusieurs drones — un véhicule ordinaire et plusieurs drones se partageant les clients — au moyen d'un programme en nombres entiers mixtes compact, d'inégalités valides et d'une décomposition avec branch-and-cut. Cette approche exacte, écrivent-ils, résout à l'optimalité prouvée des instances comptant jusqu'à vingt-quatre clients, améliorant les méthodes exactes antérieures pour des problèmes similaires, qui atteignaient environ dix clients.

Vingt-quatre est le nombre de clients de leurs instances de test, et non une prévision de la demande. L'énergie dépendant de la charge utile et du vent, les créneaux sur les aires et la réglementation restent hors de portée. N'organisez pas de concours de chiffres avec les trente-neuf clients de Roberti et Ruthmair avec un seul drone.

L'inspection se pose la même question : des dizaines de ponts doivent être visités à tour de rôle. Voir la recherche du MnDOT sur l'inspection par étapes de 39 ponts dans le guide Inspection.