Dynamic Programming Approach for Drone Routes Planning
Hristijan Gjorshevski, Kire V. Trivodaliev, Ivana Nižetić Kosović, Slobodan Kalajdziski, Biljana Risteska Stojkoska · 2018
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.