Formulation of multicriteria problem of routing and scheduling of manned and unmanned aircraft in a dynamic environment and approach to its solution using genetic algorithms

The article deals with the multi-criteria task of routing and scheduling of unmanned and manned aircraft using the method of penalty functions. The authors describe the urgency of the problem being solved for the airline management under the conditions of the existing changes in the dynamic situation with a great variety of flight situations. A mathematical statement of the problem is formulated and a universal optimality criterion is proposed in the form of a sum of additive and multiplicative forms, including partial quality indicators. The search for optimal and rational solutions to the problem of optimal flight routing, taking into account the airline fleet resources, airspace users' offers, constant and variable restrictions, associated, for example, with unfavorable weather conditions, can be implemented using a one-criteria and multi-criteria approach, but as a result, it is proposed to use a genetic algorithm that has low computational complexity and offers as solutions ("ancestors"), close to the optimal and rational result.  With this approach, an "elite" is formed at the beginning of the algorithm, which allows the crossing operation to be performed at each step of the iteration (evolution). As a result, we get new "descendants", and by rearranging at least one item from one block to the next one, we can get a sufficiently large number of representatives, from which a new "elite" can be selected with the help of the criterion. The practice of using genetic algorithms has shown that along with the achievement of a global extremum with it, the process of substantial improvement of planning results is achieved in several evolution steps, and their number is clearly less than the number of steps when using numerical methods of parametric optimization.  The proposed approach will significantly improve the efficiency and quality of flight planning for the airline, taking into account the diversity of aircraft fleet, payload and environmental impact. This task is especially important under the conditions of joint management (CDM), where aeronautical data can be considered as additional criteria.

penalty functions, optimal control, aircraft, genetic algorithm, collaborative decision-making (CDM)

1. Borsoev, V.A., Lebedev, G.N., Malygin, V.B., Nechaev, E.E., Nikulin, A.O. and Tin, Pkhon Chzho. (2018). Prinyatie resheniya v zadachakh upravleniya vozdushnym dvizheniyem. Metody i algoritmy [Decision Making in Air Traffic Management Tasks. Methods and Algorithms]. Moscow: Radiotekhnika, 432 p., pp. 351–414. (in Russian)

2. Allilueva, N.V. and Rudenko, E.M. (2017). Matematicheskiy metod rascheta celevoy funktsii na grafakh i reshenie zadachi marshrutizatsii [Athematic method of calculating the objective function on graphs and solving routing problems]. Trudy MAI [Proceedings of MAI], no. 96. (in Russian)

3. Chekhov, I.A. and Chekhov, O.I. (2017). Algoritm formirovaniya dinamicheskoy ocheredi BPLA pri zahode na posadku [Algorithm for the formation of a dynamic queue of UAVs at the approach]. Civil Aviation High Technologies, vol. 20, no. 4, рр. 25–30. (in Russian)

4. Zaitsev, A.V. and Talimanchuk, L.L. (2008). Intellektualnaya sistema prinyatiya resheniy dlya otsenki nauchnoy deyatelnosti na osnove mnogoagentnoy sistemi [Intellectual decisionmaking system for the evaluation of scientific activity on the basis of a multi-segment system]. Neyrokomputers: razrabotka, primenenie [Neurocomputers], no. 7, pр. 85–88. (in Russian)

5. Kuznetsova, T.I. and Tsaregorodtseva, M.G. (2016). Kompleksnaya otsenka kachestva izucheniya inostrannogo yazika v vide summi additivnoy i multiplikativnoi svertok otdelnikh pokazateley [Comprehensive assessment of the quality of learning a foreign language in the form of a sum of additive and multiplicative convolutions of individual indicators]. Trudy XXV mezhdunarodnoy konferentsii «Sovremennie tekhnologii v zadachah upravleniya, avtomatiki I obrabotki informatsii» [Proceedings of the international conference «Modern technologies in control, automation and information processing problems], Alushta, 2016, Technology, p. 208. (in Russian)

6. Sobol, E.M. and Statnikov, R.B. (1981). Vibor optimalnih parametrov v zadachah so mnogimi kriteriyami [The choice of optimal parameters in problems with many criteria]. M.: Nauka, 110 p.

7. Programmy razvitiya system organizatsii vozdushnogo dvizheniya Evropy i SSHA SESAR i NextGen: analiticheskiy obzor po materialam zarubezhnikh informatsionnikh istochnikov [Programs for the development of air traffic management systems in Europe and the US SESAR and NextGen: an analytical review on the materials of foreign information sources]. (2011). Ed. E.A. Fedosov. Moscow: GosNIIAS. 256 p. (in Russian)

8. Lebedev, G.N., Malygin, V.B. and Mikhaylin, D.A. (2017). Postanovka i reshenie zadachi operativnoy korrektsii prileta i vileta vozdushnikh sudov v rayone aerodroma s pomoschyu geneticheskogo algoritma [The formulation and solution of the problem of the operational correction of the arrival and departure of aircraft in the area of the aerodrome with the help of a genetic algorithm]. Civil Aviation High Technologies, vol. 20, no. 4, pр. 8–15. (in Russian)

9. Lugovaya, A.V. and Konovalov, A.E. (2017). Sovmestnoe prinyatie resheniya o potokakh prileta i vileta VS pri organizacii vozdushnogo dvizheniya [Joint decision-making on the arrival and departure flows in the organization of air traffic]. Civil Aviation High Technologies, vol. 20, no. 4, pp. 8–15. (in Russian)

10. Kulakov, Yu.A., Kogan, A.V. and Morozovskiy, T.O. (2015). Sposob organizatsii mnogoputevoy marshrutizatsii s pomoschyu modifitsirovannogo metoda vetvey i granits [A way to organize multi-path routing using a modified branch and bound method]. Visnik NTUU «KPI». Informatika, upravlennya ta obchislyuvalna tehknika [Bulletin of NTUU «KPI». Computer Science, Management and Computing], no. 62, pр. 27–31. URL: http://it-visnyk.kpi.ua (available at: 28.08.2018). (in Russian)