UAV routing with genetic algorithm based matheuristic for border security missions

Omer Ozkan; Muhammed Kaya

doi:10.11121/ijocta.01.2021.001023

Authors

Omer Ozkan National Defense University, Turkish Air Force Academy, 34149, Yeşilyurt , Istanbul, Turkey http://orcid.org/0000-0002-3839-2754
Muhammed Kaya Turkish Air Force, Turkey http://orcid.org/0000-0001-9410-7367

DOI:

https://doi.org/10.11121/ijocta.01.2021.001023

Keywords:

UAV routing, Genetic algorithm, Matheuristic, Border security, Homeland security

Abstract

In recent years, Unmanned Aerial Vehicles (UAVs) are a good alternative for the problem of ensuring the security of the borders of the countries. UAVs are preferred because of their speed, ease of use, being able to observe many points at the same time, and being more cost-effective in total compared to other security tools. This study is dealt with the problem of the use of UAVs for the security of the Turkey-Syria borderline which becomes sensitive in recent years and the problem is modeled as a UAV routing problem. To solve the problem, a Genetic Algorithm Based Matheuristic (GABM) approach has been developed and 12 scenarios have been created covering the departure bases, daily patrol numbers, and ranges of UAVs. GABM finds the minimum number of UAVs to use in scenarios with the help of a GA run first and tries to find the optimal routes for these UAVs. If GABM can find an optimal route for the determined UAV number, it decreases the UAV number and tries to solve the problem again. GABM proposes a hybrid approach in which a metaheuristic with a mathematical model works together and the metaheuristic sets an upper limit for the number of UAVs in the model. In computational studies, when compared GA with GABM it is seen that GABM has obtained good results and decreased the utilized number of UAVs (up to 400%) and their flight distances (up to 85.99%) for the problem in very short CPU times (max. 122.17 s. for GA and max. 46.39 s. for GABM in addition to GA).

Downloads

Download data is not yet available.

Author Biographies

Omer Ozkan, National Defense University, Turkish Air Force Academy, 34149, Yeşilyurt , Istanbul, Turkey

Omer Ozkan received his B.Sc. degree in Industrial Engineering from Turkish Air Force Academy, Istanbul, in 2002. He received his M.Sc. degree in Industrial Engineering from Dokuz Eylul University, Izmir, in 2010 and the Ph.D. degree in Industrial Engineering from National Defence University, Istanbul, in 2016. He is currently an Assistant Professor of Operations Research in Industrial Engineering Department, Turkish Air Force Academy, National Defence University. His research interests include metaheuristics, optimization, and network analysis.

Muhammed Kaya, Turkish Air Force, Turkey

Muhammed Kaya received his B.Sc. degree in Industrial Engineering from Turkish Air Force Academy, National Defence University, Istanbul, in 2018. He is a First Lieutenant in Turkish Air Force.

References

Kaza, S., Wang, Y., & Chen, H. (2007). Enhancing border security: Mutual information analysis to identify suspect vehicles, Decision Support Systems, 43, 199-210.

Sun, Z., Wang, P., Vuran, M.C., Al-Rodhaan, M. A., Al-Dhelaan, A.M., & Akyildiz, I.F. (2011). BorderSense: Border patrol through advanced wireless sensor networks, Ad Hoc Networks, 9, 468-477.

Owen, A., Duckworth, G., & Worsley, J. (2012). OptaSense: Fibre optic distributed acoustic sensing for border monitoring, in Proc. of the 2012 European Intelligence and Security Informatics Conference, 22-24 Aug., Odense, Denmark [Online]. Available: IEEE Xplore, http://www.ieee.org. [Accessed: 16 September 2020].

Hare, J., Gupta, S., & Wilson, J. (2015). Decentralized smart sensor scheduling for multiple target tracking for border surveillance, in Proc. of the 2015 IEEE Int. Conf. on Robotics and Automation, ICRA 2015, 26-30 May, Seattle, Washington, [Online]. Available: IEEE Xplore, http://www.ieee.org. [Accessed: 16 September 2020].

Karabulut, E., Aras, N., & Alt?nel, ?.K. (2017). Optimal sensor deployment to increase the security of the maximal breach path in border surveillance, European Journal of Operational Research, 259, 19-36.

Alkhathami, M., Alazzawi, L., & Elkateeb, A. (2017). Large scale border security systems modeling and simulation with OPNET, in Proc. of the 2017 IEEE 7th Annual Computing and Communication Workshop and Conference, CCWC 2017, 09-11 Jan., Las Vegas, USA.

Arjun, D., Indukala, P.K., & Unnikrishna Menon, K.A. (2017). Border surveillance and intruder detection using wireless sensor networks: A brief survey, in Proc. of the 2017 Int. Conf. on Communication and Signal Processing, ICCSP 2017, 06-08 April, Chennai, India.

Lessin, A.M., Lunday, B.J., & Hill, R.R. (2018). A bilevel exposure-oriented sensor location problem for border security, Computers and Operations Research, 98, 56-68.

