Olasý Ýstanbul depreminin hasarlarýnýn gözlenmesi için ÝHA rotalama probleminin bir genetik algoritma ile eniyilenmesi

Bu çalýþmada, olasý Ýstanbul depremi sonrasý oluþabilecek hasarlarý havadan gözlemlemek için ilk 24 saat içerisinde Ýstanbul’dan kaldýrýlan bir ÝHA’nýn hangi rotada uçmasý gerektiði problemi ele alýnmýþtýr. Problemde, Ýstanbul üzerinde ÝHA’nýn ziyaret edebileceði 230 aday grid nokta belirlenmiþ ve her aday nokta için noktanýn deprem riski aðýrlýðý ile nüfus yoðunluðunu birleþtiren aðýrlýk deðerleri belirlenmiþtir. Problemde en fazla sayýda aday noktanýn aðýrlýðýný toplayacak þekilde ÝHA’nýn menzil kýsýtý altýnda rotalanmasý amaçlanmýþtýr. Tanýmlanan bu problem, literatürdeki Oryantring problemine uyarlanmýþtýr. Oryantring problemi NP-zor bir problem olduðundan dolayý, problemin çözümü için probleme özgü bir genetik algoritma ve bir tavlama benzetimi algoritmasý geliþtirilmiþtir. Algoritmalarýn parametreleri deneyler ile ayarlanmýþtýr. Gerçek hayata uygun olarak deprem sonrasý ÝHA’nýn kalktýðý havalimaný ile günlük ziyaret (veya görüntü sayýsý) durumlarýný kapsayan 15 farklý senaryo oluþturulmuþ ve senaryolar ILOG ile kesin ve geliþtirilen metasezgisel algoritmalar ile yaklaþýk olarak çözülmeye çalýþýlmýþtýr. 15 senaryonun 2’sinde optimal çözüm bulunmuþ olup diðer senaryolar için genetik algoritma daha iyi sonuçlar elde etmiþ ve kabul edilebilir CPU süreleri içinde problemi çözebilmiþtir.

The optimization of UAV routing problem with a genetic algorithm to observe the damages of possible Istanbul earthquake

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.