Light unmanned aerial vehicle flight routing in the fixed wind field on the basis of a solution of travelling salesman problem variants

Аuthors

Moiseev D. V.^1*, Trinh V. M.^2**, Mozolev L. A.^1***, Moiseeva S. G.^1****, Pham X. Q.^2*****

1. Moscow Aviation Institute (National Research University), 4, Volokolamskoe shosse, Moscow, А-80, GSP-3, 125993, Russia
2. Le Qui Don State Technical University, Quoc Viet street, Hanoi, 100000, Vietnam

*e-mail: moiseev801@mail.ru
**e-mail: trinhminh6666@gmail.com
***e-mail: leonidmozolev@mail.ru
****e-mail: svetlamois@mail.ru
*****e-mail: famvn@mail.ru

Abstract

The article formulates a number of problems of practical interest, such as detection of a light unmanned aerial vehicle (UAV) flyby route over predetermined points on the earth surface. Routing problem is reduced to different variants of closed and open traveling salesman problem. In particular, we considered variants for the open problem when information about starting and end points of a route is available, or not available. Flight duration over the route herewith is minimized, as far as it provides the rise in operativeness of target function solving. Lightweight UAV is characterized by a relatively small range and short flight time. This allows to assume speed and direction of wind as constant over the entire zone and flight time. Traveling salesman problem matrix elements, representing the flight time between pairs of points, are calculated taking into account the effect of wind. Routing problems under discussion are mathematically formalized as a linear integer programming problem with Boolean variables. Each of the considered arrangements presents its features in limitations and target function records. In terms of computing route preparation is reduced to the successive solution of integer linear programming problems with addition of conditions eliminating sub-loops. Solution algorithmic basis stems from branch-and-bound procedure, realized by MATLAB function bintprog. Thus, the main result of this paper is the development of a unified approach to mathematical formalization and numerical solution of a number of topical and called for in practice light UAV flight routing problems in the fixed wind. We present examples of flight routes. In particular, the calculation of the closed flyby route over 40 uniformly distributed in the flight area points on the computer with Intel ^® i3-4160 CPU @ 3.60GHz and 4.00 GB of RAM required 61 seconds.

Keywords:

the traveling salesman problem, flight routing problem, unmanned aerial vehicle, Boolean linear programming problem

References

1. Moiseev V.S., Gushchina D.S., Moiseev G.V. Osnovy teorii sozdaniya i primeneniya informatsionnykh aviatsionnykh kompleksov (Fundamentals of the theory of creation and application of information aviation systems), Kazan, Ministerstvo obrazovanija i nauki Respubliki Tatarstan, 2010, 196 p.
2. Moiseev V.S., Absaljamov M.N., Hakimullina A.R. Izvestiya Vuzov. Aviatsionnaya tekhnika, 2001, no. 1, pp. 16-23.
3. Podlip’jan P.E., Maksimov N.A. Elektronnyi zhurnal «Trudy MAI», 2011, no. 43, available at: http://www.mai.ru/science/trudy/published.php?ID=24769 (assessed 30.03.2011).
4. Ceccarelli Nicola, Enright John J., Frazzoli Emilio, Rasmussen Steven J. and Schumacher Corey J. Micro UAV Path Planning for Reconnaissance in Wind. Proceedings of the 2007 American Control Conference. New York City, USA, July 11-13, 2007.
5. Targamadze R.Ch., Moiseev D.V., Fam S.K. Vestnik FGUP NPO im. S.A.Lavochkina, 2012, no. 3, pp. 76-83.
6. Sigal I.H, Ivanova A.P. Vvedenie v prikladnoe diskretnoe programmirovanie: modeli i vychislitel’nye algoritmy (Introduction to Applied discrete programming: models and computational algorithms), Moscow, FIZMATLIT, 2003, 240 p.
7. Kozlov M.V., Kostjuk F.V., Sorokin S.V., Tjulenev A.V. Advanced Science, 2012, no. 2, pp. 124-141.
8. Kozlov M.V., Kostjuk F.V., Sorokin S.V., Tjulenev A.V. Advanced Science, 2012, no. 2, pp. 142-159.

Download