Skip to main content
Skip to article control options
No AccessFull-Length Paper

Metaheuristic Approach for Distributed Trajectory Planning for European Functional Airspace Blocks

Published Online:

The functional airspace block (FAB) concept is adopted by European airspace to allow cooperation between airspace users to manage the air traffic flow, while ensuring efficiency, safety, and fairness without the constraints of geographical boundaries. This integration of airspaces allows for flexibility in airspace management and aircraft trajectory planning. This paper proposes a distributed air traffic flow management model to address four-dimensional trajectory planning over the European FAB. The proposed method is based on a metaheuristic approach that uses a hybrid algorithm of simulated annealing and hill-climbing local search to separate a given set of aircraft trajectories in space and time domain (termed as flight interaction), by allocating an alternative flight plan (route and departure time) to each flight. An innovative data structure, termed as FAB–flight interaction matrix, captures the flight interaction information between and within FABs. The proposed distributed model is implemented and tested with two air traffic data sets comprising 4000 flights (3 h traffic) and 26,000 flights (one full day traffic data over the European airspace). The performance of the model is then compared with a centralized air traffic flow management model on scalability and interaction minimization. Results indicates that, though both approaches were able to achieve interaction-free trajectory planning within computational time acceptable for the operational context, the distributed model converges faster to an interaction-free solution as traffic size increases, which shows the viability of the distributed model for effective FAB implementation.


  • [1] Manual on Collaborative Air Traffic Flow Management, 2nd ed., International Civil Aviation Organization, Document 9971 AN/485, Montreal, 2014. Google Scholar

  • [2] Button K. and Neiva R., “Single European Sky and the Functional Airspace Blocks: Will They Improve Economic Efficiency?Journal of Air Transport Management, Vol. 33, Oct. 2013, pp. 73–80. doi: Google Scholar

  • [3] Dubot T., Aubry S. and Bedouet J., “Building a Smooth and Dynamic Opening Scheme from Graph Partitioning-Exploring Dynamic Airspace Configurations,” 15th AIAA Aviation Technology, Integration, and Operations Conference, AIAA Paper 2015-3403, 2015. LinkGoogle Scholar

  • [4] Single European Sky Legislative Package,” Tech. Rept.  1070/2009, European Commission, Strasbourg, France, 2009. Google Scholar

  • [5] Eurocontrol Functional Airspace Block,” [accessed 20 June 2018]. Google Scholar

  • [6] Angenendt A., “DFS on Central Flow Management Unit,” Skyway Magazine Eurocontrol, Vol. 9, No. 39, 2005, p. 23. Google Scholar

  • [7] Performance Review Report, PRR 2008,” Tech. Rept., EUROCONTROL, Brussels, 2008. Google Scholar

  • [8] Adler N., Hanany E. and Proost S., “Managing European Air Traffic Control Provision,” Proceedings of the 4th SESAR Innovation Days, Nov. 2014, Google Scholar

  • [9] Luppo A., Argunov G., Gorlenko N. and Chaika V., “Optimisation of the Performance of the ATM Network in Europe,” Proceedings of the National Aviation University, Vol. 59, No. 2, 2014, pp. 37–43. Google Scholar

  • [10] Modić A., Steiner S. and Mihetec T., “Performance Scheme Implementation in Functional Airspace Block Central Europe,” Proceedings of the 22nd International Symposium on Electronics in Transport ISEP 2014: ITS for Seamless and Energy Smart Transport, Electrotechnical Assoc. of Slovenia, 2014. Google Scholar

  • [11] Ichoua S., “A Scenario-Based Approach for the Air Traffic Flow Management Problem with Stochastic Capacities,” International Journal of Mechanical, Aerospace, Industrial and Mechatronics Engineering, Vol. 7, No. 8, 2013. Google Scholar

  • [12] Holland J. H., Adaptation in Natural and Artificial Systems: An Introductory Analysis with Applications to Biology, Control, and Artificial Intelligence, MIT Press, Cambridge, MA, 1992. Google Scholar

  • [13] Hansen J. V., “Genetic Search Methods in Air Traffic Control,” Computers and Operations Research, Vol. 31, No. 3, 2004, pp. 445–459. doi: Google Scholar

  • [14] Cheng V., Crawford L. and Menon P., “Air Traffic Control Using Genetic Search Techniques,” Proceedings of the 1999 IEEE International Conference on Control Applications, Vol. 1, IEEE Publ., Piscataway, NJ, Aug. 1999, pp. 249–254. doi: Google Scholar

  • [15] Du W., Liang B., Yan G., Lordan O. and Cao X., “Identifying Vital Edges in Chinese Air Route Network via Memetic Algorithm,” Chinese Journal of Aeronautics, Vol. 30, No. 1, 2017, pp. 330–336. doi: CJAEEZ 1000-9361 Google Scholar

  • [16] Delahaye D., Durand N., Alliot J.-M. and Schoenauer M., “Genetic Algorithms for Air Traffic Control Systems,” Proceedings of the 14th Triennal Conference of the International Federation of Operational Research Societies, Vancouver, Canada, 1996. Google Scholar

  • [17] Chaimatanan S., Delahaye D. and Mongeau M., “Large Scale 4D Trajectory Planning,” IEEE Computational Intelligence Magazine, Vol. 9, No. 4, 1989, pp. 46–61. Google Scholar

  • [18] Bertsimas D. and Gupta S., “Fairness in Air Traffic Flow Management,” INFORMS Meeting, Vol. 54, Catonsville, USA, 2009, p. 100. Google Scholar

  • [19] Barnhart C., Fearing D., Odoni A. and Vaze V., “Demand and Capacity Management in Air Transportation,” EURO Journal on Transportation and Logistics, Vol. 1, Nos. 1–2, 2012, pp. 135–155. doi: Google Scholar

  • [20] Glover C. and Ball M., “Stochastic Optimization Models for Ground Delay Program Planning with Equity–Efficiency Tradeoffs,” Transportation Research Part C: Emerging Technologies, Vol. 33, Aug. 2013, pp. 196–202. doi: Google Scholar

  • [21] Mukherjee A., Grabbe S. and Sridhar B., “Predicting Ground Delay Program at an Airport Based on Meteorological Conditions,” 14th AIAA Aviation Technology, Integration, and Operations Conference, AIAA Paper 2014-2713, 2014. LinkGoogle Scholar

  • [22] Kirkpatrick S., Gelatt C. D. and Vecchi M. P., “Optimization by Simulated Annealing,” Science, Vol. 220, No. 4598, 1983, pp. 671–680. doi: SCIEAS 0036-8075 Google Scholar

  • [23] Dreo J., Petrowski A., Siarry P. and Taillard E., Metaheuristics for Hard Optimization, Springer–Verlag, Berlin, 2006. Google Scholar