2022/11/12 by Saswata Jana, Jana, Saswata, Partha Sarathi Mandal +1
Computer Science · Engineering · #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Optimization and Search Problems #Transportation and Mobility Innovations #Vehicle Routing Optimization Methods
paper · pdf · doi:10.48550/arxiv.2211.06636
openalex publication_date 2022/11/12 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The coordination among drones and ground vehicles for last-mile delivery has gained significant interest in recent years. In this paper, we study \textitmultiple drone delivery scheduling problem(MDSP) \citeBettiICDCN22 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 (1)/(4)-approximation algorithm for MDSP with a constraint on the number of drones.