Optimization approaches for the traveling salesman problem with drone

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

full-text

这篇论文确立了“带无人机的旅行商问题”（traveling salesman problem with drone）这一名称，以及“先路径、后聚类”分配无人机客户的方法。它与纯计算类短文的区别在于还讨论了最坏情况下的近似比。本卡片记录引用信息与通行结论，不保证重新通读了完整 PDF。

该文将卡车与无人机协同建模为整数规划，并提出了基于局部搜索和动态规划的启发式算法。小规模算例与最优解进行比较，较大的人工算例则与纯卡车配送比较。在这些实验设定下，作者认为可以实现可观的节省。

节省幅度取决于对速度比、续航和客户分布的假设。“可以节省”的结论并不承诺每座城市都有同样的比例。监管与多无人机运行不在该模型范围内。

巡检面临同样的问题：自主线路巡检已有综述，其中包括车辆支持。请参阅Automatic autonomous vision-based power line inspection（Inspection 指南）。