Journal
IEEE TRANSACTIONS ON INTELLIGENT TRANSPORTATION SYSTEMS
Volume 22, Issue 9, Pages 6048-6060Publisher
IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC
DOI: 10.1109/TITS.2020.3044420
Keywords
Drones; Heuristic algorithms; Payloads; Energy consumption; Vehicle dynamics; Batteries; Shortest path problem; Drone delivery algorithms; energy model; wind model; time-dependent cost graphs; mission feasibility problem
Categories
Funding
- Intelligent Systems Center (ISC) at Missouri ST
- National Science Foundation (NSF) [CNS-1545050, CNS-1725755, SCC-1952045]
- Fondo Ricerca di Base 2019, UNIPG
Ask authors/readers for more resources
This paper examines the feasibility of using drones for goods delivery from a depot to customers, utilizing a novel framework based on time-dependent cost graphs and three algorithms to optimize energy consumption and route selection. The performance of the algorithms is evaluated on synthetic and real-world data, comparing success rates of completed, delivered, and failed missions.
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).
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available