İki amaçlı İHA filosu rota planlaması: Kesin ve sezgisel yöntemler

Öz

İnsansız hava araçlarının (İHA’ların) askeri ve sivil amaçlarla artan kullanımı ile birlikte İHA rotalama problemi önem kazanmaktadır. İHA’ların sayısı ve özellikleri, rotalama yapılan alanın özellikleri ve kullanılan amaç fonksiyonları gibi faktörlerle değişkenlik gösteren bu problem için literatürde farklı yaklaşımlar geliştirilmiştir. Bu çalışmada, bir üsten ayrıldıktan sonra farklı önem derecelerine sahip olan hedef noktalarına uğrayarak geri dönmesi gereken özdeş bir İHA filosunun rota planlama problemi ele alınmıştır. Toplam mesafenin minimize edilmesi ve ziyaret edilen hedeflerin toplam önemlerinin maksimize edilmesi şeklinde iki amaç fonksiyonu kullanılmış, tek bir çözüm yerine alternatif etkin çözümler üretilmiştir. Problem matematiksel model ve genetik algoritma yaklaşımları ile çözülmüş, farklı sayıda İHA ve hedef noktaları ile sayısal testler yapılmıştır. İki yöntemle de karar vericilere sunmak üzere amaç uzayının farklı bölgelerinden çözümler elde edilebilmiştir. Ayrıca, genetik algoritma ile çok daha kısa sürelerde kesin çözümlere yakın çözümler bulunabildiği görülmüştür.

Anahtar Kelimeler

• İnsansız hava aracı
• rota planlama
• çok amaçlı optimizasyon
• genetik algoritma

Biobjective route planning for a fleet of UAVs: Exact and heuristic approaches

Öz

As the use of unmanned aerial vehicles (UAVs) for military and civilian purposes increases, UAV route planning problem has gained importance. The problem varies according to factors like the number and properties of UAVs, the characteristics of the terrain and the objective functions used; and different approaches have been developed for it in the literature. This study considers route planning for a fleet of homogeneous UAVs that need to collect information from target points with different levels of importance before returning to the base. The two objectives used are minimizing the total distance traveled and maximizing the total importance level of the targets visited, and alternative efficient solutions are generated rather than a single solution. The problem is solved with mathematical modelling and genetic algorithm approaches, and computational tests are made with different number of UAVs and target points. Solutions from different regions of the objective space could be obtained to be presented to the decision makers by both methods. Also, with the genetic algorithm, solutions close to the exact solutions could be obtained in considerably shorter computation times.

Anahtar Kelimeler

• Unmanned aerial vehicles
• route planning
• multiobjective optimization
• genetic algorithm

Kaynakça

1. Coutinho, W.P., Battarra, M., Fliege, J., The unmanned aerial vehicle routing and trajectory optimisation problem, a taxonomic review, Computers & Industrial Engineering, Comput. Ind. Eng., 120, 16–128, 2018.
2. Sundar, K., Rathinam, S., Algorithms for Routing an Unmanned Aerial Vehicle in the Presence of Refueling Depots, IEEE Trans. Autom. Sci. Eng., 11, 287–294, 2014.
3. Ousingsawat, J., UAV Path Planning for Maximum Coverage Surveillance of Area with Different Priorities, The 20th Conference of Mechanical Engineering Network of Thailand, Thailand, 2006.
4. Hernández-Hernández, L., Tsourdos, A., Shin, H.-S., Waldock, A., Multi-objective UAV routing, International Conference on Unmanned Aircraft Systems (ICUAS), 534–542, 2014.
5. Tezcaner Öztürk, D., Köksalan, M., An interactive approach for biobjective integer programs under quasiconvex preference functions, Ann. Oper. Res., 244, 677–696, 2016.
6. Tezcaner Öztürk, D., Köksalan, M., Biobjective UAV route planning in Continuous Terrain, Technical Report, Department of Industrial Engineering, METU, 2018.
7. Türeci, H., Interactive Approaches for Bi-Objective UAV Route Planning in Continuous Space, M.S. Thesis, The Graduate School of Natural and Applied Sciences of Middle East Technical University, Ankara, 2017.
8. Korkmaz, Y., İyibilgin, O., Fındık, F., Geçmişten günümüze insansız hava araçlarının gelişimi, SAÜ Fen Bilim. Enstitüsü Derg., 20, 103, 2015.

9. Lamont, G.B., Slear, J.N., Melendez, K., UAV Swarm Mission Planning and Routing using Multi-Objective Evolutionary Algorithms, IEEE Sympoisum on Computational Intelligence in Multicriteria Decision Making, 10–20, 2007.
10. Peng, X., Gao, X., A Multi-objective Optimal Approach for UAV Routing in Reconnaissance Mission with Stochastic Observation Time, Foundations of Intelligent Systems, ISMIS, 246–255, 2008.
11. Levy, D., Sundar, K., Rathinam, S., Heuristics for Routing Heterogeneous Unmanned Vehicles with Fuel Constraints, Math. Probl. Eng, 2014.
12. Wu, W., Wang, X., Cui, N., Fast and coupled solution for cooperative mission planning of multiple heterogeneous unmanned aerial vehicles, Aerosp. Sci. Technol., 79, 131–144, 2018.
13. Uçar,U. Ü., İşleyen, S. K., Hareketli hedefli – heterojen filolu İHA rotalama problemi için yeni bir çözüm yaklaşımı, Politeknik Dergisi, 22(4), 999-1016, 2019.
14. Yılmaz, N., Gencer, C. T., Integration of sensor vision capabilities on UAV flight route optimization: A linear model and a heuristic algorithm proposal, Journal of the Faculty of Engineering and Architecture of Gazi University, 34 (4), 1917-1928, 2019.
15. Karakaya, M., UAV Route Planning for Maximum Target Coverage, Comput. Sci. Eng. An Int. J., 4 27–34, 2014.
16. Alotaibi, K.A., Rosenberger, J.M., Mattingly, S.P., Punugu, R.K., Visoldilokpun, S., Unmanned aerial vehicle routing in the presence of threats, Comput. Ind. Eng., 115, 190–205, 2018.
17. Yakıcı, E., Solving location and routing problem for UAVs, Comput. Ind. Eng., 102, 294–301, 2016.
18. Chankong, V., Haimes, Y.Y., Multiobjective Decision Making: Theory and Methodology, North-Holland, New York, 1983.
19. Deb, K., A., Pratap, A., Agarwal, S., Meyarivan, T., A Fast and Elitist Multiobjective Genetic Algorithm, NSGA-II, IEEE Trans. Evol. Comput., 6, 182–197, 2002.
20. Deb, K., Multi-Objective Optimization Using Evolutionary Algorithms, Wiley, 235, 2001.
21. Bento, M. D. F., Unmanned aerial vehicles: an overview, Inside GNSS, 3 (1), 54-61, 2008.
22. Shang, K., Ishibuchi, H., He, L., Pang, L.M., A Survey on the Hypervolume Indicator in Evolutionary Multiobjective Optimization, IEEE Trans. Evol. Comput., 25(1), 2021.