Package Delivery Using Drones with Restricted Movement Areas
Package Delivery Using Drones with Restricted Movement Areas
复制标题
DOI：
10.48550/arxiv.2209.12314
复制
发表时间：
2022-09
期刊：
影响因子：
--
通讯作者：
T. Erlebach;Kelin Luo;F. Spieksma
中科院分区：
文献类型：
--
作者：
T. Erlebach;Kelin Luo;F. Spieksma
对于使用一组无人机将包裹从源节点递送到图中的目的地节点的问题，我们研究了每个无人机的移动被限制在给定图的某个子图的设置。我们考虑的目标，最大限度地减少交货时间（问题DDT）和最大限度地减少总能耗（问题DDC）。对于一般的图，我们证明了一个强的不可逼近的结果和匹配的近似算法的DDT以及NP-硬度和2-近似算法的DDC。对于路径的特殊情况下，我们证明了DDT是NP-难的，如果无人机有不同的速度。对于树，我们在假设所有无人机具有相同的速度或相同的能耗率的情况下给出了最优算法。树的结果推广到任意图，如果每个drone的子图是等距的。
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.