Pamukkale University Journal of Engineering Sciences (Apr 2021)
The optimization of UAV routing problem with a genetic algorithm to observe the damages of possible Istanbul earthquake
Abstract
In this study, the problem is to find a route for a UAV that takes off from Istanbul to observe the damages that may occur after the possible Istanbul earthquake within the first 24 hours. In the problem, 230 candidate grid points that UAV can visit on Istanbul are determined and the weight values combining the risk values based on earthquake degree zones and the population densities of the grid points are calculated for each candidate point. It is aimed to find a route for the UAV to maximize the total weights of the visited grid points under the UAV range constraint. The described problem is adapted to the Orienteering Problem in the literature. Since the Orienteering Problem is an NP-hard problem, a problem-specific genetic algorithm and a simulated annealing algorithm are developed to solve the problem. The parameters of the algorithms are tuned by experiments. 15 different scenarios including the daily number of visits (of taken images) and the airports that the UAV takes and lands off after the earthquake are created and tried to be solved exactly via ILOG and approximately via developed metaheuristics. While the optimal solutions are found for 2 of 15 scenarios via ILOG, the designed genetic algorithm has better solutions and can solve the problem within acceptable CPU times for the rest of the scenarios.
