Research Article
BibTex RIS Cite

A Mixed-Integer Linear Programming Model for Conflict Resolution Using Airspace Discretization Technique in a Generic Free Route Airspace

Year 2024, Volume: 27 Issue: 4, 1427 - 1440, 25.09.2024

Zekeriya Kaplan , Cem Çetek , Tuğba Saraç

https://doi.org/10.2339/politeknik.1293137

Abstract

In this study, a mixed-integer linear programming (MILP) model is proposed to detect and resolve conflicts between aircraft in a generic free route airspace while minimizing the total flight distance. The proposed solution approach uses airspace partitioning technique to control safety separations and determine flight trajectories. However, defining too many nodes during the airspace partitioning phase allows for achieving high-quality solutions but also increases problem complexity and computation time. Therefore, the impact of the partitioning rate (number of nodes in the airspace) on the solution quality and time is investigated by partitioning the airspace into low, medium, and high node numbers. The experimental results indicate that a medium partitioning rate can achieve a significant improvement in solution quality within an acceptable computation time compared to a low rate, while a high partitioning rate results in a significant increase in computation time without providing an equivalent improvement in solution quality.

Keywords

Mixed-integer linear programming (MILP) Conflict resolution Free route airspace Airspace discretization Air traffic management

References

  • [1] Cecen R.K., Cetek C., “Conflict-free en-route operations with horizontal resolution manoeuvers using a heuristic algorithm”, Aeronautical Journal, 124(1275): 767-85, (2020).
  • [2] Cecen R.K., Cetek C., “A Two-Step Approach for Airborne Delay Minimization Using Pretactical Conflict Resolution in Free-Route Airspace”, J Adv Transp, (2019).
  • [3] Cecen R.K., Saraç T., Cetek C., “Meta-heuristic algorithm for aircraft pre-tactical conflict resolution with altitude and heading angle change maneuvers”, TOP, 29(3): 629-47, (2021).
  • [4] Pallottino L., Feron E.M., Bicchi A., “Conflict Resolution Problems for Air Traffic Management Systems Solved with Mixed Integer Programming”, IEEE Transactions on Intelligent Transportation Systems, 3(1): 3-11, (2002).
  • [5] Alonso-Ayuso A., Escudero L.F., Martín-Campo F.J., “Collision avoidance in air traffic management: A mixed-integer linear optimization approach”, IEEE Transactions on Intelligent Transportation Systems, 12(1): 47-57, (2011).
  • [6] Alonso-Ayuso A., Escudero L.F., Olaso P., Pizarro C., “Conflict avoidance: 0-1 linear models for conflict detection & resolution”, TOP. 21(3): 485-504, (2011).
  • [7] Alonso-Ayuso A., Escudero L.F., Martín-Campo F.J., “A mixed 0-1 nonlinear optimization model and algorithmic approach for the collision avoidance in ATM: Velocity changes through a time horizon”, Comput Oper Res, 39(12): 3136-46, (2012).
  • [8] Alonso-Ayuso A., Escudero L.F., Martín-Campo F.J., “Exact and approximate solving of the aircraft collision resolution problem via turn changes”, Transportation Science, 50(1): 263-74, (2014).
  • [9] Alonso-Ayuso A., Escudero L.F., Martín-Campo F.J., “Multiobjective optimization for aircraft conflict resolution. A metaheuristic approach”, Eur J Oper Res., 248(2): 691-702, (2016).
  • [10] Hong Y., Choi B., Oh G., Lee K., Kim Y., “Nonlinear Conflict Resolution and Flow Management Using Particle Swarm Optimization”, IEEE Transactions on Intelligent Transportation Systems, 18(12): 3378-87, (2017).
  • [11] Christodoulou M., Costoulakis C., “Nonlinear mixed integer programming for aircraft collision avoidance in free flight”, Proceedings of the Mediterranean Electrotechnical Conference – MELECON, Dubrovnik, 1: 327-30, (2004).
  • [12] Vela A., Solak S., Singhose W., Clarke J.P., “A mixed integer program for flight-level assignment and speed control for conflict resolution”, Proceedings of the IEEE Conference on Decision and Control, Shanghai, 5219-26, (2009).
  • [13] Vela A.E., Solak S, Clarke JP.B., Singhose W.E., Barnes E.R., Johnson E.L., “Near real-time fuel-optimal en route conflict resolution”, IEEE Transactions on Intelligent Transportation Systems, 11(4): 826-37, (2010).
  • [14] Cafieri S., Durand N., “Aircraft deconfliction with speed regulation: New models from mixed-integer optimization”, Journal of Global Optimization, 58(4): 613-29, (2014).
  • [15] Cafieri S., Rey D., “Maximizing the number of conflict-free aircraft using mixed-integer nonlinear programming”, Comput Oper Res., 80: 147-58, (2017).
  • [16] Cafieri S., Omheni R., “Mixed-integer nonlinear programming for aircraft conflict avoidance by sequentially applying velocity and heading angle changes”, Eur J Oper Res, 260(1): 283-90, (2017).
  • [17] Omer J., “A space-discretized mixed-integer linear model for air-conflict resolution with speed and heading maneuvers”, Comput Oper Res, 58: 75-86, (2015).
  • [18] Erzberger H., Heere K., “Algorithm and operational concept for resolving short-range conflicts”, Proc Inst Mech Eng G J Aerosp Eng, 224(2): 225-43, (2010).
  • [19] Kaplan Z., Çetek C., “Yapay Bağışıklık Metasezgiseli ile Tek Pistli Havaalanlarında İniş Sıralamasının Eniyilenmesi”, J ESOGU Engin Arch Fac, 28(3): 321-31, (2020).
  • [20] Gui D., Le M., Huang Z., Zhang J., D’Ariano A., “Optimal aircraft arrival scheduling with continuous descent operations in busy terminal maneuvering areas”, J Air Transp Manag, 107, (2023).
  • [21] Vadlamani S., Hosseini S., “A novel heuristic approach for solving aircraft landing problem with single runway”, J Air Transp Manag, 40: 144-8, (2014).
  • [22] Kwasiborska A., “Sequencing landing aircraft process to minimize schedule length”, Transportation Research Procedia. Elsevier B.V., 111-6, (2017).
  • [23] Lee H., Balakrishnan H., “A Study of Tradeoffs in Scheduling Terminal-Area Operations”, Proceedings of the IEEE, 96(12): 2081-95, (2008).
  • [24] Balakrishnan H., Chandran B., “Efficient and Equitable Departure Scheduling in Real-Time: New Approaches to Old Problems”, USA/Europe Air Traffic Management R&D Seminar, Barcelona, (2007).
  • [25] Rathinam S., Wood Z., Sridhar B., Jung Y., “A generalized dynamic programming approach for a departure scheduling problem”, AIAA Guidance, Navigation, and Control Conference, Chicago, (2009).
  • [26] Hancerliogullari G., Rabadi G., Al-Salem A.H., Kharbeche M., “Greedy algorithms and metaheuristics for a multiple runway combined arrival-departure aircraft sequencing problem”, J Air Transp Manag, 32: 39-48, (2013).
  • [27] Farhadi F., Ghoniem A., Al-Salem M., “Runway capacity management - An empirical study with application to Doha International Airport”, Transp Res E Logist Transp Rev, 68: 53-63, (2014).
  • [28] Murça M.C.R., Müller C., “Control-based optimization approach for aircraft scheduling in a terminal area with alternative arrival routes”, Transp Res E Logist Transp Rev, 73: 96-113, (2015).
  • [29] Samà M., D’Ariano A., Palagachev K., Gerdts M., “Integration methods for aircraft scheduling and trajectory optimization at a busy terminal manoeuvring area”, OR Spectrum, 41(3): 641-81, (2019).
  • [30] Samà M., D’Ariano A., D’Ariano P., Pacciarelli D., “Optimal aircraft scheduling and routing at a terminal control area during disturbances”, Transp Res Part C Emerg Technol, 47(P1): 61-85, (2014).
  • [31] Samà M., D’Ariano A., D’Ariano P., Pacciarelli D., “Air traffic optimization models for aircraft delay and travel time minimization in terminal control areas”, Public Transport, 7(3): 321-37, (2015).
  • [32] Kaplan Z., Çetek C., Saraç T., “A multi-objective nonlinear integer programming model for mixed runway operations within the TMAs”, The Aeronautical Journal, 1-31, (2023).
  • [33] Dönmez K., Çetek C., Kaya O., “Air traffic management in parallel-point merge systems under wind uncertainties”, J Air Transp Manag, 104, (2022).
  • [34] Dönmez K., Çetek C., Kaya O., “Aircraft Sequencing and Scheduling in Parallel-Point Merge Systems for Multiple Parallel Runways”, Transportation Research Record, 108-24, (2022).
  • [35] Liang M., Delahaye D., Maréchal P., “Integrated sequencing and merging aircraft to parallel runways with automated conflict resolution and advanced avionics capabilities”, Transp Res Part C Emerg Technol, 85: 268-91, (2017).
  • [36] Liang M., Delahaye D., Marechal P., “Conflict-free arrival and departure trajectory planning for parallel runway with advanced point-merge system”, Transp Res Part C Emerg Technol. 95: 207-27, (2018). [37] Cecen R.K., “Multi-objective TMA management optimization using the point merge system”, Aircraft Engineering and Aerospace Technology, 93(1): 15-24, (2021).
  • [38] Cecen R.K., Cetek C., Kaya O., “Aircraft sequencing and scheduling in TMAs under wind direction uncertainties”, The Aeronautical Journal, 124(1282): 1896-912, (2020).
  • [39] Çetek F.A., Kantar Y.M., Cavcar A., “A regression model for terminal airspace delays”, The Aeronautical Journal, 121(1239): 680-92, (2017).
  • [40] EUROCONTROL, “User Manual for the Base of Aircraft Data (BADA)”, France, (2013).

