.png){kind=icon}
.png){kind=icon}
Return
Approximation Algorithms for Drone Delivery Scheduling Problem
.png){kind=icon}
PRE
AI
DOI：10.1007/978-3-031-37765-5_10.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
The coordination among drones and ground vehicles for last-mile delivery has gained significant interest in recent years. In this paper, we study multiple drone delivery scheduling problem (MDSP) [3] for last-mile delivery, where we have a set of drones with an identical battery budget and a set of delivery locations, along with profit for delivery, cost and delivery time intervals. The objective of the MDSP is to find conflict-free schedules for each drone such that the total profit gained is maximum subject to the battery constraint of the drones. In this paper, we propose a fully polynomial time approximation scheme (FPTAS) for the single drone delivery scheduling problem (SDSP) and a 1/3-approximation algorithm for MDSP with a constraint on the number of drones. We also describe a deterministic rounding algorithm for the problem by relaxing the integer linear programming(ILP) formulation of the problem.
Keywords:
Approximation Algorithm
Drone Delivery Scheduling
Truck
Last-mile Delivery
Journal
N
IF:
0
Papers:
3
Citations:
0