Document Type : Research Paper

Authors

1 Department of Industrial Engineering, Central Tehran Branch, Islamic Azad University, Tehran, Iran.

2 Department of Mathematics, Rasht Branch, Islamic Azad University, Gilan, Iran.

3 Department of Basic Sciences, Central Tehran Branch, Islamic Azad University, Tehran, Iran

Abstract

The Aircraft Scheduling Problem (ASP) refers to allocating each aircraft to the optimal take-off and landing time and the appropriate runway. This problem is the allocation of aircraft to the desired runway so that the total damage due to delays or haste in landing or take-off of all aircraft is minimized. Runway allocation, landing and take-off sequences, and scheduling for each aircraft must be done in a predetermined time window. Time should also be considered as the time of separation between landings and take-offs due to the wake vortex phenomenon. In general, the purpose of such problems is to make maximum use of the runway. Therefore, in this study, a mathematical model of robust landing and take-off scheduling at an airport is provided, assuming no access to the airport runway at certain times. Moreover, delays and haste in landing and take-off on the runway, limited access to aircraft, runway repair time, and the possibility of runway disturbances are investigated. Robust optimization is used to deal with uncertainty at take-off and landing times. Finally, Genetic and Imperialistic Competitive Algorithm are used to evaluate and analyze the problem because it is NP-HARD problem. The results indicate the ability of the proposed algorithms to find high-quality solutions in a short computation time for problems up to 7 runways and 60 aircraft.

Keywords