Jenerik Serbest Rotalı Hava Sahasında Kesikleştirme Tekniği Kullanılarak Çakışmaların Çözümlenme Problemi için Karma Tamsayılı Doğrusal Programlama Modeli

Year 2024, Volume: 27 Issue: 4, 1427 - 1440, 25.09.2024

Zekeriya Kaplan , Cem Çetek , Tuğba Saraç

https://doi.org/10.2339/politeknik.1293137

Abstract

Bu çalışmada, jenerik serbest rotalı hava sahasında, uçaklar arasındaki çakışmaları belirlemek ve çözmek amacıyla bir karma tamsayılı doğrusal programlama (MILP) modeli önerilmiştir. Model, toplam uçuş mesafesinin enküçüklenmesini hedeflemektedir. Önerilen çözüm yaklaşımında, hava sahası kesikleştirme tekniği kullanılarak emniyet ayırmaları kontrol edilmekte ve uçuş yörüngeleri belirlenmektedir. Hava sahasının kesikleştirilmesi aşamasında çok fazla düğüm tanımlanması, kaliteli çözümlere ulaşılması fırsatı yaratmasına rağmen problem karmaşıklığını ve dolayısıyla çözüm süresini de arttırmaktadır. Bu nedenle, çalışmada ilgili hava sahası düşük, orta ve yüksek düğüm sayıları içerecek şekilde kesikleştirilmiş ve kesikleştirme oranının (hava sahasının içerdiği düğüm sayısının) çözüm süresi ve kalitesine etkisi incelenmiştir. Elde edilen deneysel sonuçlar, orta kesikleştirme oranı kullanıldığında, düşüğe kıyasla ciddi bir çözüm kalitesi artışının, kabul edilebilir bir çözüm süresi içinde sağlanabildiğini ancak yüksek orana geçildiğinde önemli bir çözüm süresi artışına karşın aynı oranda çözüm kalitesi iyileşmesi sağlayamadığını ortaya koymuştur.

