Resource-aware cooperative delivery mission planning for UAV and AGV

Abstract

In this study, a problem related to cooperative delivery mission planning of an unmanned aerial vehicle (UAV) and an autonomous ground vehicle (AGV) is con sidered. The problem is a new sub- variant of the Traveling Salesman Problem with Drone (TSP-D), known as a variant of the Traveling Salesman Problem (TSP) in the literature, and is called the Flying Sidekick Traveling Salesman Problem (FSTSP). Challenging part of the problem is that the UAV is able to carry only one package per flight and performs only one deliver mission as well. In the study, UAV is considered as able to take-off from warehouse or any delivery points on the route of AGV and land on the AGV on any delivery point on the route of AGV or warehouse. UAV takes the package for the next delivery point while staying on the AGV. Main constraints are taken as payload capacity (regarding weight of the package) and battery capacity of the UAV. Differently from original FSTSP model in the literature, a weight-aware energy consumption model is applied for the UAV and UAV has a chargeable battery with limited capacity. Main objective of the study is to develop a computation-time efficient algorithm by dynamic programming (DP) method to find the exact solution of cooperative delivery mission planning for UAV and AGV. The applicability of dynamic programming method instead of enumeration method was analyzed by considering ex ternal factors and constraints and it was proved that DP method has time efficiency compared to Enumeration method for increased number of delivery points. On the other hand, obtained results showed that determination of the value of battery capac ity and charging rate of the UAV take lead role for the cooperative delivery mission planning for UAV and AGV.