RADIOELECTRONIC AND COMPUTER SYSTEMS

Motivation. One of the tasks of nuclear power plants and other potentially dangerous objects monitoring employing unmanned aerial vehicles (UAV) is flying over specified points of the territory of such objects. Finding the optimum routes often involves different options for the traveling salesman problem solving. However, if there are multiple starting positions, there is a need to solve the traveling salesman problem for each variant of the UAV start (for each variant of the start-end point of the route). The subject matter of the paper is the process of minimizing the flight time of visiting the specified points of the potentially dangerous object territory, taking into account the locations and models of the UAV fleet. The tasks to be solved are: to develop an algorithm for determining the optimal route for flight over of the given points of the potentially dangerous object territory for the fleet, each UAV of which is at its separate starting position; to show the possibility of using the proposed algorithm to minimize the flight time for visiting all of the appointed control posts of the automated radiation situation monitoring system for Zaporizhzhia nuclear power plant. The methods used are: graph theory, mathematical optimization models, methods for solving the traveling salesman problem. The following results were obtained. The faceted classification of the traveling salesman problem for UAV flight routing is offered. The steps of the algorithm for determining the optimal route of flight over of the specified points of the potentially dangerous object territory by the UAV fleet are described. The problem of determining the fastest flight over of 11 control posts of the automated radiation monitoring system for Zaporizhzhia nuclear power plant is solved for two cases: 1) UAV "Leleka-100" are at all starting positions, 2) UAV "Leleka-100" is at the first starting position, various modifications of the model "R-100" are at the rest starting position. Changes in the optimal route when changing UAV models and speeds are shown. Conclusions. The results obtained should be used to justify the composition of the UAV fleet, simulate its application, evaluate its target effectiveness, as well as to create algorithmic support and software for ground control station operators’ work places. Further research should focus on developing models that take into account the possibility of refueling UAVs or recharging their batteries at stationary or moving posts while being on a route.

unmanned aerial vehicle; potentially dangerous object; traveling salesman problem; flight routing; starting position; automated radiation monitoring system; control post

Sachenko, A. A., Kochan, V. V., Kharchenko, V. S., Yastrebenetskii, M. A., Fesenko, G. V., Yanovskii, M. E. Sistema posleavariinogo monitoringa AES s ispol'zovaniem bespilotnykh letatel'nykh apparatov: kontseptsiya, printsipy postroeniya [NPP post-accident monitoring system based on unmanned aircraft vehicle: сoncept, design principles]. Yaderna ta radiatsiina bezpeka – Nuclear and Radiation Safety, 2017, vol. 73, no. 1, pp. 24–29.

Kharchenko, V. S., Yastrebenetskii, M. A., Fesenko, G. V., Sachenko, A. A., Kochan, V. V. Sistema posleavariinogo monitoringa AES s ispol'zovaniem bespilotnykh letatel'nykh apparatov: modeli nadezhnosti [NPP post-accident monitoring system based on unmanned aircraft vehicle: reliability models]. Yaderna ta radiatsiina bezpeka – Nuclear and Radiation Safety, 2017, vol. 76, no. 4, pp. 50–55.

Fesenko, H. Optimal redistribution of UAVs in case of changing monitoring zones after a NPP accident. 9th IEEE International Conference on Dependable Systems, Services and Technologies (DESSERT), Kyiv, Ukraine, 5-7 June, 2018, pp. 48–52.

Fesenko, H. V. Minimizatsiya chasu pochatku vykonannya flotom bezpilotnykh lital'nykh aparativ zavdannya z radiatsiynoho monitorynhu v noviy zoni vidpovidal'nosti [Minimization of the waiting time to start performing a radiation monitoring mission via a fleet of unmanned aerial vehicles in the new zone of responsibility]. Systemy ta tekhnolohiyi – Systems and Technologies, 2019, vol. 57, no. 1, pp. 5–20.

Fesenko, H. V., Kharchenko, V. S. Modeli nadiynosti uhrupovan' flotiv BPLA z kovznym rezervuvannyam dlya monitorynhu potentsiyno nebezpechnykh ob"yektiv [Reliability models of UAV fleet groups with k-out-of-n redundancy for monitoring of potentially dangerous objects]. Radioelektronni i komp"yuterni systemy – Radioelectronic and Computer Systems, 2019, vol. 90, no. 2, pp. 147–146. DOI: 10.32620/reks.2019.2.14.

