Heuristic approaches for the multi-objective routing problem for a fleet of unmanned aerial vehicles

Abstract

Günümüzde, İnsansız Hava Araçları (İHA'lar), farklı amaçlarla çeşitli görevlerde yaygın olarak kullanılmaktadır. Her görevde, farklı amaçlar ve problem yapıları göz önünde bulundurulmaktadır. Bu tezde, özdeş İHA'lardan oluşan bir İHA filosunun rotalama problemi, birden fazla amaç gözetilerek incelenmiştir. Filodaki İHA'lar, sahip oldukları sınırlı uçuş süreleri içerisinde ve iki boyutlu bir görev alanında hareket etmek üzere, bir üsten ayrılır, belirli bir sayıdaki hedefi ziyaret eder ve üsse geri dönerler. Hedeflerin farklı öncelikleri olduğu varsayılmakta olup İHA'ların maksimum seviyede ödül toplamak için uçuş limitleri dahilinde mümkün olduğu kadar çok hedefi ziyaret etmeye çalışması beklenir. Bu çalışmadaki rotalama probleminde göz önünde bulundurulan üç amaç: filonun kat ettiği toplam mesafeyi en aza indirgemek, hedeflerden toplanan toplam ödülü en üst seviyeye çıkarmak ve toplam radar tehdidini en aza indirmektir. Rotalama probleminin iki versiyonu ele alınmıştır. Bu versiyonlar: radarsız bir alanda rotalama (amaç olarak mesafe ve ödül gözetilerek) ve radarla izlenen bir arazide rotalamadır (her üç amaç da gözetilerek). Filodaki her İHA için etkin bir rota ve her rotadaki hedef çiftleri arasında etkin yollar bulmak amaçlanmıştır.Problemin her iki versiyonu için iki çözüm yaklaşımı kullanılmıştır. İlk yaklaşımda, problem Çok Amaçlı Takım Oryantiring Problemi olarak modellenmiş ve kesin çözümler bulunmuştur. İkinci yaklaşımda, makul sürede etkin çözümler üretmek için evrimsel bir algoritma olan EA-fUAV kullanılmıştır. Her iki yaklaşım da üç farklı problem vakasında test edilmiştir. Sonuçlar, EA-fUAV'ın etkin çözüm setine makul bir zamanda yaklaştığını göstermektedir.

Nowadays, Unmanned Aerial Vehicles (UAVs) are extensively employed for various missions with different purposes. In every mission, different goals and problem structures are considered. In this thesis, we study the routing problem of a fleet of identical UAVs under multiple objectives. UA Vs in the fleet, which have limited flight durations, take off from a base, visit a number of targets in a two-dimensional mission area, and return to the base. We assume that the targets have different priorities, and the UAVs try to visit as many targets as possible to collect maximum reward within flight limits. We consider the following three objectives: minimizing the total distance traveled by the fleet, maximizing the total reward collected from the targets, and minimizing the total radar threat. We address two versions of the problem: routing in a radar-free terrain (with distance andeward as objectives) and routing in a radar-monitored terrain (with all three objectives). We aim to find efficient routes for each UAV in the fleet and the trajectory between pairs of targets in each route.We employ two solution approaches for each version of our problem. First, we model the problem as a Multi-Objective Team Orienteering Problem (MOTOP) and find exact solutions. In our second approach, we utilize an Evolutionary Algorithm, EA-fUAV (Evolutionary Algorithm for routing a fleet of UAVs), to approximate efficient solutions in reasonable time. We test both approaches on three different problem cases. The results show that EA-fUAV approximates the efficient set well in reasonable time.