A heuristics based approach for optimizing delivery schedule of an Unmanned Aerial Vehicle (Drone) based delivery system

摘要

In this work we address the problem of computing a delivery schedule for drones in an Unmanned Aerial Vehicle delivery system. The problem specification consists of a set of orders (each order contains a list of items with quantity) to be delivered to customers whose locations are known, also specified are locations of warehouses and drones. The aim is to minimize the time for completing a batch of order deliveries. The problem has some of the features of the Vehicle Routing Problem (as well as the Travelling Salesman Problem), however the increased number of constraints and dynamic nature of the problem are the distinguishing features in this setting. As most versions of the problem are NP-hard we employ a heuristics based approach since such an approach would be more suitable to solve large scale instances of the problem that might be encountered by a commercial delivery service. The proposed heuristics are compared with regard to the quality of solution and computation overhead.