Dynamic programming approaches for the traveling salesman problem with drone

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

full-text

Separado do artigo heurístico dos mesmos autores, este ataca o TSP-D de forma exata com programação dinâmica. O par é o que as pessoas citam ao discutir o tamanho de instância que pode ser resolvido exatamente. O algoritmo não foi reimplementado.

Apresenta métodos exatos de programação dinâmica e relata que resolveram problemas maiores do que as abordagens de programação matemática então existentes na literatura. Restringir quantos locais o caminhão pode visitar enquanto o drone está fora reduz substancialmente o tempo de solução, com efeito relativamente pequeno na qualidade da solução.

“Maiores” é relativo aos métodos exatos daquela época, não ao tamanho de um VRP operacional diário. Acrescentar a restrição geralmente abre mão da garantia de otimalidade. Leia esse ponto como a observação experimental do artigo.