A decomposition-based iterative optimization algorithm for traveling salesman problem with drone

Yurek, E. E., & Ozmutlu, H. C. · 2018

citation-level

Cet article est cité pour une décomposition itérative du TSP-D en tournée du camion et affectation, puis optimisation des trajets du drone. C'est une référence lorsqu'on cherche une décomposition qui reste proche de la résolution exacte. La méthode n'a pas été réimplémentée pour vérifier cette fiche.

La première étape choisit la tournée du camion et les clients confiés au drone. La seconde fige ces décisions et optimise la partie drone par un programme en nombres entiers mixtes. Les auteurs indiquent que des instances uniformes d'une douzaine de clients ont été résolues en un temps moyen court, et proposent une heuristique fondée sur l'optimisation pour les cas plus grands.

Les tailles résolues correspondent à leur type d'instances. L'algorithme ne doit pas être considéré comme prêt pour un plan quotidien de plusieurs centaines de clients. L'énergie détaillée et la géométrie des zones d'interdiction de vol ne sont pas l'objectif principal.