Load and Wind Aware Routing of Delivery Drones

Abstract

Delivery drones have been attracting attention as one of the promising technologies to deliver packages. Several research studies on routing problems specifically for drone delivery scenarios have extended Vehicle Routing Problems (VRPs). Most existing VRPs are based on Traveling Salesman Problems (TSPs) for minimizing the overall distance. On the other hand, VRPs for drone delivery have been aware of energy consumption due to the consideration of battery capacity. Despite hovering motions with loading packages accounting for a large portion of energy consumption since delivery drones need to hover with several packages, little research has been conducted on drone routing problems that aim at the minimization of overall flight times. In addition, flight time is strongly influenced by windy conditions such as headwinds and tailwinds. In this paper, we propose a VRP for drone delivery in which flight time is dependent on the weight of packages in a windy environment, called Flight Speed-aware Vehicle Routing Problem with Load and Wind (FSVRPLW). In this paper, flight speed changes depending on the load and wind. Specifically, a heavier package slows down flight speeds and a lighter package speeds up flight speeds. In addition, a headwind slows down flight speeds and a tailwind speed up flight speeds. We mathematically derived the problem and developed a dynamic programming algorithm to solve the problem. In the experiments, we investigate how much impact both the weight of packages and the wind have on the flight time. The experimental results indicate that taking loads and wind into account is very effective in reducing flight times. Moreover, the results of comparing the effects of load and wind indicate that flight time largely depends on the weight of packages.

Keywords

• drone routing problem
• flight speed-aware vehicle routing problem
• dynamic programming algorithm
• drone