Keywords

Karma tamsayılı doğrusal programlama (MILP) Çakışma çözümleme Serbest rotalı hava sahası Hava sahası kesikleştirme Hava trafik yönetimi

References

  • [1] Cecen R.K., Cetek C., “Conflict-free en-route operations with horizontal resolution manoeuvers using a heuristic algorithm”, Aeronautical Journal, 124(1275): 767-85, (2020).
  • [2] Cecen R.K., Cetek C., “A Two-Step Approach for Airborne Delay Minimization Using Pretactical Conflict Resolution in Free-Route Airspace”, J Adv Transp, (2019).
  • [3] Cecen R.K., Saraç T., Cetek C., “Meta-heuristic algorithm for aircraft pre-tactical conflict resolution with altitude and heading angle change maneuvers”, TOP, 29(3): 629-47, (2021).
  • [4] Pallottino L., Feron E.M., Bicchi A., “Conflict Resolution Problems for Air Traffic Management Systems Solved with Mixed Integer Programming”, IEEE Transactions on Intelligent Transportation Systems, 3(1): 3-11, (2002).
  • [5] Alonso-Ayuso A., Escudero L.F., Martín-Campo F.J., “Collision avoidance in air traffic management: A mixed-integer linear optimization approach”, IEEE Transactions on Intelligent Transportation Systems, 12(1): 47-57, (2011).
  • [6] Alonso-Ayuso A., Escudero L.F., Olaso P., Pizarro C., “Conflict avoidance: 0-1 linear models for conflict detection & resolution”, TOP. 21(3): 485-504, (2011).
  • [7] Alonso-Ayuso A., Escudero L.F., Martín-Campo F.J., “A mixed 0-1 nonlinear optimization model and algorithmic approach for the collision avoidance in ATM: Velocity changes through a time horizon”, Comput Oper Res, 39(12): 3136-46, (2012).
  • [8] Alonso-Ayuso A., Escudero L.F., Martín-Campo F.J., “Exact and approximate solving of the aircraft collision resolution problem via turn changes”, Transportation Science, 50(1): 263-74, (2014).
  • [9] Alonso-Ayuso A., Escudero L.F., Martín-Campo F.J., “Multiobjective optimization for aircraft conflict resolution. A metaheuristic approach”, Eur J Oper Res., 248(2): 691-702, (2016).
  • [10] Hong Y., Choi B., Oh G., Lee K., Kim Y., “Nonlinear Conflict Resolution and Flow Management Using Particle Swarm Optimization”, IEEE Transactions on Intelligent Transportation Systems, 18(12): 3378-87, (2017).
  • [11] Christodoulou M., Costoulakis C., “Nonlinear mixed integer programming for aircraft collision avoidance in free flight”, Proceedings of the Mediterranean Electrotechnical Conference – MELECON, Dubrovnik, 1: 327-30, (2004).
  • [12] Vela A., Solak S., Singhose W., Clarke J.P., “A mixed integer program for flight-level assignment and speed control for conflict resolution”, Proceedings of the IEEE Conference on Decision and Control, Shanghai, 5219-26, (2009).
  • [13] Vela A.E., Solak S, Clarke JP.B., Singhose W.E., Barnes E.R., Johnson E.L., “Near real-time fuel-optimal en route conflict resolution”, IEEE Transactions on Intelligent Transportation Systems, 11(4): 826-37, (2010).
  • [14] Cafieri S., Durand N., “Aircraft deconfliction with speed regulation: New models from mixed-integer optimization”, Journal of Global Optimization, 58(4): 613-29, (2014).
  • [15] Cafieri S., Rey D., “Maximizing the number of conflict-free aircraft using mixed-integer nonlinear programming”, Comput Oper Res., 80: 147-58, (2017).
  • [16] Cafieri S., Omheni R., “Mixed-integer nonlinear programming for aircraft conflict avoidance by sequentially applying velocity and heading angle changes”, Eur J Oper Res, 260(1): 283-90, (2017).
  • [17] Omer J., “A space-discretized mixed-integer linear model for air-conflict resolution with speed and heading maneuvers”, Comput Oper Res, 58: 75-86, (2015).
  • [18] Erzberger H., Heere K., “Algorithm and operational concept for resolving short-range conflicts”, Proc Inst Mech Eng G J Aerosp Eng, 224(2): 225-43, (2010).
  • [19] Kaplan Z., Çetek C., “Yapay Bağışıklık Metasezgiseli ile Tek Pistli Havaalanlarında İniş Sıralamasının Eniyilenmesi”, J ESOGU Engin Arch Fac, 28(3): 321-31, (2020).
  • [20] Gui D., Le M., Huang Z., Zhang J., D’Ariano A., “Optimal aircraft arrival scheduling with continuous descent operations in busy terminal maneuvering areas”, J Air Transp Manag, 107, (2023).
  • [21] Vadlamani S., Hosseini S., “A novel heuristic approach for solving aircraft landing problem with single runway”, J Air Transp Manag, 40: 144-8, (2014).
  • [22] Kwasiborska A., “Sequencing landing aircraft process to minimize schedule length”, Transportation Research Procedia. Elsevier B.V., 111-6, (2017).
  • [23] Lee H., Balakrishnan H., “A Study of Tradeoffs in Scheduling Terminal-Area Operations”, Proceedings of the IEEE, 96(12): 2081-95, (2008).
  • [24] Balakrishnan H., Chandran B., “Efficient and Equitable Departure Scheduling in Real-Time: New Approaches to Old Problems”, USA/Europe Air Traffic Management R&D Seminar, Barcelona, (2007).
  • [25] Rathinam S., Wood Z., Sridhar B., Jung Y., “A generalized dynamic programming approach for a departure scheduling problem”, AIAA Guidance, Navigation, and Control Conference, Chicago, (2009).
  • [26] Hancerliogullari G., Rabadi G., Al-Salem A.H., Kharbeche M., “Greedy algorithms and metaheuristics for a multiple runway combined arrival-departure aircraft sequencing problem”, J Air Transp Manag, 32: 39-48, (2013).
  • [27] Farhadi F., Ghoniem A., Al-Salem M., “Runway capacity management - An empirical study with application to Doha International Airport”, Transp Res E Logist Transp Rev, 68: 53-63, (2014).
  • [28] Murça M.C.R., Müller C., “Control-based optimization approach for aircraft scheduling in a terminal area with alternative arrival routes”, Transp Res E Logist Transp Rev, 73: 96-113, (2015).
  • [29] Samà M., D’Ariano A., Palagachev K., Gerdts M., “Integration methods for aircraft scheduling and trajectory optimization at a busy terminal manoeuvring area”, OR Spectrum, 41(3): 641-81, (2019).
  • [30] Samà M., D’Ariano A., D’Ariano P., Pacciarelli D., “Optimal aircraft scheduling and routing at a terminal control area during disturbances”, Transp Res Part C Emerg Technol, 47(P1): 61-85, (2014).
  • [31] Samà M., D’Ariano A., D’Ariano P., Pacciarelli D., “Air traffic optimization models for aircraft delay and travel time minimization in terminal control areas”, Public Transport, 7(3): 321-37, (2015).
  • [32] Kaplan Z., Çetek C., Saraç T., “A multi-objective nonlinear integer programming model for mixed runway operations within the TMAs”, The Aeronautical Journal, 1-31, (2023).
  • [33] Dönmez K., Çetek C., Kaya O., “Air traffic management in parallel-point merge systems under wind uncertainties”, J Air Transp Manag, 104, (2022).
  • [34] Dönmez K., Çetek C., Kaya O., “Aircraft Sequencing and Scheduling in Parallel-Point Merge Systems for Multiple Parallel Runways”, Transportation Research Record, 108-24, (2022).
  • [35] Liang M., Delahaye D., Maréchal P., “Integrated sequencing and merging aircraft to parallel runways with automated conflict resolution and advanced avionics capabilities”, Transp Res Part C Emerg Technol, 85: 268-91, (2017).
  • [36] Liang M., Delahaye D., Marechal P., “Conflict-free arrival and departure trajectory planning for parallel runway with advanced point-merge system”, Transp Res Part C Emerg Technol. 95: 207-27, (2018). [37] Cecen R.K., “Multi-objective TMA management optimization using the point merge system”, Aircraft Engineering and Aerospace Technology, 93(1): 15-24, (2021).
  • [38] Cecen R.K., Cetek C., Kaya O., “Aircraft sequencing and scheduling in TMAs under wind direction uncertainties”, The Aeronautical Journal, 124(1282): 1896-912, (2020).
  • [39] Çetek F.A., Kantar Y.M., Cavcar A., “A regression model for terminal airspace delays”, The Aeronautical Journal, 121(1239): 680-92, (2017).
  • [40] EUROCONTROL, “User Manual for the Base of Aircraft Data (BADA)”, France, (2013).
