Dynamic Programming Approach for Drone Routes Planning

摘要

This paper addresses the routes planning problem in a scenario where an UAV (Unmanned Aerial Vehicle) and a land-based transportation vehicle are used to deliver parcels to customer locations. We developed and implemented a solution based on the well-known Bellman-Held-Karp dynamic programming algorithm for the Travelling Salesman Problem that finds the least-cost routes for both the aircraft and the land-based transportation vehicle. We applied this algorithm to different, randomly selected commercial drones, with different maximum velocity and flight range, in order to select the best performing drone for the lowest price.