Control Systems and Computers

https://doi.org/10.15407/usim.2019.01.003

Upr. sist. maš., 2019, Issue 1 (279), pp. 3-10.

UDC 519.8

V.P. HORBULIN, Academician of the National Academy of Sciences of Ukraine, First Vice-President of the National Academy of Sciences of Ukraine, 54 Volodymyrska Str., Kyiv-30, 01601, Ukraine, horbulin@nas.gov.ua

L.F. HULIANYTSKYI, Doctor of Technical Sciences, Professor,
Head of Department V.M. Glushkov Institute of Cybernetics of NAS of Ukraine, 40 Acad. Glushkova Ave., 03680, Kyiv, Ukraine, leonhul.icyb@gmail.com

I.V. SERGIENKO, Academician of the National Academy of Sciences of Ukraine, Director V.M. Glushkov Institute of Cybernetics of NAS of Ukraine, 40 Acad. Glushkova Ave., 03680, Kyiv, Ukraine, incyb@incyb.kiev.ua

FORMULATIONS AND MATHEMATICAL MODELS OF THE OPTIMIZING ROUTES PROBLEMS FOR AIRCRAFT WITH DYNAMIC DEPOTS

Introduction. In recent years there has been a tendency to expand the use of unmanned vehicles, in particular, unmanned aerial vehicles (UAVs). In addition to the tasks of routing the aircraft launching from the ground, the problem of routing has recently become topical for the aircraft (UAVs or cruise missiles) that are launched from a special aircraft carrier, the route of which is laid subject to possible restrictions. The problems of finding the optimal routes for a special aircraft group, in particular, UAVs, which can start and complete the route on an aircraft carrier, are considered.

Purpose. Analysis and formalization of routing problems of the specified type.

Methods. Mathematical models development to find the optimal routes for the aircraft using an aircraft carrier, that are focused on the use of combinatorial optimization methods.

Results. A new mathematical model has been developed for the problems where a given aircraft group, that can start from different launch points and has the ability to complete the route in different places of the aircraft carrier trajectory, has the task to fly over a number of specified objects (points on the ground) with minimizing the total route lengths or flight duration, provided that each object is visited by one and only one aircraft and all objects must be visited.

Conclusion. For the first time the problem of routing is considered for the case when aircraft start from an aircraft carrier and finish the route on it. Based on realistic assumptions reflecting the technical aspects of the process, the formalization of this problem is proposed as a special combinatorial optimization problem, which is called the routing problem with dynamic depots. The possible approaches to its solution based on the using the neighborhoods of a special type are discussed.

 Download full text! (In Ukrainian)

Keywords: unmanned aerial vehicles, route optimization, dynamic depots, mathematical model, combinatorial optimization.

1. Ponda, S.S., Johnson, L.B., Geramifard, A., How, J.P., 2015. “Cooperative mission planning for multi-UAV teams”. In Handbook of Unmanned Aerial Vehicles. Dordrecht: Springer, pp. 1447-1490.
   https://doi.org/10.1007/978-90-481-9707-1_16
2. Austin, R., 2010. Unmanned Aircraft Systems. UAVs Design, Development And Deployment. West Sussex: John Wiley and Sons, 365 p.
   https://doi.org/10.1002/9780470664797
3. Tsourdos, A., White, B., Shanmugavel, M., 2011. Cooperative Path Planning of Unmanned Aerial Vehicles. West Sussex: John Wiley and Sons, 212 p.
   https://doi.org/10.1002/9780470974636
4. Shima, T., Rasmussen, S., 2009. UAV Cooperative Decision and Control. Challenges and Practical Approaches. Philadelphia: SIAM, 186 p.
   https://doi.org/10.1137/1.9780898718584
5. Toth, P., Vigo, D., 2014. Vehicle routing: problems, methods, and applications. Society for Industrial and Applied Mathematics, 462 p.
   https://doi.org/10.1137/1.9781611973594
6. Braekers, K., Ramaekers, K., Nieuwenhuyse, I.V., 2015. “The Vehicle Routing Problem: Stateof the Art Classification and Review”. Computers & Industrial Engineering, pp. 300-313.
   https://doi.org/10.1016/j.cie.2015.12.007
7. Karakatiu, S., Podgorelec, V., 2015. “A survey of genetic algorithms for solving multi depot vehicle routing problem”. Applied Soft Computing, 27, pp. 519-532.
   https://doi.org/10.1016/j.asoc.2014.11.005
8. Hulianytskyi, L.F., Rybalchenko, O.V., 2018. “Formalizatsiya ta rozv’yazuvannya odnoho typu zadach marshrutyzatsiyi BPLA”. Teoriya optymalʹnykh rishen, 17, pp. 107-114. (In Ukrainian).
9. Serhiyenko, I.V., 2010. Metody optymizatsiyi ta systemnoho analizu dlya zadach transobchyslyuvalʹnoyi skladnosti. K.: Akademperiodyka, 318 p. (In Ukrainian).
10. Hulianytskyi, F., Riasna, I.I., 2017. “Formalization and classification of combinatorial optimization problems”. In Optimization Methods and Applications (eds. Butenko S., Pardalos P. M., Shylo V.). Cham: Springer International Publishing AG, pp. 239-250.
    https://doi.org/10.1007/978-3-319-68640-0_11
11. Hulianytskyi, L.F., Mulesa, O.Yu., 2016. Prykladni metody kombinatornoyi optymizatsiyi. K.: Vyd.-polihraf. tsentr “Kyyivsʹkyy universytet”, 142 p. (In Ukrainian).
12. Arbanas, et al., 2018. “Decentralized planning and control for UAV-UGV cooperative teams”. Autonomous Robots, 42 (8), pp.1601-1618.
    https://doi.org/10.1007/s10514-018-9712-y

Received 27.11.2018