Vestron. ASKRO ZAES. Tekhnicheskoe zadanie. TZ – VN 702.410.34 [Vestron. ZNPP ARSMS. Technical decision. TZ – VN 702.410.34]. Kharkiv, 2011. 22 р.

Moiseev, D. V., Chin', V. M., Mozolev, L. A., Moiseeva, S. G., Kuen, F. S. Marshrutizatsiya poleta legkogo bespilotnogo letatel'nogo apparata v pole postoyannogo vetra na osnove resheniya raznovidnostei zadachi kommivoyazhera [Flight routing of lightweight unmanned aerial vehicle in a constant wind field on the basis of the decision of species of the traveling salesman problem]. Elektronnyi zhurnal «Trudi MAI» – Electronic journal of Moscow Aviation Institute Transactions, 2015, no. 79. Available at: http://trudymai.ru/published.php?ID=55782 (аccessed 10.08.2019).

Moiseev, D. V., Chin', V. M. Marshrutizatsiya poleta legkogo bespilotnogo letatel'nogo apparata v pole postoyannogo vetra s uchetom ogranicheniya na prodolzhitel'nost' poleta [Flight routing of a light unmanned aerial vehicle in a constant wind field with account of constraint on the flight duration]. Mekhatronika, avtomatizatsiya, upravlenie – Mechatronics, Automation, Control, 2016, vol. 17, no. 3, pp. 206–209. DOI: 10.17587/mau/17.206-210.

Dmitriev, V. I., Grushevoi, S. A. Optimizatsiya marshruta peremeshcheniya bespilotnykh letatel'nykh apparatov s retranslyatorami radiosvyazi [Optimizing the route of unmanned aerial vehicles with radiorepeaters]. Vestnik RGRTU – RSRU Bulletin, 2018, no. 63, pp. 64–67. DOI: 10.21667/1995-4565-2018-63-1-64-68.

Ivanov, A. A. Geneticheskii algoritm resheniya zadachi kommivoyazhera dlya planirovaniya marshruta bespilotnogo letatel'nogo apparata [The genetic algorithm for solving the traveling salesman problem for UAV flight routing]. Otkrytye informatsionnye i komp'yuternye integrirovannye tekhnologii – Open Information and Computer Integrated Technologies, 2016, no. 71, pp. 202–205.

Allilueva, N. V., Rudenko, E. M. Zadacha marshrutizatsii BPLA na grafe repernykh tochek [A UAV routing problem on the graph of reference points]. I-methods, 2018, vol. 10, no. 1, pp. 5-18.

Min', Ch. V. Planirovanie marshruta poleta legkogo bespilotnogo letatel'nogo apparata s uchetom deistviya vetra. Avtoref. Kand. Diss. [Light unmanned aerial vehicle flight planning taking into account wind action. PhD Diss. Rep.]. Moscow, 2017. 22 p.

Sebbane, Y. B. Intelligent autonomy of UAVs: advanced missions and future use, CRC Press, 2018. 404 p.

Murray, C. C., Chu, A. G. The flying sidekick traveling salesman problem: Optimization of drone-assisted parcel delivery. Transportation Research Part C: Emerging Technologies, 2015, vol. 54, pp. 86–109. DOI: 10.1016/j.trc.2015.03.005

Ha, M. Q., Deville, Y., Pham, D. G., Ha, M. H. On the min-cost traveling salesman problem with drone. Transportation Research Part C: Emerging Technologies, 2018, vol. 86, pp. 597–621. DOI: 10.1016/j.trc.2017.11.015.

Kitjacharoenchai, P., Ventresca, M., Moshref-Javadi, M., Lee, S., Tanchoco, J. A., Brunese, P. A. Multiple traveling salesman problem with drones: Mathematical model and heuristic approach. Computers & Industrial Engineering, 2019, vol. 129, pp. 14–30. DOI: 10.1016/j.cie.2019.01.020.