基于仓库的无人机包裹递送的近似线性时间调度

《ACM Journal on Autonomous Transportation Systems》：Near-Linear Time Scheduling for Drone-Based Parcel Delivery from a Warehouse

针对多无人机仓库配送问题，本研究将LPT启发式算法扩展至无人机场景，并提出基于动态维护下界包络线的近线性时间算法，有效提升调度效率。

　　

摘要

我们考虑这样一个问题：一个仓库配备多架无人机，需要将包裹送达多个客户手中。每架无人机从仓库取一个包裹，送达目的地后再返回仓库。不同无人机之间的飞行速度和电池续航时间各不相同，由于电池寿命的限制，每架无人机都有其可覆盖的有限配送范围。我们的目标是合理分配包裹给这些无人机，以最小化完成所有包裹配送所需的总时间。这个问题属于NP难问题，因此本文的重点是设计一种高效的近似算法。我们通过将经典的“最长处理时间优先”（Longest Processing Time First, LPT）启发式方法进行改造，将其应用于“无人机仓库问题”（Drones Warehouse Problem, DWP），后者实际上是均匀机器调度问题的一个自然扩展。我们证明了使用LPT启发式方法解决该问题的近似因子为?，其中?约等于1.62（即黄金分割比）。

LPT启发式方法最初由Gonzalez等人提出（SIAM J. Comput. 6(1):155–166, 1977）。此后，人们进行了大量研究以改进LPT启发式的近似因子。然而，所有已知的LPT实现方法的时间复杂度均为O(mn)，其中m表示机器数量，n表示任务数量。在这项工作中，我们首次提出了适用于DWP和均匀调度问题的“接近线性时间”的LPT实现方案，其运行时间为O((n + m)(log2m + logn))。值得注意的是，这一结果是通过将问题映射到计算几何学中广泛研究的“下包络线动态维护”问题来获得的。