Uçuş Menzili ve Hizmet Süresi Kısıtları Altında Çoklu İHA Yönlendirme için Etkin Genetik Algoritma

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

Özet

Son zamanlarda gerek askeri gerekse sivil amaçlı İnsansız Hava Aracı (İHA) kullanımı giderek popülerlik kazanmaktadır. Ancak İHA'ların etkin kullanımı için gerekli Servis Kalitesi(QoS)'ni karşılaması için benimsenen yaklaşımlarının sınırlamaları vardır. İHA'lar arasındaki kıyaslamanın önemli sınırlarından biri de uçuş menzilidir. Çoğu zaman, İHA'ların, yeterli enerji kaynağı olmaması ve böylelikle nispeten kısa uçuş menzillerine sahip olmalarıdır. İlave olarak, İHA'ları kullanan uygulamalar için, verilen hizmet süresi zamanı içerisinde ziyaret edilmesi gereken pek çok nokta olabilir. Üstelik, uygulamalar tarafından yönlendirilecek İHA'ların sayısı da sınırlıdır. Bu nedenle, gerçek hayattaki uygulamalarda, önceden belirlenen zaman aralığı pencerelerinde daha fazla noktanın ziyaret edilmesi maksadıyla belirli bir uçuş menzili olan çok sayıda İHA için bir optimizasyon sorunu ile karşılaşılmaktadır. Bu problemde biz, kullanılan İHA sayısını en aza indirmek ve zaman aralığı içerisinde ziyaret edilecek nokta sayısını en üst düzeye çıkarmak istiyoruz. Bu nedenle, Genetik bir algoritma tasarladık ve çeşitli uçuş menzilleri, servis zaman aralıkları ve nokta ağ topolojileri için kapsamlı simülasyon testleri yoluyla etkinliğini doğruladık. Daha da ötesinde, tasarlanan algoritma ile arzu edilen başarıyı sağlayabilecek rakip bir algoritma ile de sonuçlar karşılaştırılmıştır.

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). 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.