Energy-Constrained Delivery of Goods with Drones under Varying Wind Conditions
Abstract
In this paper, we study the feasibility of sending drones to deliver goods from a depot to a customer by solving what we call the Mission-Feasibility Problem (MFP). Due to payload constraints, the drone can serve only one customer at a time. To this end, we propose a novel framework based on time-dependent cost graphs to properly model the MFP and tackle the delivery dynamics. When the drone moves in the delivery area, the global wind may change thereby affecting the drone's energy consumption, which in turn can increase or decrease. This issue is addressed by designing three algorithms, namely: (i) compute the route of minimum energy once, at the beginning of the mission, (ii) dynamically reconsider the most convenient trip towards the destination, and (iii) dynamically select only the best local choice. We evaluate the performance of our algorithms on both synthetic and real-world data. The changes in the drone's energy consumption are reflected by changes in the cost of the edges of the graphs. The algorithms receive the new costs every time the drone flies over a new vertex, and they have no full knowledge in advance of the weights. We compare them in terms of the percentage of missions that are completed with success (the drone delivers the goods and comes back to the depot), with delivered (the drone delivers the goods but cannot come back to the depot), and with failure (the drone neither delivers the goods nor comes back to the depot).
Recommended Citation
F. B. Sorbelli et al., "Energy-Constrained Delivery of Goods with Drones under Varying Wind Conditions," IEEE Transactions on Intelligent Transportation Systems, vol. 22, no. 9, pp. 6048 - 6060, Institute of Electrical and Electronics Engineers (IEEE), Sep 2021.
The definitive version is available at https://doi.org/10.1109/TITS.2020.3044420
Department(s)
Computer Science
Research Center/Lab(s)
Intelligent Systems Center
Second Research Center/Lab
Center for High Performance Computing Research
Keywords and Phrases
Batteries; Drone delivery algorithms; Drones; Energy consumption; energy model; Heuristic algorithms; mission feasibility problem.; Payloads; Shortest path problem; time-dependent cost graphs; Vehicle dynamics; wind model
International Standard Serial Number (ISSN)
1524-9050; 1558-0016
Document Type
Article - Journal
Document Version
Citation
File Type
text
Language(s)
English
Rights
© 2020 Institute of Electrical and Electronics Engineers (IEEE), All rights reserved.
Publication Date
01 Sep 2021
Comments
Published online: 29 Dec 2020
This work was supported in part by the Intelligent Systems Center (ISC) at Missouri S&T; in part by the National Science Foundation (NSF) under Grant CNS-1545050, Grant CNS-1725755, and Grant SCC-1952045; and in part by the Fondo Ricerca di Base 2019, UNIPG.