An Efficient Genetic Algorithm for Routing Multiple UAVs under Flight Range and Service Time Window Constraints

Year 2017, Volume: 10 Issue: 1, 113 - 0, 24.01.2017

Murat Karakaya , Ender Sevinç

Abstract

Recently using Unmanned Aerial Vehicles (UAVs) either for military or civilian purposes is getting popularity. However, UAVs have their own limitations which require adopted approaches to satisfy the Quality of Service (QoS) promised by the applications depending on effective use of UAVs. One of the important limitations of the UAVs encounter is the flight range. Most of the time, UAVs have very scarce energy resources and, thus, they have relatively short flight ranges. Besides, for the applications using UAVs, there could be many customers to be serviced for the given service time windows. Moreover, the number of UAVs managed by the applications is also limited. Therefore, in real life applications, we face with an optimization problem such that for a given number of UAVs with a specific flight range, they should be servicing more customers in the predetermined time windows. In this problem, we would like to minimize the number of used UAVs and maximize the number of serviced customers meeting the time window requirement. For this reason, we have designed a Genetic Algorithm and validated its effectiveness via extensive simulation tests for various flight ranges, time windows, and customer topologies. Furthermore, the results of the proposed algorithm with a rival algorithm supporting the expected success have also been compared.

Keywords

Unmanned Aerial Vehicles, Route planning, Genetic Algorithm, Optimization, Simulation