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.

I. Introduction

Drones, also known as unmanned aerial vehicles (UAVs), are increasingly employed for last-mile goods delivery due to their speed and cost-efficiency [1], [2]. The rising demand for faster delivery and the growing need to reduce carbon emissions are driving the growth of electric UAV-based delivery, as these UAVs consume less energy and are less impacted by traffic congestion than land-based transport [3], [4], [5]. Commercial UAVs are powered by onboard batteries, restricting their flight distance and capability [6]. The delivery range can be expanded through flight planning and battery management [7], [8], [9], [10], but long-distance delivery remains challenging. Charging stations can help overcome battery limitations [11], [12], [13], [14], but they can also cause delays. It is important to carefully design UAV flight plans and charging schedules to balance delivery requirements and energy consumption.