论文标题
无人机交付包装问题的近似算法
Approximation Algorithms for Drone Delivery Packing Problem
论文作者
论文摘要
无人驾驶飞机（也称为无人机）的最新进展激发了物流，将无人机用于多次操作。在最后一英里交付系统中，无人机和卡车之间的协作具有许多好处，并减少了许多挑战。在本文中，我们介绍了\ textit {无人机交付包装问题}（DDP），在那里我们有一套交货和各自的客户，其处方位置，交付时间间隔，相关的交付成本以及一组具有相同电池预算的无人机。 DDP的目的是通过使用受电池预算的最小无人机数量以及每份无人机分配的兼容性来找到所有向无人机交付的任务。我们证明了DDP是NP-固定的，并为其制定了整数线性编程（ILP）公式。我们提出了DDP的两种贪婪近似算法。第一个算法最多使用$ 2opt +（δ + 1）$无人机。第二个算法最多使用$ 2OPT +ω$无人机，其中OPT是DDP的最佳解决方案，$ω$是最大集团大小，而$δ$是从交付时间间隔构建的间隔图$ G $的最大程度。
Recent advancements in unmanned aerial vehicles, also known as drones, have motivated logistics to use drones for multiple operations. Collaboration between drones and trucks in a last-mile delivery system has numerous benefits and reduces a number of challenges. In this paper, we introduce \textit{drone-delivery packing problem} (DDP), where we have a set of deliveries and respective customers with their prescribed locations, delivery time intervals, associated cost for deliveries, and a set of drones with identical battery budgets. The objective of the DDP is to find an assignment for all deliveries to the drones by using the minimum number of drones subject to the battery budget and compatibility of the assignment of each drone. We prove that DDP is NP-Hard and formulate the integer linear programming (ILP) formulation for it. We proposed two greedy approximation algorithms for DDP. The first algorithm uses at most $2OPT + (Δ+ 1)$ drones. The second algorithm uses at most $2OPT + ω$ drones, where OPT is the optimum solution for DDP, $ω$ is the maximum clique size, and $Δ$ is the maximum degree of the interval graph $G$ constructed from the delivery time intervals.