Matveev, A.S., Teimoori, H., & Savkin, A.V. (2011). A method for guidance and control of an autonomous vehicle in problems of border patrolling and obstacle avoidance, Automatica, 47, 515-524.

Tanas, M., Holubowicz, W., Adamczyk, A., & Taberski, G. (2011). The TALOS Project. EU wide robotic border guard system, in Proc. of the 2011 16th Int. Conf. on Methods & Models in Automation & Robotics, 22-25 Aug., Miedzyzdroje, Poland.

Tanas, M., Taberski, G., Ho?ubowicz, W., Samp, K., Spro?ska, A., G?ówka, J., & Macia?, M. (2012). The TALOS project – autonomous robotic patrol vehicles, in Proc. of the 2012 European Intelligence and Security Informatics Conference, 22-24 Aug., Odense, Denmark.

Girard, A.R., Howell, A.S., & Hedrick, J.K. (2004). Border patrol and surveillance missions using multiple unmanned air vehicles, in Proc. of the 43rd IEEE Conference on Decision and Control, 2004, 14-17 Dec., Atlantis, Bahamas.

Blazakis, J. (2006). Border security and unmanned aerial vehicles, Connections, 5(2), 154-159.

Matveev, A.S. Teimoori, H., & Savkin, A.V. (2010). A method for navigation of an autonomous vehicle for border patrol, in Proc. of the 2010 American Control Conference, 30 June-02 July, Marriott Waterfront, Baltimore, USA.

Haddal, C.C., & Gertler, J. (2010). Homeland security: Unmanned aerial vehicles and border surveillance, Congressional Research Service Report for Congress, RS21698, USA, [Online]. Available: https://nsarchive2.gwu.edu/NSAEBB/NSAEBB527-Using-overhead-imagery-to-track-domestic-US-targets/documents/EBB-Doc24.pdf, [Accessed: 16 September 2020].

Ortiz-Rivera, E.I., Estela, A., Romero, C., & Valentin, J.A. (2012). The use of UAVS in USA’s security by an engineering education approach, in Proc. of the 2012 IEEE Conference on Technologies for Homeland Security (HST), 13-15 Nov., Waltham, USA.

Moss, V., Jones, D., & Nwaneri, S. (2012). Analysis of homeland security and economic survey using special missions unmanned aerial vehicle utilities, in Proc. of the 2012 IEEE International Geoscience and Remote Sensing Symposium, 22-27 July, Munich, Germany.

Office of Inspector General (2014). U.S. customs and border protection’s unmanned aircraft system program does not achieve intended results or recognize all costs of operations”, Department of Homeland Security Report, OIG-15-17, USA, [Online]. Available: https://www.oig.dhs.gov/assets/Mgmt/2015/OIG_15-17_Dec14.pdf, [Accessed: 16 September 2020].

Bein, D., Bein, W., Karki, A., & Madan, B.B. (2015). Optimizing border patrol operations using unmanned aerial vehicles, in Proc. of the 2015 12th International Conference on Information Technology - New Generations, 13-15 April, Las Vegas, USA.

Pó?ka, M., Ptak, S., & Kuziora, L. (2017). The use of UAV's for search and rescue operations, Procedia Engineering, 192, 748-752.

Cic?, C., & Filipoaia, L. (2016). Border surveillance optimization using a multi-objective mathematical model, in Proc. of the 2016 IEEE Int. Conf. on Electronics, Computers and Artificial Intelligence, ECAI 2016, 30 June-02 July, Ploiesti, Romania.

Çelik, G., & Sabuncuo?lu, ?. (2007). Simulation modelling and analysis of a border security system, European Journal of Operational Research, 180, 1394-1410.

Jenkins, J.L., Marquardson, J., Proudfoot, J.G., Valacich, J.S., Golob, E., & Nunamaker, Jr., J.F. (2013). The Checkpoint Simulation: A tool for informing border patrol checkpoint design and resource allocation, in Proc. of the 2013 European Intelligence and Security Informatics Conference, 12-14 Aug., Uppsala, Sweden.

Muaafa, M., & Ramirez-Marquez, J.E. (2017). Bi-objective evolutionary approach to the design of patrolling schemes for improved border security”, Computers & Industrial Engineering, 107, 74-84.

Ackleson, J. (2003). Directions in border security research, The Social Science Journal, 40, 573-581.

Gravelle, T.B. (2018). Politics, time, space, and attitudes toward US–Mexico border security, Political Geography, 65, 107-116.

Fisher, D.X.O. (2018). Situating border control: Unpacking Spain's SIVE border surveillance assemblage, Political Geography, 65, 67-76.

Dalamagkidis, K. Valavanis, K.P., & Piegl, L.A. (2008). On unmanned aircraft systems issues, challenges and operational restrictions preventing integration into the National Airspace System, Progress in Aerospace Sciences, 44, 503-519.

Gupte, S., Mohandas, P.I.T., & Conrad, J.M. (2012). A survey of quadrotor unmanned aerial vehicles, in Proc. of the 2012 IEEE Southeastcon, 15-18 March, Orlando, USA.

Yu, X., & Zhang, Y. (2015). Sense and avoid technologies with applications to unmanned aircraft systems: Review and prospects, Progress in Aerospace Sciences, 74, 152-166.

Mcfadyen, A., & Mejias, L. (2016). A survey of autonomous vision-based see and avoid for unmanned aircraft systems, Progress in Aerospace Sciences, 80, 01-17.

Eksioglu, B., Vural, A.V., & Reisman, A. (2009). The vehicle routing problem: A taxonomic review, Computers & Industrial Engineering, 57, 1472-1483.

Braekers, K., Ramaekers, K., & Nieuwenhuyse, I.V. (2016). The vehicle routing problem: State of the art classification and review, Computers & Industrial Engineering, 99, 300-313.

Gansterer, M., & Hartl, R.F. (2018). Collaborative vehicle routing: A survey, European Journal of Operational Research, 268, 1-12.

Tlili, T., Faiz, S., & Krichen, S. (2014). A hybrid metaheuristic for the distance-constrained capacitated vehicle routing problem, Procedia - Social and Behavioral Sciences, 109, 779-783.

Letchford, A.N., & Salazar-González, J.-J. (2019). The capacitated vehicle routing problem: Stronger bounds in pseudo-polynomial time, European Journal of Operational Research, 272, 24-31.

Montoya-Torres, J.R., Franco, J.L., Isaza, S.N., Jiménez, H.F., & Herazo-Padilla, N. (2015). A literature review on the vehicle routing problem with multiple depots, Computers & Industrial Engineering, 79, 115-129.

Bektas, T. (2006). The multiple traveling salesman problem: an overview of formulations and solution procedures”, Omega, 34, 209-219.

Kaempfer, Y., & Wolf, L. (2018). Learning the multiple traveling salesmen problem with permutation invariant pooling networks, CORR, abs/1803.09621, 1-17.

Coutinho, W.P., Battarra, M., & Fliege, J. (2018). The unmanned aerial vehicle routing and trajectory optimisation problem, a taxonomic review, Computers & Industrial Engineering, 120, 116-128.

Pandey, P., Shukla, A., & Tiwari, R. (2017). Aerial path planning using meta-heuristics: A survey, in Proc. of the 2017 Second International Conference on Electrical, Computer and Communication Technologies (ICECCT), 22-24 Feb., Coimbatore, India.

Zhao, Y., Zheng, Z., & Liu, Y. (2018). Survey on computational-intelligence-based UAV path planning, Knowledge-Based Systems, 158, 54-64.

Seyis, A., Karacin, Y., & Ozkan, O. (2016). Optimal path planning with minimum number of UAVs by using genetic algorithm”, in Proc. of the 28th European Conference on Operational Research (EURO 2016), 03-06 July, Poznan, Poland.

Kaya, M., & Ozkan, O. (2018). S?n?r koruma görevi için insans?z hava araçlar?n?n rotalanmas? probleminin genetik algoritma ile eniyilenmesi, in Proc. of the 38. Ulusal Yöneylem Ara?t?rmas? ve Endüstri Mühendisli?i Kongresi (YAEM 2018), 26-29 June, Eski?ehir, Turkey.

Ozkan, O. (2018). ?nsans?z hava araçlar? ile Türkiye’deki orman yang?nlar?n?n tespiti probleminin tavlama benzetimi ile eniyilenmesi, in Proc. of the 38. Ulusal Yöneylem Ara?t?rmas? ve Endüstri Mühendisli?i Kongresi (YAEM 2018), 26-29 June, Eski?ehir, Turkey.

Yang, L., Qi, J., Xiao, J., & Yong, X. (2014). A literature review of UAV 3D path planning, in Proc. of the 2014 11th World Congress on Intelligent Control and Automation, 29 June-04 July, Shenyang, China.

Khan, M.A., Safi, A., Qureshi, I.M., & Khan, I.U. (2017). Flying Ad-Hoc Networks (FANETs): A review of communication architectures, and routing protocols, in Proc. of the 2017 First International Conference on Latest trends in Electrical Engineering and Computing Technologies (INTELLECT), 15-16 Nov., Karachi, Pakistan.

T.C. Cumhurba?kanl???, Türk Savunma Sanayii Ba?kanl??? (2021). SSB – Türk Savunma Sanayii Ürün Katalo?u [online]. Available from: SSB - TÜRK SAVUNMA SANAY?? ÜRÜN KATALO?U, [Accessed: 16 September 2020].

Baykar Savunma (2021). Bayraktar TB-2 [online]. Available from: BAYKAR ?nsans?z Hava Arac? Sistemleri (baykarsavunma.com), [Accessed: 16 September 2020].