Job Selection in a Network of Autonomous UAVs for Delivery of Goods

Authors: Pasquale Grippa, Doris Behrens, Christian Bettstetter, Friederike Wall

This article analyzes two classes of job selectionpolicies that control how a network of autonomous aerial vehiclesdelivers goods from depots to customers. Customer requests(jobs) occur according to a spatio-temporal stochastic processnot known by the system. If job selection uses a policy in whichthe first job (FJ) is served first, the system may collapse toinstability by removing just one vehicle. Policies that serve thenearest job (NJ) first show such threshold behavior only in somesettings and can be implemented in a distributed manner. Thetiming of job selection has significant impact on delivery time andstability for NJ while it has no impact for FJ. Based on thesefindings we introduce a methodological approach for decision-making support to set up and operate such a system, taking intoaccount the trade-off between monetary cost and service quality.In particular, we compute a lower bound for the infrastructureexpenditure required to achieve a certain expected delivery time.The approach includes three time horizons: long-term decisionson the number of depots to deploy in the service area, mid-term decisions on the number of vehicles to use, and short-termdecisions on the policy to operate the vehicles.