Cybernetics And Systems Analysis logo
Editorial Board Announcements Abstracts Authors Archive
Cybernetics And Systems Analysis
International Theoretical Science Journal
Volume 56 >>> № 2 MARCH — APRIL 2020
UDC 519.8
V.P. Horbulin1, L.F. Hulianytskyi2, I.V. Sergienko3


1 vice-president of the National Academy of Sciences of Ukraine,
Kyiv, Ukraine

 horbulin@nas.gov.ua

2 V.M. Glushkov Institute of Cybernetics, National Academy
of Sciences of Ukraine, Kyiv, Ukraine

 leonhul.icyb@gmail.com

3 V.M. Glushkov Institute of Cybernetics, National Academy
of Sciences of Ukraine, Kyiv, Ukraine

 incyb@incyb.kiev.ua

OPTIMIZATION OF UAV TEAM ROUTES AT THE AVAILABILITY OF ALTERNATIVE
AND DYNAMIC DEPOTS

Abstract. The paper considers the problems of optimization of unmanned aerial vehicle (UAV) routes which act as a team when inspecting or supporting a given set of objects in the presence of alternative and dynamic depots (starting and/or landing sites) and resource constraints. Problem definition and mathematical models are proposed. Such problems, in particular, include UAV flight planning problems, which use moving platforms as a depot. The optimization criteria are both the total length of the routes and the number of UAVs involved. Algorithms for solving formulated combinatorial optimization problems based on ant colony optimization, tabu search, and exhaustive search have been developed and implemented. The results of the computational experiment are presented.

Keywords: route optimization, UAV, ant algorithms, dynamic depo, tabu search, gremlins.



FULL TEXT

