Greedy Algorithms for Scheduling Package Delivery with Multiple Drones
Abstract
Unmanned Aerial Vehicles (or drones) can be used for a myriad of civil applications, such as search and rescue, precision agriculture, or last-mile package delivery. Interestingly, the cooperation between drones and ground vehicles (trucks) can even enhance the quality of service. In this paper, we investigate the symbiosis among a truck and multiple drones in a last-mile package delivery scenario, introducing the Multiple Drone-Delivery Scheduling Problem (MDSP). From the main depot, a truck takes care of transporting a team of drones that will be used to deliver packages to customers. Each delivery is associated with a drone's energy cost, a reward that characterizes the priority of the delivery, and a time interval representing the launch and rendezvous times from and to the truck. The objective of MDSP is to find an optimal scheduling for the drones that maximizes the overall reward subject to the drone's battery capacity while ensuring that the same drone performs deliveries whose time intervals do not intersect. After showing that MDSP is an NP-hard problem, we devise an optimal Integer Linear Programming (ILP) formulation for it. Consequently, we design a heuristic algorithm for the single drone case and two more heuristic algorithms for the multiple drone case. Finally, we thoroughly compare the performance of our presented algorithms on different synthetic datasets.
Recommended Citation
F. Betti Sorbelli et al., "Greedy Algorithms for Scheduling Package Delivery with Multiple Drones," ACM International Conference Proceeding Series, pp. 31 - 39, Association for Computing Machinery (ACM), Jan 2022.
The definitive version is available at https://doi.org/10.1145/3491003.3491028
Meeting Name
23rd International Conference on Distributed Computing and Networking, ICDCN 2022 (2022: Jan. 4-7, Delhi, India)
Department(s)
Computer Science
Keywords and Phrases
Drone; Last-Mile Delivery System; Truck
International Standard Book Number (ISBN)
978-145039560-1
Document Type
Article - Conference proceedings
Document Version
Citation
File Type
text
Language(s)
English
Rights
© 2022 Association for Computing Machinery (ACM), All rights reserved.
Publication Date
07 Jan 2022
Comments
This work was partially supported by NSF grants CNS-1818942, OAC-1725755, OAC-2104078, and SCC-1952045; and also partially supported by "HALY-ID" project funded by the European Union’s Horizon 2020 under grant agreement ICT-AGRI-FOOD no. 862665, no. 862671, and from MIPAAF .