Hareketli Hedefli - Heterojen Filolu İHA Rotalama Problemi İçin Yeni Bir Çözüm Yaklaşımı

Savunma sanayinde yaşanan teknolojik gelişmeler, ülkeleri robotik sistemlere dayalı askersiz ordular oluşturmaya yönlendirmektedir. Hedeflerin anlık olarak gözetlenmesi, takibi, tespiti ve imhasında, insansız hava araçlarının yoğun bir şekilde kullanmasıyla beraber, operasyon alanında farklı özelliklere sahip hava araçlarından hangilerinin seçileceği ve etkin bir şekilde nasıl rotalanacağı, önemli ve zor bir problem olarak ortaya çıkarmıştır. Bu çalışmada filo halinde hareket eden silahlı ve silahsız insansız hava araçlarının kapasite ve zaman penceresi kısıtları dikkate alınarak hareket halindeki hedefleri etkisiz hale getirmesi için sezgisel algoritmaya dayalı çok kriterli bir çözüm yaklaşımı önerilmiştir. Hedef ve vurucuların önceliklendirilmesinde Analitik Hiyerarşik Proses yönteminden yararlanılmış, İHA’ lara ait uçuşların belirli bir maliyete sahip olması, gereksiz kullanılan İHA’ ların bakım-onarım maliyetini ve arıza riskini artırması, operasyon alanında fazla sayıda İHA kullanılmasının düşman unsurlarını uyandırması ve İHA’ lara karşı savunma tedbirleri almaya yönlendirmesi nedenlerinden dolayı kısa bir çözüm süresi içinde tüm hedeflerin minimum sayıda araç ile imha edilmesi amaçlanmıştır. Algoritmanın etkinliği, vurucu sayısının 10 ile 50, hedef sayısının 40 ile 200 arasında değiştiği 25 farklı senaryo üzerinde test edilmiş, sonuç olarak kabul edilebilir çözüm süresi içerisinde tüm hedeflerin belirtilen öncelik sırasına göre minimum sayıda araçla imha edildiği tespit edilmiştir. Önerilen yöntemin filo halinde hareket eden farklı özelliklere sahip (heterojen) insansız hava araçlarının etkin bir şekilde rotalanmasına katkıda bulunduğu görülmüştür.

Anahtar Kelimeler:

Dinamik insansız hava aracı rotalama, analitik hiyerarşik proses, sezgisel algoritma, hareketli hedefli gezgin satıcı problemi, filo rotalama

A New Solution Approach for UAV Routing Problem with Moving Target – Heterogeneous Fleet

The technological developments in the defence industry lead countries to create unmanned armies based on robotic systems. Due to the intense use of unmanned aerial vehicles in the instant surveillance, tracking, detection and disposal of targets, it is an important and difficult problem to determine which of the different types of air vehicles in the field of operations should be selected and how they can be effectively routed. In this study, a multi-criteria solution approach based on heuristic algorithm is proposed for destroying moving targets taking into account of the capacity and time window constraints by armed and unarmed unmanned aerial vehicles moving as a fleet. The Analytical Hierarchical Process method was used to prioritize the targets and pursuers; and it was aimed to destroy all targets with a minimum number of vehicles in a short time due to the cost of flights with UAVs, increase in maintenance-repair costs and the risk of fault due to unnecessary UAV use, the use of large numbers of UAVs in the field of operation evoked enemy elements and directed them to take defensive measures against UAVs. The effectiveness of the algorithm has been tested on 25 different scenarios where the number of pursuers is between 10 and 50 and the target number ranges from 40 to 200. As a result, it has been determined that all targets are destroyed with minimum number of vehicles according to the specified order of priority within the acceptable solution period and the proposed method contributed to the efficient routing of (heterogeneous) unmanned aerial vehicles moving in a fleet.

Keywords:

Dynamic unmanned aerial vehicle routing problem, analytical hierarchical process, heuristic algorithm, moving target traveling salesman problem, fleet routing,

___

