Drone Systems for Delivery of Goods

We consider a fleet of drones delivering goods to customers scattered on a certain service area. Customers (jobs) arrive according to a space-temporal stochastic process, and vehicles autonomously decide which customer to serve (job selection) in order to optimize some performance metrics (delivery time or profit per delivery). We address two complementary problems in these systems: 1) Dimensioning the system, i.e. choosing the right number of depots and vehicles, and 2) computing policies to control the vehicles. An incorrect dimensioning may prevent to achieve a certain level of service, or may lead to instability (customers waiting forever). An ineffective job selection policy may considerably decrease the performance. To address the first problem, we analyze the performance of two classes of job section policies "first job first" and "nearest job first". We show that the choice of the best policy depends on the operating conditions and on the timing of job selection. Furthermore, we compute a lower bound to the cost necessary to have a certain delivery time. Based on these results, we introduce a method to dimension the system and balance the trade-off between infrastructure expenditure and service level. To address the second problem, we introduce a novel semi-Markov model that enables the computation of optimal policies. The complexity related to the exact modeling makes the computation of the optimal policy unfeasible for real scenarios. To overcome this problem we introduce an approximation method leading to near-optimal performance and applicable in real scenarios.