Optimal Charging Scheduling and Speed Control for Delay-Bounded Drone Delivery

Unmanned aerial vehicles (UAVs) have demonstrated success in delivering goods, but their delivery distances are limited due to their finite battery capacity. While roadside charging stations can replenish the battery, they cause delays and prevent timely delivery. In this paper, we present a novel UAV charging scheduling and speed control framework that optimizes the decisions on flight speed and charging schedule at roadside charging stations to achieve timely and energy-efficient goods delivery. The approach we take is to first formulate a finite-horizon Markov decision process (FH-MDP) problem and then analytically and rigorously reveal the underlying structure of the optimal solution to the problem. Specifically, a FH-MDP is put forth to minimize the energy requirement of the UAV while guaranteeing timely delivery at the destination. We analytically reveal an underlying monotone deterministic Markovian policy, asserting that the optimal charging time and speed are monotonic regarding the distance remaining and the time elapsed. We also show that the optimal charging time and speed change only when the UAV reaches the derived distance- and time-related thresholds. Simulations also show that our approach can extend the flight distance of the UAV by at least 19.8% under our simulation setting, compared to the benchmarks.