UAV routing with genetic algorithm based matheuristic for border security missions
Keywords:UAV routing, Genetic algorithm, Matheuristic, Border security, Homeland security
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).
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].
How to Cite
Copyright (c) 2021 Omer Ozkan, Muhammed Kaya
This work is licensed under a Creative Commons Attribution 4.0 International License.
Articles published in IJOCTA are made freely available online immediately upon publication, without subscription barriers to access. All articles published in this journal are licensed under the Creative Commons Attribution 4.0 International License (click here to read the full-text legal code). This broad license was developed to facilitate open access to, and free use of, original works of all types. Applying this standard license to your work will ensure your right to make your work freely and openly available.
Under the Creative Commons Attribution 4.0 International License, authors retain ownership of the copyright for their article, but authors allow anyone to download, reuse, reprint, modify, distribute, and/or copy articles in IJOCTA, so long as the original authors and source are credited.
The readers are free to:
- Share — copy and redistribute the material in any medium or format
- Adapt — remix, transform, and build upon the material
- for any purpose, even commercially.
- The licensor cannot revoke these freedoms as long as you follow the license terms.
under the following terms:
- Attribution — You must give appropriate credit, provide a link to the license, and indicate if changes were made. You may do so in any reasonable manner, but not in any way that suggests the licensor endorses you or your use.
- No additional restrictions — You may not apply legal terms or technological measures that legally restrict others from doing anything the license permits.
This work is licensed under a Creative Commons Attribution 4.0 International License.