There are 39 citations in total.

Details

Primary Language Turkish
Subjects Engineering
Journal Section Research Article
Authors

Zekeriya Kaplan 0000-0001-8555-4579

Cem Çetek 0000-0002-2162-511X

Tuğba Saraç 0000-0002-8115-3206

Early Pub Date September 3, 2023
Publication Date September 25, 2024
Submission Date May 5, 2023
Published in Issue Year 2024 Volume: 27 Issue: 4

Cite

APA Kaplan, Z., Çetek, C., & Saraç, T. (2024). Jenerik Serbest Rotalı Hava Sahasında Kesikleştirme Tekniği Kullanılarak Çakışmaların Çözümlenme Problemi için Karma Tamsayılı Doğrusal Programlama Modeli. Politeknik Dergisi, 27(4), 1427-1440. https://doi.org/10.2339/politeknik.1293137
AMA Kaplan Z, Çetek C, Saraç T. Jenerik Serbest Rotalı Hava Sahasında Kesikleştirme Tekniği Kullanılarak Çakışmaların Çözümlenme Problemi için Karma Tamsayılı Doğrusal Programlama Modeli. Politeknik Dergisi. September 2024;27(4):1427-1440. doi:10.2339/politeknik.1293137
Chicago Kaplan, Zekeriya, Cem Çetek, and Tuğba Saraç. “Jenerik Serbest Rotalı Hava Sahasında Kesikleştirme Tekniği Kullanılarak Çakışmaların Çözümlenme Problemi için Karma Tamsayılı Doğrusal Programlama Modeli”. Politeknik Dergisi 27, no. 4 (September 2024): 1427-40. https://doi.org/10.2339/politeknik.1293137.
EndNote Kaplan Z, Çetek C, Saraç T (September 1, 2024) Jenerik Serbest Rotalı Hava Sahasında Kesikleştirme Tekniği Kullanılarak Çakışmaların Çözümlenme Problemi için Karma Tamsayılı Doğrusal Programlama Modeli. Politeknik Dergisi 27 4 1427–1440.
IEEE Z. Kaplan, C. Çetek, and T. Saraç, “Jenerik Serbest Rotalı Hava Sahasında Kesikleştirme Tekniği Kullanılarak Çakışmaların Çözümlenme Problemi için Karma Tamsayılı Doğrusal Programlama Modeli”, Politeknik Dergisi, vol. 27, no. 4, pp. 1427–1440, 2024, doi: 10.2339/politeknik.1293137.
ISNAD Kaplan, Zekeriya et al. “Jenerik Serbest Rotalı Hava Sahasında Kesikleştirme Tekniği Kullanılarak Çakışmaların Çözümlenme Problemi için Karma Tamsayılı Doğrusal Programlama Modeli”. Politeknik Dergisi 27/4 (September 2024), 1427-1440. https://doi.org/10.2339/politeknik.1293137.
JAMA Kaplan Z, Çetek C, Saraç T. Jenerik Serbest Rotalı Hava Sahasında Kesikleştirme Tekniği Kullanılarak Çakışmaların Çözümlenme Problemi için Karma Tamsayılı Doğrusal Programlama Modeli. Politeknik Dergisi. 2024;27:1427–1440.
MLA Kaplan, Zekeriya et al. “Jenerik Serbest Rotalı Hava Sahasında Kesikleştirme Tekniği Kullanılarak Çakışmaların Çözümlenme Problemi için Karma Tamsayılı Doğrusal Programlama Modeli”. Politeknik Dergisi, vol. 27, no. 4, 2024, pp. 1427-40, doi:10.2339/politeknik.1293137.
Vancouver Kaplan Z, Çetek C, Saraç T. Jenerik Serbest Rotalı Hava Sahasında Kesikleştirme Tekniği Kullanılarak Çakışmaların Çözümlenme Problemi için Karma Tamsayılı Doğrusal Programlama Modeli. Politeknik Dergisi. 2024;27(4):1427-40.

 download This work is licensed under Creative Commons Attribution-ShareAlike 4.0 International.