2021, issue 4, p. 12-26
Received 11.12.2021; Revised 19.12.2021; Accepted 21.12.2021
Published 30.12.2021; First Online 27.01.2022
https://doi.org/10.34229/2707-451X.21.4.2
Previous | FULL TEXT (in Ukrainian) | Next
Formalization of the Problem of Optimization of Base Places and Routes of the UAV Group
Leonid Hulianytskyi * 
, Oleg Rybalchenko
V.M. Glushkov Institute of Cybernetics of the NAS of Ukraine, Kyiv
* Correspondence: This email address is being protected from spambots. You need JavaScript enabled to view it.
Introduction. The problem of planning the mission of a set of heterogeneous unmanned aerial vehicles (UAVs)is considered, which is to survey and/or service a given set of targets in the field. A mathematical model of the problem and algorithms for its solving that is based on deterministic local search, as well as optimization by ant colonies are proposed. The efficiency of algorithms is investigated based on the results of solving problems with real objects in the field. The relative error of the results of each algorithm was obtained, which allowed to compare their efficiency.
The purpose of the paper is to solve a routing problem in different ways to reduce overall mission cost and compare the efficiency. The problem statement considers multiple starting points and destinations (depots) for UAVs with determined capacity, so algorithms proposed in the paper are designed to optimize the initial placement. Each UAV has a maximum flight distance because of an energy limit, though vehicles can be recharged by visiting one of previously placed depots. The mission goal is to visit all the given targets while minimizing the overall cost, so fuel consumption over distance, depot placement, and resources needed to survey and/or service of the target by each UAV are considered as components of the final cost metric to be minimized considering a set of specific constraints.
Results. To solve the given UAV routing problem, a max-min algorithm of ant systems was developed, which features step-by-step interaction of ants to form solutions, a hybrid taboo search algorithm and a deterministic local search algorithm - the decay vector method. The developed algorithms were tested both on the known travelling salesman problems, and on specially developed problems with multiple depots and additional restrictions.
Conclusions. The proposed algorithms which are based on ant colony optimization are compared both in terms of accuracy and computation time. A hybrid algorithm achieved slightly better score, though computation time has increased.
Keywords: routing, combinatorial optimization, UAV, local search, ant colony optimization algorithms.
Cite as: Hulianytskyi L., Rybalchenko O. Formalization of the Problem of Optimization of Base Places and Routes of the UAV Group. Cybernetics and Computer Technologies. 2021. 4. P. 12–26. (in Ukrainian) https://doi.org/10.34229/2707-451X.21.4.2
References
1. Ramos T.R.P, Gomes M.I., Povoa, A.P.B. Multi-depot vehicle routing problem: a comparative study of alternative formulations. International Journal of Logistics Research and Applications. Jun, 2019. P. 103–120. https://doi.org/10.1080/13675567.2019.1630374
2. Bezerra S.N., Souza S.R., Souza M.J.F. A GVNS Algorithm for Solving the Multi-depot Vehicle Routing Problem. Electronic Notes in Discrete Mathematics. 2018. 66. P. 167–174. https://doi.org/10.1016/j.endm.2018.03.022
3. Nucamendi-Guillen S., Padilla A.G., Olivares-Benitez E. et al. The multi-depot open location routing problem with a heterogeneous fixed fleet. Expert Systems with Applications. 2020. 165. 113846. https://doi.org/10.1016/j.eswa.2020.113846
4. Horbulin V.P., Hulianytskyi L.F., Sergienko I.V. Optimization of UAV Team Routes in the Presence of Alternative and Dynamic Depots. Cybernetics and Systems Analysis. 2020. 56 (2). P. 195–203. https://doi.org/10.1007/s10559-020-00235-8
5. Hulianytskyi L.F., Rybalchenko O.V. Formalization and solution of the particular UAV routing problem. The theory of optimal solutions. 2018. 17. P. 107–114. (in Ukrainian) http://dspace.nbuv.gov.ua/handle/123456789/144979
6. Liu Y., Liu Z., Shi J., Wu G., Chen C. Optimization of Base Location and Patrol Routes for Unmanned Aerial Vehicles in Border Intelligence, Surveillance, and Reconnaissance. Hindawi Journal of Advanced Transportation. Volume 2019. Article ID 9063232. 13 p. https://doi.org/10.1155/2019/9063232
7. Sergienko I.V. Mathematical models and methods for solving discrete optimization problems. Kyiv: Naukova dumka, 1988. (in Russian)
8. Hulianytskyi L.F., Mulesa O.Yu. Applied methods of combinatorial optimization. Kyiv's University, 2016. 142 p. (in Ukrainian)
9. Dorigo M., Stützle T. Ant Colony Optimization: Overview and Recent Advances. Handbook of metaheuristics. Cham: Springer, 2019. P. 311–352. https://doi.org/10.1007/978-3-319-91086-4_10
10. Dorigo M., Stutzle T. Ant Colony Optimization. MIT Press, Cambridge. 2004. https://doi.org/10.7551/mitpress/1290.001.0001
11. Stützle T., Hoos H.H. MAX-MIN ant system. Future Generation Computer Systems. 2000. P. 889 – 914. https://doi.org/10.1016/S0167-739X(00)00043-1
12. Hulianytskyi L.F. Search diversification in ant colony optimization algorithms. The theory of optimal solutions. 2017. 16. P. 47–57. (in Ukrainian) http://dspace.nbuv.gov.ua/handle/123456789/131437
13. Library TSPLIB. http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/ (accessed: 14/12/2021)
14. Hulianytskyi L.F. ACO algorithms with diversified search. Intern. Science. symposium "Intelligent Solutions". Decision Theory: Proceedings of the IX International School-Seminar (Uzhhorod, April 15-20, 2019). Uzhhorod: UzhNU, 2019. P. 17–21. (in Ukrainian)
15. Mora A.M., García-Sánchez P., Merelo J.J. Pareto-based multi-colony multi-objective ant colony optimization algorithms: an island model proposal. Soft Computing. 2013. 17. Р. 1175. https://doi.org/10.1007/s00500-013-0993-y
ISSN 2707-451X (Online)
ISSN 2707-4501 (Print)
Previous | FULL TEXT (in Ukrainian) | Next