Dynamic programming approaches for the traveling salesman problem with drone

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

full-text

与同一批作者的启发式论文不同，这篇用动态规划精确求解 TSP-D。讨论精确求解能处理多大规模的算例时，人们引用的就是这两篇。该算法未重新实现。

该文提出了精确的动态规划方法，并报告其求解的问题规模大于当时文献中的数学规划方法。据报告，限制无人机离开期间卡车可访问的地点数量能大幅缩短求解时间，而对解的质量影响相对较小。

“更大”是相对于当时的精确方法而言，而非相对于日常运营 VRP 的规模。加入该限制通常会放弃最优性保证。请把这一点视为论文的实验观察。