Decision Making in a UAV-Based Delivery...

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(L 3 ) 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 δ.