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.

Anahtar Kelimeler:

İHA rotalama, Araç rotalama, Genetik algoritma, Oryantring problemi, İstanbul depremi, Afet yönetimi

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.

Keywords:

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

PDF

___

[1] Boğaziçi Üniversitesi, Kandilli Rasathanesi ve Deprem Araştırmaları Enstitüsü. “İstanbul Metropolitan Alanının Deprem Risk Analizi”. http://www.koeri.boun.edu.tr/arastirma_3.depmuh (02.07.2019).
[2] Erdik M, Durukal E. “Earthquake risk and its mitigation in Istanbul”. Natural Hazards, 44, 181-197, 2008.
[3] Yu X, Zhang Y. “Sense and avoid technologies with applications to unmanned aircraft systems: review and prospects”. Progress in Aerospace Sciences, 74, 152-166, 2015.
[4] Griffin GF. “The use of unmanned aerial vehicles for disaster management”. Geomatica, 68(4), 265-281, 2014.
[5] Liu P, Chen AY, Huang YN, Han JY, Lai JS, Kang SC, Wu TH, Wen MC, Tsai MH. “A review of rotorcraft unmanned aerial vehicle (UAV) developments and applications in civil engineering”. Smart Structures and Systems, 13(6), 1065-1094, 2014.
[6] Mersheva V. UAV Routing Problem for Area Monitoring in a Disaster Situation. PhD Thesis, Alpen-Adria Universitat, Klagenfurt, Austria, 2015.
[7] Nedjati A, Vizvari B, Izbirak G. “Post-earthquake response by small UAV helicopters”. Natural Hazards, 80, 1669-1688, 2016.
[8] Zhu M, Du X, Zhang X, Luo H, Wang G. “Multi-UAV rapid-assessment task-assessment problem in a post-earthquake scenario”. IEEE Access, 7, 74542-74557, 2019.
[9] Coutinho WP, Battarra M, Fliege J. “The unmanned aerial vehicle routing and trajectory optimisation problem, a taxonomic review”. Computers & Industrial Engineering, 120, 116-128, 2018.
[10] Seyis A, Karacin Y, Ozkan O. “Optimal path planning with minimum number of UAVs by using genetic algorithm”. 28th European Conference on Operational Research (EURO 2016), Poznan, Poland, 3-6 July 2016.
[11] Ozkan O. “İnsansız hava araçları ile Türkiye’deki orman yangınlarının tespiti probleminin tavlama benzetimi ile eniyilenmesi”. 38. Ulusal Yöneylem Araştırması ve Endüstri Mühendisliği Kongresi (YAEM 2018), Eskişehir, Türkiye, 26-29 Haziran 2018.
[12] Kaya M, Ozkan O. “Sınır koruma görevi için insansız hava araçlarının rotalanması probleminin genetik algoritma ile eniyilenmesi”. 38. Ulusal Yöneylem Araştırması ve Endüstri Mühendisliği Kongresi (YAEM 2018), Eskişehir, Türkiye, 26-29 Haziran 2018.
[13] Ercan C, Gencer C. “Dinamik insansız hava sistemleri rota planlaması literatür araştırması ve insansız hava sistemleri çalışma alanları”. Pamukkale Üniversitesi Mühendislik Bilimleri Dergisi, 19(2), 104-111, 2013.
[14] Sahin Y, Karagul K. “Gezgin satıcı probleminin melez akışkan genetik algoritma (MAGA) kullanarak çözümü”. Pamukkale Üniversitesi Mühendislik Bilimleri Dergisi, 25(1), 106-114, 2019.
[15] Tsiligirides, T. “Heuristic methods applied to orienteering”. Journal of the Operational Research Society, 35(9), 797-809. 1984.
[16] Golden BL, Levy L, Vohra R. “The orienteering problem”. Naval Research Logistics, 34(3), 307-318, 1987.
[17] Ramesh R, Yoon YS, Karwan MH. “An optimal algorithm for the orienteering tour problem”. ORSA Journal of Computing, 4(2), 155-165, 1992.
[18] Chao IM, Golden BL, Wasil EA. “A fast and effective heuristic for the orienteering problem”. European Journal of Operational Research, 88(3), 475-489, 1996.
[19] Feillet D, Dejax P, Gendreau M. “Traveling salesman problems with profits: An overview”. ORP3 Conference, Paris, France, 26-29 September, 2001.
[20] Fomin FV, Lingas A. “Approximation algorithms for time-dependent orienteering”. Information Processing Letters, 83, 57-62, 2002.
[21] Boussier S, Feillet D, Gendreau M. “An exact algorithm for the team orienteering problem”. 4OR, 5(3), 211-230, 2007.
[22] Righini G, Salani M. “Decremental state space relaxation strategies and initialization heuristics for solving the orienteering problem with time windows with dynamic programming”. Computers & Operations Research, 36(4), 1191-1203, 2009.
[23] Bouly H, Dang DC, Moukrim A. “A memetic algorithm for the team orienteering problem”. 4OR, 8(1), 49-70, 2010.
[24] Tricoire F, Romauch M, Doerner KF, Hartl RF. “Heuristics for the multi-period orienteering problem with multiple time windows”. Computers & Operations Research, 37(2), 351-367, 2010.
[25] Campbell AM, Gendreau M, Thomas BW. “The orienteering problem with stochastic travel and service times”. Annals of Operations Research, 186(1), 61-81, 2011.
[26] Labadie N, Mansini R, Melechovsky J, Calvo WR. “Hybridized evolutionary local search algorithm for the team orienteering problem with time windows”. Journal of Heuristics, 17(6), 729-753, 2011.
[27] Vansteenwegen P, Souffriau W, Van Oudheusden D. “The orienteering problem: A survey”. European Journal of Operational Research, 209(1), 1-10, 2011.
[28] Labadie N, Mansini R, Melechovsky J, Calvo WR. “The team orienteering problem with time windows: An LP-based granular variable neighborhood search”. European Journal of Operational Research, 220(1), 15-27, 2012.
[29] Lin SW, Yu VF. “A simulated annealing heuristic for the team orienteering problem with time windows”. European Journal of Operational Research, 217(1), 94-107, 2012.
[30] Afsar HM, Labadie N. “Team orienteering problem with decreasing profits”. Electronic Notes in Discrete Mathematics, 41, 285-293, 2013.
[31] Archetti C, Bianchessi N, Speranza MG. “The capacitated team orienteering problem with incomplete service”. Optimization Letters, 7(7), 1405-1417, 2013.
[32] Dang DC, Guibadj RN, Moukrim A. A Branch-And-Cut Algorithm for Solving the Team Orienteering Problem. Editors: Gomes C., Sellmann M. Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems (CPAIOR 2013) Lecture Notes in Computer Science, vol 7874, Berlin, Heidelberg, Springer, 2013.
[33] Divsalar A, Vansteenwegen P, Cattrysse D. “A variable neighborhood search method for the orienteering problem with hotel selection”. International Journal of Production Economics, 145(1), 150-160, 2013.
[34] Lin SW. “Solving the team orienteering problem using effective multi-start simulated annealing”. Applied Soft Computing, 13(2), 1064-1073, 2013.
[35] Özdemir M. Zaman Kısıtı Altında Takım Oryantiring Problemlerinin Yapay Arı Kolonosi Yaklaşımı ile Çözümü. Yüksek Lisans Tezi, İstanbul Üniversitesi, İstanbul, Türkiye, 2013.
[36] Tarantilis CD, Stavropoulou F, Repoussis PP. “The capacitated team orienteering problem: A bi-level filter-and-fan method”. European Journal of Operational Research, 224(1), 65-78, 2013.
[37] Angelelli E, Archetti C, Vindigni M. “The clustered orienteering problem”. European Journal of Operational Research, 238(2), 404-414, 2014.
[38] Campos V, Marti R, Sanchez-Oro J, Duarte A. “GRASP with path relinking for the orienteering problem”. Journal of the Operational Research Society, 65(12), 1800-1813, 2014.
[39] Cura T. “An artificial bee colony algorithm approach for the team orienteering problem with time windows”. Computers & Industrial Engineering, 74, 270-290, 2014.
[40] Evers L, Glorie K, van der Ster S, Barros AI, Monsuur H. “A two-stage approach to the orienteering problem with stochastic weights”. Computers & Operations Research, 43, 248-260, 2014.
[41] Hu Q, Lim A. “An iterative three-component heuristic for the team orienteering problem with time windows”. European Journal of Operational Research, 232(2), 276-286, 2014.
[42] Salazar-Aguilar MA, Langevin A, Laporte G. “The multi-district team orienteering problem”. Computers & Operations Research, 41, 76-82, 2014.
[43] Verbeeck C, Sörensen K, Aghezzaf EH, Vansteenwegen P. “A fast solution method for the time-dependent orienteering problem”. European Journal of Operational Research, 236(2), 419-432, 2014.
[44] Zhang S, Ohlmann JW, Thomas BW. “A priori orienteering with time windows and stochastic wait times at customers”. European Journal of Operational Research, 239(1), 70-79, 2014.
[45] Duque D, Lozano L, Medaglia AL. “Solving the orienteering problem with time windows via the pulse framework”. Computers & Operations Research, 54, 168-176, 2015.
[46] Gavalas D, Konstantopoulos C, Mastakas K, Pantziou G, Vathis N. “Approximation algorithms for the arc orienteering problem”. Information Processing Letters, 115, 313-315, 2015.
[47] Gunawan A, Lau HC, Lu K. “Well-Tuned ILS for Extended Team Orienteering Problem with Time Windows”. Living Analytics Research Center, Singapore, Technical Report, 2015.
[48] Lin SW, Yu VF. “A simulated annealing heuristic for the multiconstraint team orienteering problem with multiple time windows”. Applied Soft Computing, 37, 632-642, 2015.
[49] Marinakis Y, Politis M, Marinaki M, Matsatsinis N. A Memetic-GRASP Algorithm for the Solution of the Orienteering Problem. Editors: Le Thi HA, Dinh TP, Nguyen N.T. Modelling, Computation and Optimization in Information Systems and Management Sciences, Advances in Intelligent Systems and Computing: 360, 105-116, Switzerland, Springer, 2015.
[50] Gunawan A, Lau HC, Vansteenwegen P. “Orienteering Problem: A survey of recent variants, solution approaches and applications”. European Journal of Operational Research, 255, 315-332, 2016.
[51] Yu J, Schwager M, Rus D. “Correlated orienteering problem and its application to persistent monitoring tasks”. IEEE Transactions on Robotics, 32(5), 1106-1118, 2016.
[52] Ostrowksi K, Karbowska-Chilinska J, Koszelew J, Zabielski P. “Evolution-inspired local improvement algorithm solving orienteering problem”. Annals of Operations Research, 253, 519-543, 2017.
[53] Hu W, Fathi M, Pardolos PM. “A multi-objective evolutionary algorithm based on decomposition and constraint programming for the multi-objective team orienteering problem with time windows”. Applied Soft Computing Journal, 73, 383-393, 2018.
[54] Tsakirakis E, Marinaki M, Marinakis Y, Matsatsinis N. “A similarity hybrid harmony search algorithm for the team orienteering problem”. Applied Soft Computing Journal, 80, 776-796, 2019.
[55] Holland JH. Adaptation in Natural and Artificial Systems, Michigan, USA, University of Michigan Press, 1975.
[56] Aarts E, Korst J. Simulated Annealing and Boltzmann Machines: A Stochastic Approach to Combinatorial Optimization and Neural Computing, New York, USA, Wiley, 1989.
[57] Türk Mühendis ve Mimar Odaları Birliği (TMMOB). “İstanbul Deprem Raporu” https://www.tmmob.org.tr/sites/default/files/rapor_2017_son.pdf (02/07/2019).
[58] T.C. Çevre ve Şehircilik Bakanlığı. “İstanbul Deprem Bölgeleri Dağılımı Haritası”. https://istanbulakdm.csb.gov.tr/istanbul-deprem-bolgeleri-dagilimi-haritasi-i-3712 (02/07/2019).
[59] Türkiye İstatistik Kurumu “Merkezi Dağıtım Sistemi”. https://biruni.tuik.gov.tr/medas/?kn=95&locale=tr (02/07/2019).
[60] Atlasbig. “İstanbul Mahalleleri Nüfus Yoğunluğu”. https://www.atlasbig.com/tr/istanbul-mahalleleri-nufus-yogunlugu (02/07/2019).