Unmanned Aerial Vehicles Surveillance Routing as a Multi-objective Team Orienteering Problem
摘要
In the team orienteering problem a fixed fleet of vehicles (i.e. unmanned aerial vehicles, self-driving vehicles) leaves the initial depot and, until reaching the destination, the fleet accumulates the rewards associated with each customer it visits, providing different routes that satisfy the time constraints. Although in these problems it is not mandatory to visit all customers, in this work we add the feature of prioritizing some of them. The objective of the paper is to identify the solutions of some real problems with these variations of the team orienteering problem scheme. Also, to obtain high quality solutions combining the bias-randomized heuristics with the weighted average method and simulation to maximize both values, reward obtained and priority customers visited. A small variation in the method is presented in order to obtain comparable or similar magnitudes in the two values that we want to maximize. In addition, we approach the problem from two different perspectives: considering time as a constant value and another more realistic approach considering time with dynamic values. To verify the performance of the proposed algorithms, different examples are executed and the results are shown graphically. To simplify decision making when maximizing a function with two objectives, Pareto frontiers are used in this work.