Pamukkale Univ Muh Bilim Derg. 2021; 27(2): 187-198 | DOI: 10.5505/pajes.2020.75725

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

Muhammed Halat, Omer Ozkan
National Defense University, Turkish Air Force Academy, Industrial Engineering Department, Istanbul, Turkey

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.

Keywords: UAV routing, Vehicle routing, Genetic algorithm, Orienteering problem, Istanbul earthquake, Disaster management

---

Olas� �stanbul depreminin hasarlar�n�n g�zlenmesi i�in �HA rotalama probleminin bir genetik algoritma ile eniyilenmesi

Muhammed Halat, Omer Ozkan
Milli Savunma �niversitesi, Hava Harp Okulu Dekanl���, End�stri M�hendisli�i B�l�m Ba�kanl���, �stanbul, T�rkiye

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.

Anahtar Kelimeler: �HA rotalama, Ara� rotalama, Genetik algoritma, Oryantring problemi, �stanbul depremi, Afet y�netimi

---

CITE