[1]. Rana, K., Praharaj, S. & Nanda, T. (2016). Unmanned Aerial Vehicles (UAVs): An Emerging Technology for Logistics. International Journal of Business and Management Invention, 5(5), 86-92. [2]. Aydemir, H. (2014). Harekat Araştırması Ana Bilim Dalı. İnsansız Hava Araçlarının Rotalama Problemi İçin Simülasyon Tabanlı Karar Destek Sistemi. Kara Harp Okulu, Savunma Bilimleri Enstitüsü,[3]. Helvig, C. S., Robins, G., & Zelikovsky, A. (1998, August). Moving-target TSP and related problems. In European Symposium on Algorithms (pp. 453-464). Springer Berlin Heidelberg.[4]. Fügenschuh, A., Knapp, M., & Rothe, H. (2014). The Multiple Traveling Salesmen Problem with Moving Targets. Helmut-Schmidt-Univ., Professur für Angewandte Mathematik.[5]. Stieber, A., Fügenschuh, A., Epp, M., Knapp, M., & Rothe, H. (2015). The multiple traveling salesmen problem with moving targets. Optimization Letters, 9(8), 1569-1583.[6]. Stieber, A., & Fügenschuh, A. (2016). Variants in Modeling Time Aspects for the Multiple Traveling Salesmen Problem with Moving Targets.[7]. Jiang, Q., Sarker, R., & Abbass, H. (2005). Tracking moving targets and the non-stationary traveling salesman problem. Complexity International, 11(2005), 171-179.[8]. Jindal, P., & Kumar, A. (2011). Multiple Target Intercepting Traveling Salesman Problem, International Journal of Computer Science and Technology, 2(2), 327-331.[9]. Englot, B., Sahai, T., & Cohen, I. (2013, December). Efficient tracking and pursuit of moving targets by heuristic solution of the traveling salesman problem. In Decision and Control (CDC), 2013 IEEE 52nd Annual Conference on (pp. 3433-3438). IEEE.[10]. Jindal, P., Kumar, A., & Kumar, S. (2011). Dynamic version of Traveling Salesman Problem. International Journal of Computer Applications (0975–8887), 19(1).[11]. Khosravi, M., & Aghdam, A. G. (2014, December). Cooperative receding horizon control for multi-target interception in uncertain environments. In Decision and Control (CDC), 2014 IEEE 53rd Annual Conference on (pp. 4497-4502). IEEE.[12]. Zhou, A., Kang, L., & Yan, Z. (2003, December). Solving dynamic TSP with evolutionary approach in real time. In Evolutionary Computation, 2003. CEC'03. The 2003 Congress on (Vol. 2, pp. 951-957). IEEE.[13]. Choubey, N. S. (2013). Moving Target Travelling Salesman Problem Using Genetic Algorithm. International Journal of Computer Applications, 70(2).[14]. Lee, Z. J., Lee, C. Y., & Su, S. F. (2002). An immunity-based ant colony optimization algorithm for solving weapon–target assignment problem. Applied Soft Computing, 2(1), 39-47. [15]. Agharkar, P., & Bullo, F. (2014, June). Vehicle routing algorithms to intercept escaping targets. In American Control Conference (ACC), 2014 (pp. 952-957). IEEE.[16]. Knapp, M., & Rothe, H. (2012). Concept for simulating engagement strategies for C-RAM systems using laser weapons. Proceedings of the DMMS.[17]. Bourjolly, J. M., Gurtuna, O., & Lyngvi, A. (2006). On‐orbit servicing: a time‐dependent, moving‐target traveling salesman problem. International Transactions in Operational Research, 13(5), 461-481.[18]. Blough, O. P., Farrington, T. K., & Hudson, J.(2016). Trojan Asteroid Mission Design: Target Selection And Sequencing Optimization.[19]. Mei, G., Ran, X., Fang, D., & Zhang, C. (2015). Improved Satellite Scheduling Algorithm for Moving Target. In Proceedings of The fourth International Conference on Information Science and Cloud Computing (ISCC2015). 18-19 December 2015. Guangzhou, China. Online at http://pos. sissa. it/cgi-bin/reader/conf. cgi? confid= 264, id. 58.[20]. Groba, C., Sartal, A., & Vázquez, X. H. (2015). Solving the dynamic traveling salesman problem using a genetic algorithm with trajectory prediction: An application to fish aggregating devices. Computers & Operations Research, 56, 22-32.[21]. Mercer, G., Barry, S. I., Marlow, D. O., & Kilby, P. (2008). Investigating the effect of detection and classification range and aircraft dynamics on a. ANZIAM Journal, 49, 475-492.[22]. Kilby, P., Tobin, P., Luscombe, R., Barry, S. I., & Hickson, R. (2007). The maritime surveillance problem.[23]. Marlow, D. O., Kilby, P., & Mercer, G. N. (2007, December). The travelling salesman problem in maritime surveillance–techniques, algorithms and analysis. In Proceedings of the International Congress on Modelling and Simulation (pp. 684-690).[24]. Fang, F., Jiang, A. X., & Tambe, M. (2013). Protecting moving targets with multiple mobile resources. Journal of Artificial Intelligence Research, 48, 583-634.[25]. Cross, M., Marlow, D., & Looker, J. (2007). Application of the non-stationary travelling salesman problem to maritime surveillance. Proceedings of MISG, 1-4.[26]. Shuttleworth, R., Golden, B. L., Smith, S., & Wasil, E. (2008). Advances in meter reading: Heuristic solution of the close enough traveling salesman problem over a street network. In The Vehicle Routing Problem: Latest Advances and New Challenges (pp. 487-501). Springer US.[27]. Del Bimbo, A., & Pernici, F. (2005, October). Distant targets identification as an on-line dynamic vehicle routing problem using an active-zooming camera. In Visual Surveillance and Performance Evaluation of Tracking and Surveillance, 2005. 2nd Joint IEEE International Workshop on (pp. 97-104). IEEE.[28]. Bimbo, A. D., & Pernici, F. (2005, June). Saccades planning with kinetic TSP for distant targets identification. In Imaging for Crime Detection and Prevention, 2005. ICDP 2005. The IEE International Symposium on (pp. 145-149). IET.[29]. Ilavarasi, K., & Joseph, K. S. (2014, February). Variants of travelling salesman problem: A survey. In Information Communication and Embedded Systems (ICICES), 2014 International Conference on (pp. 1-7). IEEE.[30]. Asahiro, Y., Horiyama, T., Makino, K., Ono, H., Sakuma, T., & Yamashita, M. (2004). How to collect balls moving in the Euclidean plane. Electronic Notes in Theoretical Computer Science, 91, 229-245.[31]. Asahiro, Y., Miyano, E., & Shimoirisa, S. (2008). Grasp and delivery for moving objects on broken lines. Theory of Computing Systems, 42(3), 289-305.[32]. Chalasani, P., Motwani, R., & Rao, A. N. I. L. (1996, July). Algorithms for robot grasp and delivery. In 2nd International Workshop on Algorithmic Foundations of Robotics.[33]. Papadakos, N., Tzallas-Regas, G., Rustem, B., & Thoms, J. (2011). Risky traveling salesman problem. European Journal of Operational Research, 212(1), 69-73.[34]. Hammar, M., & Nilsson, B. J. (1999, July). Approximation results for kinetic variants of TSP. In International Colloquium on Automata, Languages, and Programming (pp. 392-401). Springer Berlin Heidelberg.[35]. Bengt, J. (2002). Approximation Results for Kinetic Variants of TSP. Discrete & Computational Geometry, 4(27).[36]. Ries, J., & Ishizaka, A. (2012, December). A multi-criteria support system for dynamic aerial vehicle routing problems. In Communications, Computing and Control Applications (CCCA), 2012 2nd International Conference on (pp. 1-4). IEEE.[37].https://webcache.googleusercontent.com/search?q=cache:2kUkSVOagR0J:https://en.wikipedia.org/wiki/Bayraktar_Tactical_UAS+&cd=1&hl=tr&ct=clnk&gl=tr [38].https://webcache.googleusercontent.com/search?q=cache:T9jga0Qp4RMJ:https://en.wikipedia.org/wiki/Alenia_Aermacchi_Sky-Y+&cd=2&hl=tr&ct=clnk&gl=tr [39].http://pages.mscsoftware.com/rs/mscsoftware/images/aleniaaeronautica_october6%5B1%5D.pdf [40].http://pages.mscsoftware.com/rs/mscsoftware/images/aleniaaeronautica_october6%5B1%5D.pdf [41]. https://umsskeldar.aero/wp-content/uploads/UMS_SKELDAR_F-720.pdf [42]. https://www.globalsecurity.org/military/world/russia/dozor.htm [43]. https://www.strategypage.com/htmw/htairfo/articles/20090913.aspx [44].https://www.airforce-technology.com/projects/yabhon-smart-eye-unmanned-aerial-vehicle-uav/ [45].https://webcache.googleusercontent.com/search?q=cache:v3ShtWEoijcJ:https://en.wikipedia.org/wiki/Guizhou_Soar_Dragon+&cd=1&hl=tr&ct=clnk&gl=tr [46].https://webcache.googleusercontent.com/search?q=cache:v3ShtWEoijcJ:https://en.wikipedia.org/wiki/Guizhou_Soar_Dragon+&cd=1&hl=tr&ct=clnk&gl=tr [47]. https://www.defenceaviation.com/2013/01/guizhou-soar-eagle.html [48].https://webcache.googleusercontent.com/search?q=cache:tGUO-Abiw-wJ:https://en.wikipedia.org/wiki/HCUAV+&cd=1&hl=tr&ct=clnk&gl=tr [49].https://webcache.googleusercontent.com/search?q=cache:Bd4xWo3AScQJ:https://en.wikipedia.org/wiki/Ababil+&cd=6&hl=tr&ct=clnk&gl=tr [50].https://indopakdef.wordpress.com/2009/07/28/eads-defence-security-tests-the-largest-unmanned-aerial-system-uav-ever-built-in-europe/ [51].https://en.wikipedia.org/wiki/Medium-altitude_long-endurance_unmanned_aerial_vehicle [52].https://webcache.googleusercontent.com/search?q=cache:7dRcarhnNV8J:https://en.wikipedia.org/wiki/IAI_Heron+&cd=1&hl=tr&ct=clnk&gl=tr [53]. https://www.militaryfactory.com/aircraft/detail.asp?aircraft_id=1673 [54]. https://www.youtube.com/watch?v=Oo_11ZkAVS4 [55]. http://www.airkule.com/yazar/NORTHROP-GRUMMAN-X-47B/1182/ [56].https://webcache.googleusercontent.com/search?q=cache:Q954ddTdA2UJ:https://en.wikipedia.org/wiki/Northrop_Grumman_X-47B+&cd=3&hl=tr&ct=clnk&gl=tr [57]. O’Gorman, Rob, and Chris Abbott. "Remote control war." (2013). [58].http://www.iai.co.il/2013/18900-37204-en/BusinessAreas_UnmannedAirSystems_HeronFamily.aspx [59]. http://www.iai.co.il/Sip_Storage//FILES/8/42458.pdf [60].https://webcache.googleusercontent.com/search?q=cache:1proqLE7jl8J:https://en.wikipedia.org/wiki/IAI_Eitan+&cd=1&hl=tr&ct=clnk&gl=tr [61].https://webcache.googleusercontent.com/search?q=cache:KwaPm4zYuxsJ:https://en.wikipedia.org/wiki/Mikoyan_Skat+&cd=1&hl=tr&ct=clnk&gl=tr [62]. http://foreignpolicy.com/2013/06/03/meet-skat-russias-stealthy-drone/ [63]. https://www.militaryfactory.com/aircraft/detail.asp?aircraft_id=909 [64]. https://ebooks.wtbooks.com/static/wtbooks/ebooks/9781283497367/9781283497367.pdf [65]. https://www.airforce-technology.com/projects/x-45-ucav/ [66]. http://www.aiad.it/aiad_res/cms/documents/FalcoEVO_Selex2013.pdf [67]. http://www.leonardocompany.com/en/-/falco-un-peacekeeping [68].https://webcache.googleusercontent.com/search?q=cache:AvA2gXAhLLcJ:https://en.wikipedia.org/wiki/DRDO_Rustom+&cd=1&hl=tr&ct=clnk&gl=tr [69].https://webcache.googleusercontent.com/search?q=cache:XyoulGy2WY4J:https://en.wikipedia.org/wiki/Medium-altitude_long-endurance_unmanned_aerial_vehicle+&cd=1&hl=tr&ct=clnk&gl=tr [70].https://webcache.googleusercontent.com/search?q=cache:arEWjWn9CnMJ:https://tr.wikipedia.org/wiki/Bayraktar_Taktik_%25C4%25B0nsans%25C4%25B1z_Hava_Arac%25C4%25B1+&cd=8&hl=tr&ct=clnk&gl=tr [71].https://webcache.googleusercontent.com/search?q=cache:2kUkSVOagR0J:https://en.wikipedia.org/wiki/Bayraktar_Tactical_UAS+&cd=7&hl=tr&ct=clnk&gl=tr [72].https://webcache.googleusercontent.com/search?q=cache:ztuJgG4o2RAJ:https://en.wikipedia.org/wiki/TAI_Anka+&cd=3&hl=tr&ct=clnk&gl=tr [73].https://webcache.googleusercontent.com/search?q=cache:ztuJgG4o2RAJ:https://en.wikipedia.org/wiki/TAI_Anka+&cd=1&hl=tr&ct=clnk&gl=tr [74].http://www.bilgiustan.com/yerli-iha-sistemleri-milli-insansiz-hava-araclari/ [75].https://tyrannosurusrex.wordpress.com/2016/06/16/vestel-karayel-hedefleri-basariyla-vurdu/ [76]. https://militaryedge.org/armaments/karayel/ [77]. Akdeniz, H. A., & Turgutlu, T. (2007). Türkiye’de perakende sektöründe analitik hiyerarşik süreç yaklaşımıyla tedarikçi performans değerlendirilmesi. Dokuz Eylül Üniversitesi Sosyal Bilimler Enstitüsü Dergisi, 9(1), 1-17.