Metaheuristic Approach for Distributed Trajectory Planning for European Functional Airspace Blocks
Abstract
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.
References
[1] Manual on Collaborative Air Traffic Flow Management, 2nd ed., International Civil Aviation Organization, Document 9971 AN/485, Montreal, 2014.
[2] , “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:https://doi.org/10.1016/j.jairtraman.2013.06.012
[3] , “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.
[4] “Single European Sky Legislative Package,” Tech. Rept. 1070/2009, European Commission, Strasbourg, France, 2009.
[5] “Eurocontrol Functional Airspace Block,” http://www.eurocontrol.int/articles/functional-airspace-block-fab [accessed 20 June 2018].
[6] , “DFS on Central Flow Management Unit,” Skyway Magazine Eurocontrol, Vol. 9, No. 39, 2005, p. 23.
[7] “Performance Review Report, PRR 2008,” Tech. Rept., EUROCONTROL, Brussels, 2008.
[8] , “Managing European Air Traffic Control Provision,” Proceedings of the 4th SESAR Innovation Days, Nov. 2014, https://www.sesarju.eu/sites/default/les/documents/sid/2014/SID%202014-09.pdf.
[9] , “Optimisation of the Performance of the ATM Network in Europe,” Proceedings of the National Aviation University, Vol. 59, No. 2, 2014, pp. 37–43.
[10] , “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.
[11] , “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.
[12] , Adaptation in Natural and Artificial Systems: An Introductory Analysis with Applications to Biology, Control, and Artificial Intelligence, MIT Press, Cambridge, MA, 1992.
[13] , “Genetic Search Methods in Air Traffic Control,” Computers and Operations Research, Vol. 31, No. 3, 2004, pp. 445–459. doi:https://doi.org/10.1016/S0305-0548(02)00228-9
[14] , “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:https://doi.org/10.1109/CCA.1999.806209
[15] , “Identifying Vital Edges in Chinese Air Route Network via Memetic Algorithm,” Chinese Journal of Aeronautics, Vol. 30, No. 1, 2017, pp. 330–336. doi:https://doi.org/10.1016/j.cja.2016.12.001 CJAEEZ 1000-9361
[16] , “Genetic Algorithms for Air Traffic Control Systems,” Proceedings of the 14th Triennal Conference of the International Federation of Operational Research Societies, Vancouver, Canada, 1996.
[17] , “Large Scale 4D Trajectory Planning,” IEEE Computational Intelligence Magazine, Vol. 9, No. 4, 1989, pp. 46–61.
[18] , “Fairness in Air Traffic Flow Management,” INFORMS Meeting, Vol. 54, Catonsville, USA, 2009, p. 100.
[19] , “Demand and Capacity Management in Air Transportation,” EURO Journal on Transportation and Logistics, Vol. 1, Nos. 1–2, 2012, pp. 135–155. doi:https://doi.org/10.1007/s13676-012-0006-9
[20] , “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:https://doi.org/10.1016/j.trc.2011.11.013
[21] , “Predicting Ground Delay Program at an Airport Based on Meteorological Conditions,” 14th AIAA Aviation Technology, Integration, and Operations Conference, AIAA Paper 2014-2713, 2014.
[22] , “Optimization by Simulated Annealing,” Science, Vol. 220, No. 4598, 1983, pp. 671–680. doi:https://doi.org/10.1126/science.220.4598.671 SCIEAS 0036-8075
[23] , Metaheuristics for Hard Optimization, Springer–Verlag, Berlin, 2006.