Main Subjects

  • Zeng, Y., Che, A., & Wu, X. (2018). Bi-objective scheduling on uniform parallel machines considering electricity cost. Engineering optimization, 50(1), 19-36.
  • Ng, K. K. H., Lee, C. K., Chan, F. T., Chen, C. H., & Qin, Y. (2020). A two-stage robust optimisation for terminal traffic flow problem. Applied soft computing, 89, 106048. https://doi.org/10.1016/j.asoc.2019.106048
  • Lambelho, M., Mitici, M., Pickup, S., & Marsden, A. (2020). Assessing strategic flight schedules at an airport using machine learning-based flight delay and cancellation predictions. Journal of air transport management, 82, 101737. https://doi.org/10.1016/j.jairtraman.2019.101737
  • Zhang, J., Zhao, P., Zhang, Y., Dai, X., & Sui, D. (2020). Criteria selection and multi-objective optimization of aircraft landing problem. Journal of air transport management, 82, 101734. https://doi.org/10.1016/j.jairtraman.2019.101734
  • Yang, S., Yan, Y., & Chen, P. (2021). Robust optimization models for flight rerouting. International journal of computational methods, 18(05), 2040001. https://doi.org/10.1142/S0219876220400010
  • Shakibayifar, M., Sheikholeslami, A., Corman, F., & Hassannayebi, E. (2020). An integrated rescheduling model for minimizing train delays in the case of line blockage. Operational research, 20, 59-87.
  • Çiftçi, M. E., & Özkır, V. (2020). Optimising flight connection times in airline bank structure through Simulated Annealing and Tabu Search algorithms. Journal of air transport management, 87, 101858. https://doi.org/10.1016/j.jairtraman.2020.101858
  • Sama, M., D’Ariano, A., Palagachev, K., & Gerdts, M. (2019). Integration methods for aircraft scheduling and trajectory optimization at a busy terminal manoeuvring area. Or spectrum, 41, 641-681.
  • Esmaeilidouki, A., Mahzouni-Sani, M., Nikhalat Jahromi, A., & Jolai, F. (2021). A novel fuzzy bi-objective vehicle routing and scheduling problem with time window constraint for a distribution system: a case study. Scientia Iranica, 28(5), 2868-2889.
  • Salehipour, A., Modarres, M., & Naeni, L. M. (2013). An efficient hybrid meta-heuristic for aircraft landing problem. Computers & operations research, 40(1), 207-213.
  • Zhou, Q., Zhang, Y., Li, Z., Li, J., Xu, H., & Olatunbosun, O. (2017). Cyber-physical energy-saving control for hybrid aircraft-towing tractor based on online swarm intelligent programming. IEEE transactions on industrial informatics, 14(9), 4149-4158.
  • Arkind, K. (2004). Requirements for a novel terminal area capacity enhancement concept in 2022. AIAA guidance, navigation, and control conference and exhibit (p. 5411), Providence, Rhode Island. https://doi.org/10.2514/6.2004-5411
  • Idris, H., Delcaire, B., Anagnostakis, I., Hall, W., Pujet, N., Feron, E., Hansman R., Clarke J. P., & Odoni, A. (1998). Identification of flow constraint and control points in departure operations at airport systems. Guidance, navigation, and control conference and exhibit (p. 4291), Boston, MA, U.S.A. https://doi.org/10.2514/6.1998-4291
  • Sinha, D. (2019). Deregulation and liberalisation of the airline industry: Asia, Europe, North America and Oceania. Routledge.
  • Sama, M., D’Ariano, A., Corman, F., & Pacciarelli, D. (2017). Metaheuristics for efficient aircraft scheduling and re-routing at busy terminal control areas. Transportation research part C: emerging technologies, 80, 485-511.
  • Fernandes, H. F., & Müller, C. (2019). Optimization of the waiting time and makespan in aircraft departures: A real time non-iterative sequencing model. Journal of air transport management, 79, 101686. https://doi.org/10.1016/j.jairtraman.2019.101686
  • Lieder, A., & Stolletz, R. (2016). Scheduling aircraft take-offs and landings on interdependent and heterogeneous runways. Transportation research part E: logistics and transportation review, 88, 167-188.
  • Lee, S., Hong, Y., & Kim, Y. (2020). Optimal scheduling algorithm in point merge system including holding pattern based on mixed-integer linear programming. Proceedings of the institution of mechanical engineers, part G: journal of aerospace engineering, 234(10), 1638-1647.
  • Allahverdi, A., Ng, C. T., Cheng, T. E., & Kovalyov, M. Y. (2008). A survey of scheduling problems with setup times or costs. European journal of operational research, 187(3), 985-1032.
  • Ball, M., Barnhart, C., Nemhauser, G., & Odoni, A. (2007). Air transportation: irregular operations and control. Handbooks in operations research and management science, 14, 1-67.
  • Zhan, Z. H., Zhang, J., Li, Y., Liu, O., Kwok, S. K., Ip, W. H., & Kaynak, O. (2010). An efficient ant colony system based on receding horizon control for the aircraft arrival sequencing and scheduling problem. IEEE transactions on intelligent transportation systems11(2), 399-412.
  • Khaksar, H., & Sheikholeslami, A. (2019). Airline delay prediction by machine learning algorithms. Scientia Iranica, 26(5), 2689-2702.
  • Beasley, J. E., Krishnamoorthy, M., Sharaiha, Y. M., & Abramson, D. (2004). Displacement problem and dynamically scheduling aircraft landings. Journal of the operational research society, 55(1), 54-64.
  • Bennell, J. A., Mesgarpour, M., & Potts, C. N. (2013). Airport runway scheduling. Annals of operations research, 204, 249-270.
  • Hu, XB., Di Paolo, E. (2009). An efficient genetic algorithm with uniform crossover for the multi-objective airport gate assignment problem. In multi-objective memetic algorithms (pp. 71-89). Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-88051-6_4
  • Bennell, J. A., Mesgarpour, M., & Potts, C. N. (2017). Dynamic scheduling of aircraft landings. European journal of operational research, 258(1), 315-327.
  • Kenan, N., Jebali, A., & Diabat, A. (2018). An integrated flight scheduling and fleet assignment problem under uncertainty. Computers & operations research, 100, 333-342.
  • Cheng, C. B., Shyur, H. J., & Kuo, Y. S. (2014). Implementation of a flight operations risk assessment system and identification of critical risk factors. Scientia Iranica, 21(6), 2387-2398.
  • Kim, S., Suh, W., & Kim, J. (2015). Forecasting hourly traffic volume: Incheon international airport access road. Scientia Iranica, 22(4), 1510-1516.
  • Tavakkoli Moghaddam, R., Yaghoubi-Panah, M., & Radmehr, F. (2012). Scheduling the sequence of aircraft landings for a single runway using a fuzzy programming approach. Journal of air transport management, 25, 15-18.
  • Rashidi Komijan, A., Tavakkoli-Moghaddam, R., & Dalil, S. A. (2021). A mathematical model for an integrated airline fleet assignment and crew scheduling problem solved by vibration damping optimization. Scientia Iranica, 28(2), 970-984.
  • Hassanpour, A., Bagherinejad, J., & Bashiri, M. (2019). A robust bi-level programming model for designing a closed-loop supply chain considering government's collection policy. Scientia Iranica, 26(6), 3747-3764.
  • Ben-Tal, A., & Nemirovski, A. (1999). Robust solutions of uncertain linear programs. Operations research letters, 25(1), 1-13.