论文标题
使用带有限制运动区域的无人机包装交付
Package Delivery Using Drones with Restricted Movement Areas
论文作者
论文摘要
对于使用一组无人机将软件包从源节点传递到目标节点的问题，我们研究了每个无人机的运动仅限于给定图的某个子图的设置。我们考虑将交付时间（问题DDT）和最小化总能耗（问题DDC）最小化的目标。对于一般图，我们显示出强烈的不XiBIMISINE结果和DDT以及NP硬度的匹配近似算法以及DDC的2-辅助算法。对于路径的特殊情况，我们表明，如果无人机具有不同的速度，DDT是NP-HARD。对于树木，我们在所有无人机都具有相同速度或相同能耗速率的假设下给出了最佳算法。如果每个无人机的子图是等距的，则树的结果扩展到任意图。
For the problem of delivering a package from a source node to a destination node in a graph using a set of drones, we study the setting where the movements of each drone are restricted to a certain subgraph of the given graph. We consider the objectives of minimizing the delivery time (problem DDT) and of minimizing the total energy consumption (problem DDC). For general graphs, we show a strong inapproximability result and a matching approximation algorithm for DDT as well as NP-hardness and a 2-approximation algorithm for DDC. For the special case of a path, we show that DDT is NP-hard if the drones have different speeds. For trees, we give optimal algorithms under the assumption that all drones have the same speed or the same energy consumption rate. The results for trees extend to arbitrary graphs if the subgraph of each drone is isometric.
