Air space routing and flights planning: A problem statement and discussion of approaches to solution

  • 1 Lviv Polytechnic National University, Lviv, Ukraine


Air routing has become an important problem of recent years. Wide implementation of idea to use a free routing airspace (FRA) over the Europe and idea of exploiting FRA as a main airspace management resource to reduce air traffic problems revealed a necessity of a new look to a routing problem. Many previous solutions relied on predefined topology of airways and ability to exploit welldeveloped methods known in graph theory. Meanwhile the problem was current due to many factors needed to be involved in the airspace as a 3D-space: air management restrictions and different air spaces regulation rules, weather conditions, danger areas, aircraft’s characteristics, pilots’ preferences, etc. Moreover, the appearance of FRA has made it inappropriate to use previous algorithms. Most of these algorithms required a definite topology with known routing points connected with predefined edges, while the FRA may have only border points to fly into or fly out of the area and no definite edges inside. The task of constructing the route became the same difficult as obvious: any pilot can fly directly through the FRA, but the route should be built and confirmed prior to a take-off. Problem comes even more evident if considered for the unmanned flying vehicles (UFV) and the need for robots or AI systems to solve the routing problem by itselves. As a topping of the complexity of the problem, one may consider the upcoming difficulties of airspace congestion in FRA. Despite the problem is known for areas close to airports, it is still current to plan routes avoiding flights conflicts in the air and to avoid FRA high congestion. There are different researches on some particular problems and some approaches to solve these problems. Nevertheless, there is no complex problem statement yet. This research was focused on need of understanding the full scope of problems for air routing to understand the ability to build an efficient solution for the problem as a whole.



  1. Flight Planning in Free Route Airspaces / Casper Kehlet Jensen, Marco Chiarandini, and Kim S. Larsen // 17th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2017), 2017 – 14p.
  2. Conflict Free and Efficient Flight Routes Planning In Free Route Airspace / Mariusz Krzyanowski // Prace Naukowe Politechniki Warszawskiej. Transport, 2013. – P.277-285
  3. Four-Dimensional Aircraft En Route Optimization Algorithm Using the Artificial Bee Colony / Murrieta-Mendoza, Alejandro; Botez, Ruxandra Mihaela; Bunel, Audric // Journal of Aerospace Information Systems – Vol. 15 Issue 6, Jun. 2018 – P. 307-334.
  4. Lateral Navigation Optimization Considering Winds and Temperatures for Fixed Altitude Cruise using the Dijsktra’s Algorithm / Murrieta-Mendoza, Alejandro; Botez, Ruxandra // Proceedings of the ASME International Mechanical Engineering Congress and Exposition, Nov. 2014 – Vol. 1, 2015. – 9 p.
  5. A Practical Approach For Optimizing Aircraft Trajectories In Winds / Ng, Hok K.; Sridhar, Banavar; Grabbe, Shon // IEEE/AIAA 31st Digital Avionics Systems Conference (DASC) Location: Williamsburg, VA, Oct. 14-18, 2012. – 14 p.
  6. Generating Optimal Aircraft Trajectories with respect to Weather Conditions / B. Girardet, L. Lapasset, D. Delahaye, C. Rabut, and Y. Brenier. // ISIATM, 2013. – 12 p.
  7. Optimizing Aircraft Trajectories with Multiple Cruise Altitudes in the Presence of Winds / Ng, Hok K.; Sridhar, Banavar; Grabbe, Shon // Journal of Aerospace Information Systems – Vol. 11, Issue 1, Jan. 2014. – P. 35-46.
  8. Aircraft Path Planning under Adverse Weather Conditions / Xie Z. and Zhong Z.W. // MATEC Web of Conferences 77, 15001 (2016), ICMMR 2016 – 4 p.
  9. Air route network optimization in fragmented airspace based on cellular automata / Shijin Wang, Xi Cao, Haiyun Li, Qingyun Li, Xu Hang, Yanjun Wang // Chinese Journal of Aeronautics – No. 30 (3), 2017 – P. 1184–1195.
  10. A novel meta-heuristic algorithm for numerical function optimization: Blind, naked mole-rats (BNMR) algorithm / Mohammad Taherdangkoo, Mohammad Hossein Shirzadi, and Mohammad Hadi Bagheri. // Scientific Research and Essays – Vol. 7 (41), Oct. 2012 – P. 3566-3583 – Retrieved from:
  11. A model for rolling swarms of locusts / Topaz, C., Bernoff, A., Logan, S., Toolson, W. // The European Physical Journal Special Topics – Vol. 157, 2008. – P.93–109.
  12. Grasshopper Optimisation Algorithm: Theory and application / Saremi S., Mirjalil S., Lewis A. // Advances in Engineering Software – Vol. 105, Mar. 2017 – P.30-47
  13. Application of Grasshopper Optimization Algorithm for Constrained and Unconstrained Test Functions / A.G. Neve, G.M. Kakandikar, and O. Kulkarni // International Journal of Swarm Intelligence and Evolutionary Computation – Vol. 6, Issue 3, Art. No. 1000165, 2017. – 7 p. – Retrieved from:

Article full text

Download PDF