Hybrid Approach for Minimizing Departure Air Traffic Delays Following Standard Instrument Departures
Keywords:
Air traffic management, Standard instrument departure, Departure traffic sequencing, Genetic algorithm, Heuristic algorithm
Abstract
The efficient scheduling of departure air traffic persists as one of the most challenging aspects of air traffic management in recent years. A proper sequencing enhances airport operations, minimises delay, and improves airspace capacity and traffic forecasting. This paper proposes a sequential hybridisation algorithm designed to assist air traffic controllers in determining the optimal departure sequence complying with the standard instrument departures (SIDs). The level of complexity increases when taking into account the departure runway constraints, the configuration of flight paths after takeoff, and the aircraft's operational limits during the takeoff phase. Another challenging aspect is the wide diversity in aircraft types. The suggested approach proposes a Genetic algorithm (GA) strengthened with the Partially Mixed Crossover technique (PMX). The initial population of the GA is enhanced with the Shortest Job First (SJF) method. This sequential hybridisation algorithm dynamically arranges the departure traffic sequence based on their performances and the complexity of the followed SIDs.References
1. ICAO, Newsroom, https://www.icao.int/Newsroom/Pages/ICAO-forecasts-complete-and-sustainable-recovery-and-growth-of-air- passenger-demand-in-2023.aspx.
2. I. Anagnostakis, H. R. Idris, J. P. Clarke, Feron, E. Feron, R. J. Hansman, A. R. Odoni, and W. D. Hall, A conceptual design of a departure planner decision aid, 2000.
3. C. Brinton, J. Krozel, B. Capozzi, and S. Atkins, Improved taxi prediction algorithms for the surface management system, AIAA Guidance, Navigation, and Control Conference and Exhibit, pp. 4857, 2002.
4. I. Anagnostakis, J. P. Clarke, D. Bohme, and U. Volckers, Runway operations planning and control sequencing and scheduling, IEEE, Proceedings of the 34th Annual Hawaii International Conference on System Sciences, pp. 12–pp, 2001.
5. P. Scala, M. M. Mota, J. Ma, and D. Delahaye, Tackling uncertainty for the development of efficient decision support system in air traffic management, IEEE Transactions on Intelligent Transportation Systems, vol. 21, no. 8, pp. 3233–3246, 2019.
6. G. Gupta, W. Malik, and Y. Jung, A mixed integer linear program for airport departure scheduling, 9th AIAA Aviation Technology, Integration, and Operations Conference (ATIO). AIAA, Hilton Head, South Carolina, 2009.
7. F. Furini, M. P. Kidd, C.A. Persiani, and P. Toth, Improved rolling horizon approaches to the aircraft sequencing problem, Springer, Journal of Scheduling, vol. 18, pp. 435–447, 2015.
8. H. S. J. Tsao, W. Wei, A. Pratama, and J. R. Tsao, Integrated Taxiing and Take-Off Scheduling for Optimization of Airport Surface Operations, Proc. 2nd Annual Conference of Indian Subcontinent Decision Science Institute (ISDSI 2009), pp. 3–5, 2009.
9. G. Clare, and A. G. Richards, Optimization of taxiway routing and runway scheduling, IEEE Transactions on Intelligent Transportation Systems, vol. 12, no. 4, pp. 1000–1013, 2011.
10. M. C. R. Murc ̧a, A robust optimization approach for airport departure metering under uncertain taxi-out time predictions, Elsevier, Aerospace science and technology, vol. 68, pp. 269–277, 2017.
11. V. F. Ribeiro, L. Weigang, V. Milea, Y. Yamashita, and L. Uden, Collaborative decision making in departure sequencing with an adapted Rubinstein protocol, IEEE Transactions on Systems, Man, and Cybernetics: Systems, vol. 46, no. 2, pp. 248–259, 2015.
12. H. Balakrishnan, and B. Chandran, Efficient and equitable departure scheduling in real-time: new approaches to old problems, 7th USA-Europe Air Traffic Management Research and Development Seminar, pp. 02–05, 2007.
13. A. Sadiq, F. Ahmad, S. A. Khan, J. C. Valverde, T. Naz, and M. W. Anwar, Modeling and analysis of departure routine in air traffic control based on Petri nets, Neural Computing and Applications, vol. 25, pp. 1099-1109, 2014.
14. R. Shone, K. Glazebrook, and K. G. Zografos, Applications of stochastic modeling in air traffic management: Methods, challenges, and opportunities for solving air traffic problems under uncertainty, Elsevier, European Journal of Operational Research, vol. 292, no. 1, pp. 1–26, 2021.
15. W. Malik, G. Gupta, and Y. Jung, Managing departure aircraft release for efficient airport surface operations, AIAA Guidance, Navigation, and Control Conference, pp. 7696, 2010.
16. E. Itoh, M. Mitici, and M. Schultz, Modeling aircraft departure at a runway using a time-varying fluid queue, MDPI Aerospace, vol. 9, no. 3, pp. 119, 2022.
17. E. Chevalley, B. Parke, J. Kraut, N. Bienert, F. Omar, and E. Palmer, Scheduling and Delivering Aircraft to Departure Fixes in the NY Metroplex with Controller-Managed Spacing Tools, 15th AIAA Aviation Technology, Integration, and Operations Conference, pp. 2428, 2015.
18. R. H. Mayer, and D. J. Zondervan, Concept and benefits of a unified departure operation spacing standard, IEEE/AIAA 31st Digital Avionics Systems Conference (DASC), pp. 4A6–1, 2012.
19. H. F. Fernandes, and C. Mu ̈ller, Optimization of the waiting time and makespan in aircraft departures: A real-time non-iterative sequencing model, Elsevier, Journal of air transport management, vol. 79, pp. 101686, 2019.
20. ICAO, the Procedures for Air Navigation Services (PANS) - Air Traffic Management (Doc 4444), https://store.icao.int/en/procedures- for-air-navigation-services-air-traffic-management-doc-4444, 2022.
21. O. Idrissi, A. Bikir, and K. Mansouri, Efficient Management of Aircraft Taxiing Phase by Adjusting Speed Through Conflict-free Routes, Statistics, Optimization & Information Computing, vol. 10, no. 1, pp. 12–24, 2022.
22. A. Bikir, O. Idrissi, and K. Mansouri, Enhancing the Management of Traffic Sequence Following Departure Trajectories, Springer, Geospatial Intelligence: Applications and Future Trends, pp. 41–49, 2022.
23. A. Kwasiborska, and A. Stelmach, Pre-departure sequencing method in the terms of the dynamic growth of airports, Journal of KONES, vol. 23, no. 4, pp. 253–260, 2016.
24. J. Zhou, S. Cafieri, D. Delahaye, and M. Sbihi, Optimization of arrival and departure routes in terminal maneuvering area, ICRAT 2014, 6th International Conference on Research in Air Transportation, pp. pp–xxxx, 2014.
25. D. Kjenstad, C. Mannino, P. Schittekat, and M. Smedsrud, Integrated surface and departure management at airports by optimization, IEEE, 2013 5th International Conference on Modeling, Simulation and Applied Optimization (ICMSAO), pp. 1–5, 2013.
26. F. Ali, L. Xiujuan, and X. Xiao, The aircraft departure scheduling based on particle swarm optimization combined with simulated annealing algorithm, 2008 IEEE Congress on Evolutionary Computation (IEEE World Congress on Computational Intelligence), pp. 1393–1398, 2008.
27. X. B. Hu, and E. Di Paolo, An efficient genetic algorithm with uniform crossover for air traffic control, Elsevier, Computers & Operations Research, vol. 36, no. 1, pp. 245–259, 2009.
28. M. Bolender, and G. Slater, Analysis and optimization of departure sequences, AIAA Guidance, Navigation, and Control Conference and Exhibit, pp. 4475, 2000.
29. S. Capri, and M. Ignaccolo, Genetic algorithms for solving the aircraft-sequencing problem: the introduction of departures into the dynamic model, Elsevier, Journal of Air Transport Management, vol. 10, no. 5, pp. 345–351, 2004.
30. L. J. Wang, D. W. Hu, and R. Z. Gong, Improved genetic algorithm for aircraft departure sequencing problem, IEEE, In 2009 Third International Conference on Genetic and Evolutionary Computing, pp. 35–38, 2009.
2. I. Anagnostakis, H. R. Idris, J. P. Clarke, Feron, E. Feron, R. J. Hansman, A. R. Odoni, and W. D. Hall, A conceptual design of a departure planner decision aid, 2000.
3. C. Brinton, J. Krozel, B. Capozzi, and S. Atkins, Improved taxi prediction algorithms for the surface management system, AIAA Guidance, Navigation, and Control Conference and Exhibit, pp. 4857, 2002.
4. I. Anagnostakis, J. P. Clarke, D. Bohme, and U. Volckers, Runway operations planning and control sequencing and scheduling, IEEE, Proceedings of the 34th Annual Hawaii International Conference on System Sciences, pp. 12–pp, 2001.
5. P. Scala, M. M. Mota, J. Ma, and D. Delahaye, Tackling uncertainty for the development of efficient decision support system in air traffic management, IEEE Transactions on Intelligent Transportation Systems, vol. 21, no. 8, pp. 3233–3246, 2019.
6. G. Gupta, W. Malik, and Y. Jung, A mixed integer linear program for airport departure scheduling, 9th AIAA Aviation Technology, Integration, and Operations Conference (ATIO). AIAA, Hilton Head, South Carolina, 2009.
7. F. Furini, M. P. Kidd, C.A. Persiani, and P. Toth, Improved rolling horizon approaches to the aircraft sequencing problem, Springer, Journal of Scheduling, vol. 18, pp. 435–447, 2015.
8. H. S. J. Tsao, W. Wei, A. Pratama, and J. R. Tsao, Integrated Taxiing and Take-Off Scheduling for Optimization of Airport Surface Operations, Proc. 2nd Annual Conference of Indian Subcontinent Decision Science Institute (ISDSI 2009), pp. 3–5, 2009.
9. G. Clare, and A. G. Richards, Optimization of taxiway routing and runway scheduling, IEEE Transactions on Intelligent Transportation Systems, vol. 12, no. 4, pp. 1000–1013, 2011.
10. M. C. R. Murc ̧a, A robust optimization approach for airport departure metering under uncertain taxi-out time predictions, Elsevier, Aerospace science and technology, vol. 68, pp. 269–277, 2017.
11. V. F. Ribeiro, L. Weigang, V. Milea, Y. Yamashita, and L. Uden, Collaborative decision making in departure sequencing with an adapted Rubinstein protocol, IEEE Transactions on Systems, Man, and Cybernetics: Systems, vol. 46, no. 2, pp. 248–259, 2015.
12. H. Balakrishnan, and B. Chandran, Efficient and equitable departure scheduling in real-time: new approaches to old problems, 7th USA-Europe Air Traffic Management Research and Development Seminar, pp. 02–05, 2007.
13. A. Sadiq, F. Ahmad, S. A. Khan, J. C. Valverde, T. Naz, and M. W. Anwar, Modeling and analysis of departure routine in air traffic control based on Petri nets, Neural Computing and Applications, vol. 25, pp. 1099-1109, 2014.
14. R. Shone, K. Glazebrook, and K. G. Zografos, Applications of stochastic modeling in air traffic management: Methods, challenges, and opportunities for solving air traffic problems under uncertainty, Elsevier, European Journal of Operational Research, vol. 292, no. 1, pp. 1–26, 2021.
15. W. Malik, G. Gupta, and Y. Jung, Managing departure aircraft release for efficient airport surface operations, AIAA Guidance, Navigation, and Control Conference, pp. 7696, 2010.
16. E. Itoh, M. Mitici, and M. Schultz, Modeling aircraft departure at a runway using a time-varying fluid queue, MDPI Aerospace, vol. 9, no. 3, pp. 119, 2022.
17. E. Chevalley, B. Parke, J. Kraut, N. Bienert, F. Omar, and E. Palmer, Scheduling and Delivering Aircraft to Departure Fixes in the NY Metroplex with Controller-Managed Spacing Tools, 15th AIAA Aviation Technology, Integration, and Operations Conference, pp. 2428, 2015.
18. R. H. Mayer, and D. J. Zondervan, Concept and benefits of a unified departure operation spacing standard, IEEE/AIAA 31st Digital Avionics Systems Conference (DASC), pp. 4A6–1, 2012.
19. H. F. Fernandes, and C. Mu ̈ller, Optimization of the waiting time and makespan in aircraft departures: A real-time non-iterative sequencing model, Elsevier, Journal of air transport management, vol. 79, pp. 101686, 2019.
20. ICAO, the Procedures for Air Navigation Services (PANS) - Air Traffic Management (Doc 4444), https://store.icao.int/en/procedures- for-air-navigation-services-air-traffic-management-doc-4444, 2022.
21. O. Idrissi, A. Bikir, and K. Mansouri, Efficient Management of Aircraft Taxiing Phase by Adjusting Speed Through Conflict-free Routes, Statistics, Optimization & Information Computing, vol. 10, no. 1, pp. 12–24, 2022.
22. A. Bikir, O. Idrissi, and K. Mansouri, Enhancing the Management of Traffic Sequence Following Departure Trajectories, Springer, Geospatial Intelligence: Applications and Future Trends, pp. 41–49, 2022.
23. A. Kwasiborska, and A. Stelmach, Pre-departure sequencing method in the terms of the dynamic growth of airports, Journal of KONES, vol. 23, no. 4, pp. 253–260, 2016.
24. J. Zhou, S. Cafieri, D. Delahaye, and M. Sbihi, Optimization of arrival and departure routes in terminal maneuvering area, ICRAT 2014, 6th International Conference on Research in Air Transportation, pp. pp–xxxx, 2014.
25. D. Kjenstad, C. Mannino, P. Schittekat, and M. Smedsrud, Integrated surface and departure management at airports by optimization, IEEE, 2013 5th International Conference on Modeling, Simulation and Applied Optimization (ICMSAO), pp. 1–5, 2013.
26. F. Ali, L. Xiujuan, and X. Xiao, The aircraft departure scheduling based on particle swarm optimization combined with simulated annealing algorithm, 2008 IEEE Congress on Evolutionary Computation (IEEE World Congress on Computational Intelligence), pp. 1393–1398, 2008.
27. X. B. Hu, and E. Di Paolo, An efficient genetic algorithm with uniform crossover for air traffic control, Elsevier, Computers & Operations Research, vol. 36, no. 1, pp. 245–259, 2009.
28. M. Bolender, and G. Slater, Analysis and optimization of departure sequences, AIAA Guidance, Navigation, and Control Conference and Exhibit, pp. 4475, 2000.
29. S. Capri, and M. Ignaccolo, Genetic algorithms for solving the aircraft-sequencing problem: the introduction of departures into the dynamic model, Elsevier, Journal of Air Transport Management, vol. 10, no. 5, pp. 345–351, 2004.
30. L. J. Wang, D. W. Hu, and R. Z. Gong, Improved genetic algorithm for aircraft departure sequencing problem, IEEE, In 2009 Third International Conference on Genetic and Evolutionary Computing, pp. 35–38, 2009.
Published
2024-08-24
How to Cite
BIKIR, A., Idrissi, O., Mansouri, K., & Qbadou, M. (2024). Hybrid Approach for Minimizing Departure Air Traffic Delays Following Standard Instrument Departures. Statistics, Optimization & Information Computing. https://doi.org/10.19139/soic-2310-5070-1861
Issue
Section
Research Articles
Authors who publish with this journal agree to the following terms:
- Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
- Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
- Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (See The Effect of Open Access).
