E-ISSN: 2587-0351 | ISSN: 1300-2694
Pamukkale University Journal of Engineering Sciences The optimization of UAV routing problem with a genetic algorithm to observe the damages of possible Istanbul earthquake [Pamukkale Univ Muh Bilim Derg]
Pamukkale Univ Muh Bilim Derg. Ahead of Print: PAJES-75725 | 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



Corresponding Author: Omer Ozkan, Türkiye
LookUs & Online Makale