Dynamic programming approaches for the traveling salesman problem with drone

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

full-text

Distinct de l'article heuristique des mêmes auteurs, celui-ci traite le TSP-D de manière exacte par programmation dynamique. C'est ce couple d'articles que l'on cite lorsqu'on discute de la taille des instances résolubles de manière exacte. L'algorithme n'a pas été réimplémenté.

Il présente des méthodes exactes de programmation dynamique et indique qu'elles ont résolu des problèmes plus grands que les approches de programmation mathématique alors présentes dans la littérature. Limiter le nombre de lieux que le camion peut visiter pendant l'absence du drone réduirait sensiblement le temps de résolution, avec un effet relativement faible sur la qualité de la solution.

« Plus grands » s'entend par rapport aux méthodes exactes de l'époque, et non par rapport à la taille d'un VRP opérationnel quotidien. Ajouter la restriction fait en général renoncer à une garantie d'optimalité. Lisez ce point comme une observation expérimentale de l'article.