Optimization approaches for the traveling salesman problem with drone

Agatz, N., Bouman, P., & Schmidt, M. · 2018

full-text

Cet article a contribué à fixer le nom traveling salesman problem with drone et la méthode route-first, cluster-second pour affecter les clients au drone. Il se distingue d'une simple note de calcul parce qu'il traite aussi des ratios d'approximation dans le pire des cas. La fiche consigne la citation et l'affirmation habituelle, et ne certifie pas une nouvelle lecture du PDF intégral.

Il modélise la collaboration camion–drone comme un programme en nombres entiers et propose des heuristiques fondées sur la recherche locale et la programmation dynamique. Les petites instances sont comparées aux solutions optimales, et les instances artificielles plus grandes à la livraison en camion seul. Dans ces conditions expérimentales, les auteurs soutiennent que des économies substantielles sont possibles.

L'ampleur de toute économie dépend des hypothèses sur le rapport de vitesse, l'autonomie et la répartition des clients. Un résultat indiquant que des économies sont possibles ne promet pas le même ratio dans chaque ville. La réglementation et les opérations multi-drones sortent du cadre de cette formulation.

L'inspection se pose la même question : l'inspection autonome des lignes a fait l'objet d'une revue, y compris l'appui par véhicule. Voir Automatic autonomous vision-based power line inspection dans le guide Inspection.