Research Article
BibTex RIS Cite

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

Year 2023, Volume: 38 Issue: 4, 2167 - 2178, 12.04.2023
https://doi.org/10.17341/gazimmfd.990791

Abstract

İ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.

References

  • 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.
  • 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.
  • 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.
  • 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.
  • 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.
  • Tezcaner Öztürk, D., Köksalan, M., Biobjective UAV route planning in Continuous Terrain, Technical Report, Department of Industrial Engineering, METU, 2018.
  • 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.
  • 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.
  • 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.
  • 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.
  • Levy, D., Sundar, K., Rathinam, S., Heuristics for Routing Heterogeneous Unmanned Vehicles with Fuel Constraints, Math. Probl. Eng, 2014.
  • 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.
  • 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.
  • 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.
  • Karakaya, M., UAV Route Planning for Maximum Target Coverage, Comput. Sci. Eng. An Int. J., 4 27–34, 2014.
  • 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.
  • Yakıcı, E., Solving location and routing problem for UAVs, Comput. Ind. Eng., 102, 294–301, 2016.
  • Chankong, V., Haimes, Y.Y., Multiobjective Decision Making: Theory and Methodology, North-Holland, New York, 1983.
  • 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.
  • Deb, K., Multi-Objective Optimization Using Evolutionary Algorithms, Wiley, 235, 2001.
  • Bento, M. D. F., Unmanned aerial vehicles: an overview, Inside GNSS, 3 (1), 54-61, 2008.
  • 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.

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

Year 2023, Volume: 38 Issue: 4, 2167 - 2178, 12.04.2023
https://doi.org/10.17341/gazimmfd.990791

Abstract

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.

References

  • 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.
  • 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.
  • 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.
  • 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.
  • 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.
  • Tezcaner Öztürk, D., Köksalan, M., Biobjective UAV route planning in Continuous Terrain, Technical Report, Department of Industrial Engineering, METU, 2018.
  • 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.
  • 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.
  • 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.
  • 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.
  • Levy, D., Sundar, K., Rathinam, S., Heuristics for Routing Heterogeneous Unmanned Vehicles with Fuel Constraints, Math. Probl. Eng, 2014.
  • 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.
  • 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.
  • 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.
  • Karakaya, M., UAV Route Planning for Maximum Target Coverage, Comput. Sci. Eng. An Int. J., 4 27–34, 2014.
  • 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.
  • Yakıcı, E., Solving location and routing problem for UAVs, Comput. Ind. Eng., 102, 294–301, 2016.
  • Chankong, V., Haimes, Y.Y., Multiobjective Decision Making: Theory and Methodology, North-Holland, New York, 1983.
  • 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.
  • Deb, K., Multi-Objective Optimization Using Evolutionary Algorithms, Wiley, 235, 2001.
  • Bento, M. D. F., Unmanned aerial vehicles: an overview, Inside GNSS, 3 (1), 54-61, 2008.
  • 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.
There are 22 citations in total.

Details

Primary Language Turkish
Subjects Engineering
Journal Section Makaleler
Authors

Büşra Bişkin This is me 0000-0001-7826-4717

Diclehan Tezcaner Öztürk 0000-0002-8628-0984

Ceren Tuncer Şakar 0000-0002-6269-4234

Publication Date April 12, 2023
Submission Date September 3, 2021
Acceptance Date October 13, 2022
Published in Issue Year 2023 Volume: 38 Issue: 4

Cite

APA Bişkin, B., Tezcaner Öztürk, D., & Tuncer Şakar, C. (2023). İki amaçlı İHA filosu rota planlaması: Kesin ve sezgisel yöntemler. Gazi Üniversitesi Mühendislik Mimarlık Fakültesi Dergisi, 38(4), 2167-2178. https://doi.org/10.17341/gazimmfd.990791
AMA Bişkin B, Tezcaner Öztürk D, Tuncer Şakar C. İki amaçlı İHA filosu rota planlaması: Kesin ve sezgisel yöntemler. GUMMFD. April 2023;38(4):2167-2178. doi:10.17341/gazimmfd.990791
Chicago Bişkin, Büşra, Diclehan Tezcaner Öztürk, and Ceren Tuncer Şakar. “İki amaçlı İHA Filosu Rota planlaması: Kesin Ve Sezgisel yöntemler”. Gazi Üniversitesi Mühendislik Mimarlık Fakültesi Dergisi 38, no. 4 (April 2023): 2167-78. https://doi.org/10.17341/gazimmfd.990791.
EndNote Bişkin B, Tezcaner Öztürk D, Tuncer Şakar C (April 1, 2023) İki amaçlı İHA filosu rota planlaması: Kesin ve sezgisel yöntemler. Gazi Üniversitesi Mühendislik Mimarlık Fakültesi Dergisi 38 4 2167–2178.
IEEE B. Bişkin, D. Tezcaner Öztürk, and C. Tuncer Şakar, “İki amaçlı İHA filosu rota planlaması: Kesin ve sezgisel yöntemler”, GUMMFD, vol. 38, no. 4, pp. 2167–2178, 2023, doi: 10.17341/gazimmfd.990791.
ISNAD Bişkin, Büşra et al. “İki amaçlı İHA Filosu Rota planlaması: Kesin Ve Sezgisel yöntemler”. Gazi Üniversitesi Mühendislik Mimarlık Fakültesi Dergisi 38/4 (April 2023), 2167-2178. https://doi.org/10.17341/gazimmfd.990791.
JAMA Bişkin B, Tezcaner Öztürk D, Tuncer Şakar C. İki amaçlı İHA filosu rota planlaması: Kesin ve sezgisel yöntemler. GUMMFD. 2023;38:2167–2178.
MLA Bişkin, Büşra et al. “İki amaçlı İHA Filosu Rota planlaması: Kesin Ve Sezgisel yöntemler”. Gazi Üniversitesi Mühendislik Mimarlık Fakültesi Dergisi, vol. 38, no. 4, 2023, pp. 2167-78, doi:10.17341/gazimmfd.990791.
Vancouver Bişkin B, Tezcaner Öztürk D, Tuncer Şakar C. İki amaçlı İHA filosu rota planlaması: Kesin ve sezgisel yöntemler. GUMMFD. 2023;38(4):2167-78.