Exact methods for the traveling salesman problem with drone

Roberti, R., & Ruthmair, M. · 2021

full-text

这项工作推进了精确方法在一辆卡车加一架无人机路线问题上所能达到的规模。“求解到三十九个客户”这句话不能换成“求解了一座城市”。本卡片放在书架上，就是为了阻止这种替换。

已发表的摘要称，他们将动态规划递推引入基于集合划分模型的分支定价方法，并使用 ng-route 松弛和三级分层分支。作者写道，这一分支定价方法可将最多三十九个客户的算例求解至最优，使当时认为可处理的规模翻了一倍以上。其情景还表明，一架速度足够快的无人机可以显著缩短路线完成时间。

三十九是一个算例中的客户数量。风、禁飞空域、电池老化与监管许可并不是精确方法的核心。“显著”是作者在其速度假设下的用词，而不是某个具体城市的分钟数。本卡片未重新推导全文。