REFERENCES

  1. Ponda S.S., Johnson L.B., Geramifard A., How J.P. Cooperative mission planning for multi-UAV teams. In: Valavanis K., Vachtsevanos G. (Eds). Handbook of Unmanned Aerial Vehicles. Dordrecht: Springer, 2015. P. 1447–1490.

  2. Otto A., Agatz N., Campbell J., Golden B., Pesch E. Optimization approaches for civil applications of unmanned aerial vehicles (UAVs) or aerial drones: A survey. Networks. 2018. Vol. 72, Iss. 4. P. 411–458.

  3. Gorbulin V.P. Defense and security of Ukraine: current problems and ways to solve them. Visn. NAS of Ukraine. 2019. N 9. P. 3–18.

  4. Coutinho W.P., Battarra M., Fliege J. The unmanned aerial vehicle routing and trajectory optimisation problem, a taxonomic review. Computers & Industrial Engineering. 2018. Vol. 120. P. 116–128.

  5. Zhao Y., Zheng Z., Liu Y. Survey on computational-intelligence-based UAV path planning. Knowledge-Based Systems. 2018. Vol. 158. P. 54–64.

  6. Gulyanitsky L.F., Rybalchenko O.V. Formalize and solve one type of UAV routing tasks. Teoriya optymalʹnykh rishenʹ. 2018. N 17. P. 107–114.

  7. Perez-Carabaza S., Besada-Portas E., Lopez-Orozco J.A., Jesus M. Ant colony optimization for multi-UAV minimum time search in uncertain domains. Applied Soft Computing. 2018. Vol. 62. P. 789–806.

  8. Cekmez U., Ozsiginan M., Sahingoz O.K. Multi-UAV path planning with multi colony ant optimization. In: International Conference on Intelligent Systems Design and Applications (2017, December). Cham: Springer, 2017. P. 407–417.

  9. Chiang W.C., Li Y., Shang J., Urban T.L. Impact of drone delivery on sustainability and cost: Realizing the UAV potential through vehicle routing optimization. Applied Energy. 2019. Vol. 242. P. 1164–1175.

  10. Binol H., Bulut E., Akkaya K., Guvenc I. Time optimal multi-UAV path planning for gathering ITS data from roadside units. In: 88th Vehicular Technology Conference (VTC-Fall) (2018, August). IEEE, 2018. P. 1–5.

  11. Xu C., Duan H., Liu F. Chaotic artificial bee colony approach to uninhabited combat air vehicle (UCAV) path planning. Aerospace Science and Technology. 2010. Vol. 14, Iss. 8. P. 535–541.

  12. Tian G., Zhang L., Bai X., Wang B. Real-time dynamic track planning of multi-UAV formation based on improved artificial bee colony algorithm. In: 37th Chinese Control Conference (CCC) (2018, July). IEEE, 2018. P. 10055–10060.

  13. Shakhatreh H., Khreishah A., Alsarhan A., Khalil I., Sawalmeh A., Othman, N.S. Efficient 3D placement of a UAV using particle swarm optimization. In: 8th International Conference on Information and Communication Systems (ICICS) (2017, April). IEEE, 2017. P. 258–263.

  14. Austin R. Unmanned aircraft systems. UAVs design, development and deployment. West Sussex: John Wiley and Sons, 2010. 365 p.

  15. Tsourdos A., White B., Shanmugavel M. Cooperative path planning of unmanned aerial vehicles. West Sussex: John Wiley and Sons, 2011. 212 p.

  16. Shima T., Rasmussen S. UAV cooperative decision and control. Challenges and practical approaches. Philadelphia: SIAM, 2009. 186 p.

  17. Toth P., Vigo D. (Eds.). Vehicle routing: problems, methods, and applications. Philadelpia: SIAM, 2014. 462 p.

  18. Braekers K., Ramaekers K., Nieuwenhuyse I.V. The vehicle routing problem: State of the art classification and review. Computers & Industrial Engineering. 2016. Vol. 99. P. 300–313.

  19. Karakati S., Podgorelec V. A survey of genetic algorithms for solving multi depot vehicle routing problem. Applied Soft Computing. 2015. Vol. 27. P. 519–532.

  20. Soto M., Sevaux M., Rossi A., Reinholz A. Multiple neighborhood search, tabu search and ejection chains for the multi-depot open vehicle routing problem. Computers & Industrial Engineering. 2017. Vol. 107. P. 211–222.

  21. Gorbulin V.P., Gulyanitsky L.F., Sergienko I.V. Formulations and mathematical models of problems of optimization of routes of aircraft with dynamic depots. Upravlyayushchiye sistemy i mashiny. 2019. N 1. P. 3–10.

  22. Husseini T. Gremlins are coming: DARPA enters Phase III of its UAV programme. Army Technology, 3 July 2018. URL: https://www.army-technology.com/features/gremlins-darpa-uav-programme/.

  23. Gulyanitsky L.F. The problem of optimizing vehicle routes with time windows. Komp'yuternaya matematika. 2007. N 1. P. 122–132.

  24. Anderson J. Discrete mathematics with combinatorics. Moscow; SPb; Kiev: Williams, 2003. 957 p.

  25. Dorigo M., Stutzle T. Ant colony optimization: Overview and recent advances. In: Handbook of Metaheuristics. Cham: Springer, 2019. P. 311–352.

  26. Stutzle T., Hoos H.H MAX-MIN ant system. Future Generation Computer Systems. 2000. Vol. 16, Iss. 8. P. 889–914.

  27. Gulianytskyi LF, Mules OY Applied combinatorial optimization methods. Kyiv: Kyiv University, 2016. 142 p.

  28. Gulyanytskyi L.F. New ant colony optimization algorithm. Modern informatics: Problems, achievements and prospects for development: Proc. Int. conf., dedicated to the 60th anniversary of the V.M. Glushkov IC of NAS of Ukraine (Kyiv, December 13-15, 2017). Kyiv: V.M. Glushkov Institute of Cybernetics of NAS of Ukraine, 2017. P. 41–43.

  29. Mora A.M., GarcЗa-Sanchez P., Merelo J.J., Castillo P.A. Pareto-based multi-colony multi-objective ant colony optimization algorithms: an island model proposal. Soft Computing. 2013. Vol. 17, Iss. 7. Р. 1175.–1207.
Editorial Board Announcements Abstracts Authors Archive
about scope office editorial board instructions for authors subscriptions contacts
© 2020 Kibernetika.org. All rights reserved.