An Optimal Routing Algorithm for Unmanned Aerial Vehicles

Autor: Soo-Yeon Kim, Byoungryul Oh, Jae Hyun Kwak, Da-Han Lee, Duehee Lee
Rok vydání: 2021
Předmět:
0209 industrial biotechnology
Computer science
Real-time computing
ComputingMethodologies_IMAGEPROCESSINGANDCOMPUTERVISION
0211 other engineering and technologies
ComputerApplications_COMPUTERSINOTHERSYSTEMS
02 engineering and technology
lcsh:Chemical technology
mixed integer linear programming
ComputingMethodologies_ARTIFICIALINTELLIGENCE
Biochemistry
subtour elimination
Analytical Chemistry
020901 industrial engineering & automation
Range (aeronautics)
unmanned aerial vehicle
network optimization
subtour elimination
network optimization
lcsh:TP1-1185
ComputerSystemsOrganization_SPECIAL-PURPOSEANDAPPLICATION-BASEDSYSTEMS
Electrical and Electronic Engineering
Instrumentation
Virtual network
Service (business)
021103 operations research
Communication
Process (computing)
Routing algorithm
multiple depots vehicle routing problem
Atomic and Molecular Physics
and Optics
Zdroj: Sensors (Basel, Switzerland)
Sensors, Vol 21, Iss 1219, p 1219 (2021)
ISSN: 1424-8220
DOI: 10.3390/s21041219
Popis: 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.
Databáze: OpenAIRE
Externí odkaz: