Decision making in a UAV-based delivery system with impatient customers

Abstract

This article introduces a framework to compute decision making policies (mission planning) for a UAV-based delivery system serving impatient customers. Customers arrive on a finite number of locations L separated by arbitrary but fixed distances and eventually leave if not served. Policies seek to minimize the average net cost (maximize the average net revenue), i.e. loss from customers' abandonment deprived of the revenue from successful services. We introduce a novel model for the stochastic and dynamic pickup and delivery problem based on semi-Markov decision processes, and show the dependence of the optimal average net cost on the minimum distance between locations δ. Furthermore, we propose a feature-based state aggregation method to overcome the curse of dimensionality due to the exact modeling. The selection of relevant features is based on their correlation with the optimal performance. We show that the distance to the nearest pickup location dominates on other features for almost all δ. Based on this observation, we introduce the policy nearest neighbor or none, a policy with computational complexity O(L3) in many cases of interest. We show that this policy performs considerably better that the nearest neighbor (greedy) policy, and reaches the optimum for some δ.