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

Year 2019, Volume: 22 Issue: 4, 999 - 1016, 01.12.2019

Ukbe Üsame Uçar , Selçuk Kürşat İşleyen

https://doi.org/10.2339/politeknik.466393

Cited By: 10

Abstract

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.  

Keywords

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

Abstract

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

References

• [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.