An Optimal Routing Algorithm for Unmanned Aerial Vehicles

Abstract

A delivery service using unmanned aerial vehicles (UAVs) has potential as a future business opportunity, due to its speed, safety and low-environmental impact. To operate a UAV delivery network, a management system is required to optimize UAV delivery routes. Therefore, we create a routing algorithm to find optimal round-trip routes for UAVs, which deliver goods from depots to customers. Optimal routes per UAV are determined by minimizing delivery distances considering the maximum range and loading capacity of the UAV. In order to accomplish this, we propose an algorithm with four steps. First, we build a virtual network to describe the realistic environment that UAVs would encounter during operation. Second, we determine the optimal number of in-service UAVs per depot. Third, we eliminate subtours, which are infeasible routes, using flow variables part of the constraints. Fourth, we allocate UAVs to customers minimizing delivery distances from depots to customers. In this process, we allow multiple UAVs to deliver goods to one customer at the same time. Finally, we verify that our algorithm can determine the number of UAVs in service per depot, round-trip routes for UAVs, and allocate UAVs to customers to deliver at the minimum cost.

Keywords

• unmanned aerial vehicle
• multiple depots vehicle routing problem
• subtour elimination
• network optimization
• mixed integer linear programming