Optimal Coverage of Borders Using Unmanned Aerial Vehicles

Document Type : Original paper

Authors

1 Mohammad Etezadi Faculty of Sciences, Emam Ali University, Tehran, Iran

2 Department of Mathematics, Maragheh Branch, Islamic Azad University Of Maragheh, Iran

3 Department faculty of mathematics, university of maragheh, maragheh, Iran

Abstract

Unmanned Aerial Vehicles (UAVs) play a very important role in military and civilian activities. In this paper, the aim is to cover the borders of Iran using UAVs. For this purpose, two zero-one programming  models are presented. In the first model, our goal is to cover the borders of Iran at the minimum total time (the required time to prepare UAVs to start flying and the flight time of the UAVs). In this model, by minimizing the total time of UAVs for covering the borders, the costs appropriate to the flight of UAVs (such as the fuel costs of UAVs) are also reduced. In the second model, which is mostly used in emergencies and when a military attack occurs on the country's borders, the aim is to minimize the maximum required time to counter attacks and cover the entire country's borders. The efficiency of both models is shown by numerical examples.

Keywords

Main Subjects

References

[1] G.S.C. Avellar, G.A.S. Pereira, L.C.A. Pimenta, and P. Iscold, Multi-UAV routing for area coverage and remote sensing with minimum time, Sensors 15 (2015), no. 11, 27783–27803.
https://doi.org/10.3390/s151127783
[2] B.N. Coelho, V.N. Coelho, I.M. Coelho, L.S. Ochi, R. Haghnazar, D. Zuidema, M.S.F. Lima, and A.R. da Costa, A multi-objective green UAV routing problem, Compute. Oper. Res. 88 (2017), 306–315.
https://doi.org/10.1016/j.cor.2017.04.011
[3] L. Cooper, The transportation-location problem, Oper. Res. 20 (1972), no. 1, 94–108.
https://doi.org/10.1287/opre.20.1.94
[4] S.K. Jacobsen and O.B.G. Madsen, A comparative study of heuristics for a two-level routing-location problem, Eur. J. Oper. Res. 5 (1980), no. 6, 378–3387.
https://doi.org/10.1016/0377-2217(80)90124-1
[5] M. Karakaya and E. Sevinç, An efficient genetic algorithm for routing multiple UAVs under flight range and service time window constraints, Int. J. Info.Technolog. 10 (2017), no. 1, Article ID 113.
[6] M. Kress and J.O. Royset, Aerial search optimization model (ASOM) for UAVs in special operations, Military Oper. Res. (2008), 23–33.
[7] X.F. Liu, L.M. Gao, Z.W. Guang, and Y.Q. Song, A UAV allocation method for traffic surveillance in sparse road network, Journal of Highway and Transportation Research and Development (English Edition) 7 (2013), no. 2, 81–87.
[8] X.F. Liu, Z.W. Guan, Y.Q. Song, and D.S. Chen, An optimization model of UAV route planning for road segment surveillance, Journal of Central South University 21 (2014), no. 6, 2501–2510.
https://doi.org/10.1007/s11771-014-2205-z
[9] X.F. Liu, Z.R. Peng, Y.T Chang, and L.Y. Zhang, Multi-objective evolutionary approach for UAV cruise route planning to collect traffic information, Journal of central south university 19 (2012), no. 12, 3614–3621.
https://doi.org/10.1007/s11771-012-1449-8
[10] Y. Liu, Z. Liu, J. Shi, G. Wu, and C. Chen, Optimization of base location and patrol routes for unmanned aerial vehicles in border intelligence, surveillance, and reconnaissance, J. Adv. Transport. 2019 (2019), Article ID 9063232.
https://doi.org/10.1155/2019/9063232
[11] H. Min, V. Jayaraman, and R. Srivastava, Combined location-routing problems: A synthesis and future research directions, Eur. J. Ope. Res. 108 (1998), no. 1, 1–15.
https://doi.org/10.1016/S0377-2217(97)00172-0
[12] J.M. Nambiar, L.F. Gelders, and L.N. Van Wassenhove, A large scale location-allocation problem in the natural rubber industry, Eur. J. Oper. Res. 6 (1981), no. 2, 183–189.
https://doi.org/10.1016/0377-2217(81)90205-8
[13] I. Or and W.P. Pierskalla, A transportation location-allocation model for regional blood banking, AIIE Trans. 11 (1979), no. 2, 86–95.
https://doi.org/10.1080/05695557908974447
[14] ˙I. Sarıçiçek and Y. Akkuş, Unmanned aerial vehicle hub-location and routing for monitoring geographic borders, Appl. Math. Model. 39 (2015), no. 14, 3939–3953.
https://doi.org/10.1016/j.apm.2014.12.010
[15] K. Sundar and S. Rathinam, Algorithms for routing an unmanned aerial vehicle in the presence of refueling depots, IEEE Transactions on Automation Science and Engineering 11 (2013), no. 1, 287–294.
https://doi.org/10.1109/TASE.2013.2279544
[16] J. Tian, L. Shen, and Y. Zheng, Genetic algorithm based approach for multi-UAV cooperative reconnaissance mission planning problem, Foundations of Intelligent Systems: 16th International Symposium, ISMIS 2006, Bari, Italy, September
27-29, 2006. Proceedings 16, Springer, 2006, pp. 101–110.
[17] D. Tuzun and L.I. Burke, A two-phase tabu search approach to the location routing problem, Eur. J. Oper. Res. 116 (1999), no. 1, 87–99.
https://doi.org/10.1016/S0377-2217(98)00107-6
[18] J. Zhang, L. Jia, S. Niu, F. Zhang, L. Tong, and X. Zhou, A space-time network-based modeling framework for dynamic unmanned aerial vehicle routing in traffic incident monitoring applications, Sensors 15 (2015), no. 6, 13874–13898.
https://doi.org/10.3390/s150613874
[19] T. Zhao, H. Wang, and Q. Ma, The coverage method of unmanned aerial vehicle mounted base station sensor network based on relative distance, International Journal of Distributed Sensor Networks 16 (2020), no. 5, 1–12.
https://doi.org/10.1177/1550147720920220
 
Communications in Combinatorics and Optimization

Articles in Press, Accepted Manuscript
Available Online from 22 April 2023

Files

Share

How to cite

Statistics