论文标题
无人机交付调度问题的近似算法
Approximation Algorithms for Drone Delivery Scheduling Problem
论文作者
论文摘要
近年来，无人机和地面车辆之间的协调引起了人们的重大兴趣。在本文中，我们研究\ textit {多个无人机交付计划问题（MDSP）\ cite {betti_icdcn22}用于最后一英里的交付，在那里我们有一组具有相同电池预算的无人机，以及一组交货地点，以及交付，成本和交付时间间隔的奖励或利润。 MDSP的目的是为每个无人机找到无冲突时间表的集合，以使交付总利润受到无人机的电池限制的最大约束。在这里，我们为单个无人机交付调度问题（SDSP）和$ \ frac {1} {4} $ - MDSP的近似算法提出了一个完全多项式时间近似方案（FPTA），并限制了无人机数量。
The coordination among drones and ground vehicles for last-mile delivery has gained significant interest in recent years. In this paper, we study \textit{multiple drone delivery scheduling problem(MDSP) \cite{Betti_ICDCN22} for last-mile delivery, where we have a set of drones with an identical battery budget and a set of delivery locations, along with reward or profit for delivery, cost and delivery time intervals. The objective of the MDSP is to find a collection of conflict-free schedules for each drone such that the total profit for delivery is maximum subject to the battery constraint of the drones. Here we propose a fully polynomial time approximation scheme (FPTAS) for the single drone delivery scheduling problem (SDSP) and a $\frac{1}{4}$-approximation algorithm for MDSP with a constraint on the number of drones.
