Heurıstıc Approaches for The Multı-Objectıve Routıng Problem for A Fleet of Unmanned Aerıal Vehıcles

Abstract

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 and reward 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.