Dynamic programming approaches for the traveling salesman problem with drone

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

full-text

Separado del artículo heurístico de los mismos autores, este ataca el TSP-D de forma exacta con programación dinámica. El par es lo que la gente cita al discutir qué tamaño de instancia puede resolverse exactamente. El algoritmo no se reimplementó.

Presenta métodos exactos de programación dinámica e informa de que resolvieron problemas mayores que los enfoques de programación matemática entonces en la literatura. Se informa de que restringir cuántas ubicaciones puede visitar el camión mientras el dron está fuera reduce sustancialmente el tiempo de solución, con un efecto relativamente pequeño en la calidad de la solución.

«Mayores» es relativo a los métodos exactos de aquel momento, no al tamaño de un VRP operativo diario. Añadir la restricción generalmente renuncia a la garantía de optimalidad. Lea ese punto como la observación experimental del artículo.