Hostname: page-component-cd9895bd7-dk4vv Total loading time: 0 Render date: 2024-12-27T13:28:00.579Z Has data issue: false hasContentIssue false
  • English
  • Français

A stochastic programming model for the aircraft sequencing and scheduling problem considering flight duration uncertainties

Published online by Cambridge University Press:  06 April 2022

R.K. Cecen Open the ORCID record for R.K. Cecen [Opens in a new window]
R.K. Cecen*
Affiliation:
Eskisehir Osmangazi University, Eskisehir, Turkey
*
Email: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

This study presents a stochastic mixed-integer linear programming model for the aircraft sequencing and scheduling problem. The proposed model aims to minimise the average fuel consumption per aircraft in the Terminal Manoeuvring Area while considering uncertain flight durations for each flight. The tabu search algorithm was selected to solve the problem. The stochastic solution and deterministic solution results were compared to show the benefits of the stochastic solution. The average sample approximation technique was applied to this problem, and enhancement rates of the average fuel consumption per aircraft were 8.78% and 9.11% comparing the deterministic approach

Keywords

Aircraft sequencing and scheduling problemStochastic programmingMixed-integer linear programmingFuel consumptionTabu search algorithm
Type
Research Article
Information
The Aeronautical Journal , Volume 126 , Issue 1304 , October 2022 , pp. 1736 - 1751
Check for updates
Copyright
© The Author(s), 2022. Published by Cambridge University Press on behalf of Royal Aeronautical Society

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Airports Council International- The impact of COVID-19 on the airport business and the path to recovery. Available from: https://aci.aero/news/2021/03/25/the-impact-of-covid-19-on-the-airport-business-and-the-path-to-recovery [Accessed 19. 05. 2021].Google Scholar
Eurocontrol-Network Operations Report 2019 Available from: https://www.eurocontrol.int/sites/default/files/2020-04/nm-annual-network-operations-report-2019-main-report.pdf [Accessed 19. 05. 2021].Google Scholar
Bianco, L., Dell’olmo, P. and Giordani, S. Scheduling models for air traffic control in terminal areas, J. Sched., 2006, 9, (3), pp 223–253.Google Scholar
Bennell, J.A., Mesgarpour, M. and Potts, C.N. Airport runway scheduling, 4OR, 2011, 9, (2), pp 115–138. CrossRefGoogle Scholar
Zhang, J., Zhao, P., Zhang, Y., Dai, X. and Sui, D. Criteria selection and multi-objective optimization of aircraft landing problem, J. Air Transp. Manag., 2020, 82, p 101734.CrossRefGoogle Scholar
Dönmez, K., Çetek, C. and Kaya, O. Aircraft sequencing and scheduling in parallel-point merge systems for multiple parallel runways, Transp. Res. Rec., 2021, pp 1–17.Google Scholar
Beasley, J.E., Krishnamoorthy, M., Sharaiha, Y.M. and Abramson, D. Scheduling aircraft landings—the static case, Transp. Sci., 2000, 34, (2), pp 180–197.CrossRefGoogle Scholar
Furini, F., Persiani, C.A. and Toth, P. Aircraft sequencing problems via a rolling horizon algorithm, International Symposium on Combinatorial Optimization Springer, Berlin, Heidelberg, 2012, pp 273–284.Google Scholar
Briskorn, D. and Stolletz, R. Aircraft landing problems with aircraft classes, J. Sched., 2014, 17, (1), pp 31–45.CrossRefGoogle Scholar
Ghoniem, A., Sherali, H.D. and Baik, H. Enhanced models for a mixed arrival-departure aircraft sequencing problem, INFORMS J. Comput., 2014, 26, (3), pp 514–530.CrossRefGoogle Scholar
Faye, A. Solving the aircraft landing problem with time discretization approach, Eur. J. Oper. Res., 2015, 242, (3), pp 1028–1038.CrossRefGoogle Scholar
Murça, M.C.R. and Müller, C. Control-based optimization approach for aircraft scheduling in a terminal area with alternative arrival routes, Transp. Res. E: Logist. Transp. Rev., 2015, 73, pp 96–113.CrossRefGoogle Scholar
Jones, J.C., Lovell, D.J. and Ball, M.O. Stochastic optimization models for transferring delay along flight trajectories to reduce fuel usage, Transp. Sci., 2018, 52, (1), pp 134–149.CrossRefGoogle Scholar
Cecen, R.K. and Çetek, F.A. Optimising aircraft arrivals in terminal airspace by mixed integer linear programming model, Aeronaut. J., 2020, 124, (1278), pp 1129–1145.CrossRefGoogle Scholar
Sölveling, G. and Clarke, J.P. Scheduling of airport runway operations using stochastic branch and bound methods, Transp. Res. C: Emerg. Technol., 2014, 45, pp 119–137.CrossRefGoogle Scholar
Montoya, J., Rathinam, S. and Wood, Z. Multiobjective departure runway scheduling using dynamic programming, IEEE Trans. Intell. Transp. Syst., 2013, 15, (1), pp 399–413.CrossRefGoogle Scholar
Lieder, A., Briskorn, D. and Stolletz, R. A dynamic programming approach for the aircraft landing problem with aircraft classes, Eur. J. Oper. Res., 2015, 43, (1), pp 61–69.CrossRefGoogle Scholar
Atkin, J.A., Burke, E.K., Greenwood, J.S. and Reeson, D. Hybrid metaheuristics to aid runway scheduling at London Heathrow airport, Transp. Sci., 2007, 41, (1), pp 90–106.Google Scholar
D’ariano, A., Pistelli, M. and Pacciarelli, D. Aircraft retiming and rerouting in vicinity of airports, IET Intell. Transp. Syst., 2012, 6, (4), pp 433–443.CrossRefGoogle Scholar
Furini, F., Kidd, M.P., Persiani, C.A. and Toth, P. Improved rolling horizon approaches to the aircraft sequencing problem, J. Sched., 2015, 18, (5), pp 435–447.CrossRefGoogle Scholar
Sama, M., D’ariano, A., D’ariano, P. and Pacciarelli, D. Optimal aircraft scheduling and routing at a terminal control area during disturbances, Transp. Res. Part C: Emerg. Technol., 2014, 47, pp 61–85.CrossRefGoogle Scholar
Hancerliogullari, G., Rabadi, G., Al-salem, A.H. and Kharbeche, M. Greedy algorithms and metaheuristics for a multiple runway combined arrival-departure aircraft sequencing problem, J. Air Transp. Manag., 2013, 32, pp 39–48.CrossRefGoogle Scholar
Liang, M., Delahaye, D. and Marechal, P. Conflict-free arrival and departure trajectory planning for parallel runway with advanced point-merge system, Transp. Res. Part C: Emerg. Technol., 2018, 95, pp 207–227.CrossRefGoogle Scholar
Salehipour, A., Modarres, M. and Naeni, L.M. An efficient hybrid meta-heuristic for aircraft landing problem, Comput. Oper. Res., 2013, 40, pp 207–213.CrossRefGoogle Scholar
Rodríguez-Díaz, A., Adenso-Díaz, B. and González-Torre, P.L. Minimizing deviation from scheduled times in a single mixed-operation runway, Comput. Oper. Res., 2017, 78, pp 193–202.CrossRefGoogle Scholar
Cecen, R., Cetek, C. and Kaya, O. Aircraft sequencing and scheduling in TMAs under wind direction uncertainties, Aeronaut. J., 2020, 124, (1282), pp 1896–1912.CrossRefGoogle Scholar
Salehipour, A., Moslemi, N.L. and Kazemipoor, H. Scheduling aircraft landings by applying a variable neighborhood descent algorithm: Runway-dependent landing time case, J. Appl. Oper. Res., 2009, 1, (1), pp 39–49.Google Scholar
Jiang, Y., Xu, Z., Xu, X., Liao, Z. and Luo, Y. A schedule optimization model on multirunway based on ant colony algorithm, Math. Probl. Eng., 2014, 2014, pp 1–13.Google Scholar
Zhan, Z.H., Zhang, J., Li, Y., Liu, O., Kwok, S.K., Ip, W.H. and Kaynak, O. An efficient ant colony system based on receding horizon control for the aircraft arrival sequencing and scheduling problem, IEEE Trans. Intell. Transp. Syst., 2010, 11, (2), pp 399–412.CrossRefGoogle Scholar
Beasley, J.E., Sonander, J. and Havelock, P. Scheduling aircraft landings at London Heathrow using a population heuristic, J. Oper. Res. Soc., 2001, 52, (5), pp 483–493.CrossRefGoogle Scholar
Hu, X.B. and Chen, W.H. Receding horizon control for aircraft arrival sequencing and scheduling, IEEE Trans. Intell. Transp. Syst., 2005, 6, (2), pp 189–197.CrossRefGoogle Scholar
Hu, X.B. and Paolo, E.A.D. A ripple-spreading genetic algorithm for the aircraft sequencing problem, Evol. Comput., 2011, 19, (1), pp 77–106.CrossRefGoogle ScholarPubMed
Hu, X.B. and di Paolo, E. An efficient genetic algorithm with uniform crossover for air traffic control, Comput. Oper. Res., 2009, 36, (1), pp 245–259.CrossRefGoogle Scholar
Liu, M., Liang, B., Zheng, F., Chu, C. and Chu, F. A two-stage stochastic programming approach for aircraft landing problem, 15th International Conference on Service Systems and Service Management, 2018.CrossRefGoogle Scholar
Pinol, H. and Beasley, J.E. Scatter search and bionomic algorithms for the aircraft landing problem, Eur. J. Oper. Res., 2006, 171, (2), pp 439–462.CrossRefGoogle Scholar
Hong, Y., Choi, B. and Kim, Y. Two-stage stochastic programming based on particle swarm optimization for aircraft sequencing and scheduling, IEEE Trans. Intell. Transp. Syst., 2018, 20, (4), pp 1365–1377.CrossRefGoogle Scholar
Hong, Y., Cho, N., Kim, Y. and Choi, B. Multiobjective optimization for aircraft arrival sequencing and scheduling, J. Air Transp., 2017, 25, (4), pp 115–122.CrossRefGoogle Scholar
Sadovsky, A. and Windhorst, R. A scheduling algorithm compatible with a distributed management of arrivals in the national airspace system, 2019 IEEE/AIAA 38th Digital Avionics Systems Conference (DASC) IEEE, 2019, pp 1–10.Google Scholar
Balakrishnan, H. and Chandran, B.G. Algorithms for scheduling runway operations under constrained position shifting, Oper. Res., 2010, 58, (6), pp 1650–1665.CrossRefGoogle Scholar
Farhadi, F., Ghoniem, A. and Al-Salem, M. Runway capacity management–an empirical study with application to Doha International Airport, Transp. Res. Part E: Logist. Transp. Rev., 2014, 68, pp 53–63.CrossRefGoogle Scholar
Lieder, A. and Stolletz, R. Scheduling aircraft take-offs and landings on interdependent and heterogeneous runways, Transp. Res. Part E: Logist. Transp. Rev., 2016, 88, pp 167–188.CrossRefGoogle Scholar
Bennell, J.A., Mesgarpour, M. and Potts, C.N. Dynamic scheduling of aircraft landings, Eur. J. Oper. Res., 2017, 258, pp 315–327.CrossRefGoogle Scholar
Girish, B.S. An efficient hybrid particle swarm optimization algorithm in a rolling horizon framework for the aircraft landing problem, Appl. Soft Comput., 2016, 44, pp 200–221.Google Scholar
Sabar, N.R. and Kendall, G. An iterated local search with multiple perturbation operators and time varying perturbation strength for the aircraft landing problem, Omega, 2015, 56, pp 88–98.CrossRefGoogle Scholar
Ji, X.P., Cao, X.B. and Tang, K. Sequence searching and evaluation: a unified approach for aircraft arrival sequencing and scheduling problems, Memetic Comput., 2016, 8, (2), pp 109–123.CrossRefGoogle Scholar
Solveling, G., Solak, S., Clarke, J.P. and Johnson, E. Runway operations optimization in the presence of uncertainties, J. Guid. Control Dyn., 2011, 34, (5), pp 1373–1382.CrossRefGoogle Scholar
Gupta, G., Malik, W. and Jung, Y. A mixed integer linear program for airport departure scheduling, 9th AIAA Aviation Technology, Integration, and Operations Conference (ATIO) and Aircraft Noise and Emissions Reduction Symposium (ANERS), 2009, p. 6933.Google Scholar
Sáez, R., Prats, X., Polishchuk, T. and Polishchuk, V. Traffic synchronization in terminal airspace to enable continuous descent operations in trombone sequencing and merging procedures: An implementation study for Frankfurt airport, Transp. Res. Part C: Emerg. Technol., 2020, 121, 102875.CrossRefGoogle Scholar
Samà, M., D’ariano, A. and Pacciarelli, D. Rolling horizon approach for aircraft scheduling in the terminal control area of busy airports, Procedia-Soc. Behav. Sci., 2013, 80, pp 531–552.CrossRefGoogle Scholar
Eun, Y., Hwang, I. and Bang, H. Optimal arrival flight sequencing and scheduling using discrete airborne delays, IEEE Trans. Intell. Transp. Syst., 2010, 11, (2), pp 359–373.Google Scholar
Samà, M., D’ariano, A., D’ariano, P. and Pacciarelli, D. Air traffic optimization models for aircraft delay and travel time minimization in terminal control areas, Public Trans., 2015, 7, (3), pp 321–337.CrossRefGoogle Scholar
Salehipour, A. An algorithm for single-and multiple-runway aircraft landing problem, Math. Comput. Simul., 2020, 175, pp 179–191.CrossRefGoogle Scholar
Kwasiborska, A. Sequencing landing aircraft process to minimize schedule length, Transp. Res. Procedia, 2017, 28, pp 111–116.CrossRefGoogle Scholar
Ng, K.K., Chen, C.H. and Lee, C.K.M. Mathematical programming formulations for robust airside terminal traffic flow optimisation problem, Comput. Ind. Eng., 2021, 154, p 107119.CrossRefGoogle Scholar
Kaplan, Z. and Çetek, C. Yapay bağişiklik metasezgiseli ile tek pistli havaalanlarinda iniş siralamasinin eniyilenmesi, Eskişehir Osmangazi Üniversitesi Mühendislik ve Mimarlık Fakültesi Dergisi, 2020, 28, (3), pp 321–331.CrossRefGoogle Scholar
Choi, S., Robinson, J.E., Mulfinger, D.G. and Capozzi, B.J. Design of an optimal route structure using heuristics-based stochastic schedulers, 29th Digital Avionics Systems Conference, 2010. CrossRefGoogle Scholar
Heidt, A., Helmke, H., Kapolke, M., Liers, F. and Martin, A. Robust runway scheduling under uncertain conditions, J. Air Transp. Manag., 2016, 56, pp 28–37.CrossRefGoogle Scholar
Ng, K.K.H., Lee, C.K.M., Chan, F.T. and Qin, Y. Robust aircraft sequencing and scheduling problem with arrival/departure delay using the min-max regret approach, Transp. Res. Part E: Logist. Transp. Rev., 2017, 106, pp 115–136.CrossRefGoogle Scholar
Murça, M.C.R. A robust optimization approach for airport departure metering under uncertain taxi-out time predictions, Aerosp. Sci. Technol., 2017, 68, pp 269–277.CrossRefGoogle Scholar
Solak, S., Solveling, G., Clarke, J.P.B. and Johnson, E.L. Stochastic runway scheduling, Transp. Sci., 2018, 52, (4), pp 917–940.CrossRefGoogle Scholar
Khassiba, A., Bastin, F., Cafieri, S., Gendron, B. and Mongeau, M. Two-stage stochastic mixed-integer programming with chance constraints for extended aircraft arrival management, Transp. Sci., 2020, 54, (4), pp 897–919.CrossRefGoogle Scholar
Dear, R.G. The dynamic scheduling of aircraft in the near terminal area, Flight Transportation Laboratory, Massachusetts Institute of Technology, 1976, Cambridge, MA.Google Scholar
https://www.routesonline.com/airports/6063/istanbul-sabiha-gokcen-international-airport/about/#mainContent [Accessed 19. 05. 2021].Google Scholar
Kaplan, Z. and Cetek, C. An approach sequencing model for minimum total fuel consumption and most efficient use of runway capacity, Master Thesis, Eskisehir Technical University, 2019.Google Scholar
https://www.oag.com/on-time-performance-airlines-airports [Accessed 19. 05. 2021].Google Scholar
BADA. User manual for the base of aircraft data (BADA) revision 3.11, 2013. Google Scholar
EASA- ICAO Aircraft Engine Emissions Databank. https://www.easa.europa.eu/easa-and-you/environment/icao-aircraft-engine-emissions-databank [Accessed 19. 05. 2021].Google Scholar
Birge, J.R. and Louveaux, F. Introduction to stochastic programming, Springer Science & Business Media, 2011.CrossRefGoogle Scholar
Rockafellar, R.T. and Wets, R.J.B. Scenarios and policy aggregation in optimization under uncertainty, Math. Oper. Res., 1991, 16, (1), pp 119–147.CrossRefGoogle Scholar
Lima, R.M., Conejo, A.J., Giraldi, L., le Maitre, O., Hoteit, I. and Knio, O.M. Sample average approximation for risk-averse problems: A virtual power plant scheduling application, EURO J. Comput. Optim., 2021, 9, 100005.CrossRefGoogle Scholar
Glover, F. Tabu search: A tutorial, Interfaces, 1990, 20, (4), pp 74–94.CrossRefGoogle Scholar
Alinaghian, M., Tirkolaee, E.B., Dezaki, Z.K., Hejazi, S.R. and Ding, W. An augmented Tabu search algorithm for the green inventory-routing problem with time windows, Swarm Evol. Comput., 2021, 60, 100802.CrossRefGoogle Scholar
Zhang, H., Liu, F., Zhou, Y. and Zhang, Z. A hybrid method integrating an elite genetic algorithm with tabu search for the quadratic assignment problem, Inf. Sci., 2020, 539, pp 347–374.CrossRefGoogle Scholar
Vela, C.R., Afsar, S., Palacios, J.J., González-Rodríguez, I. and Puente, J. Evolutionary tabu search for flexible due-date satisfaction in fuzzy job shop scheduling, Comput. Oper. Res., 2020, 119, 104931.CrossRefGoogle Scholar
Sangaiah, A.K. and Khanduzi, R. Tabu search with simulated annealing for solving a location-protection-disruption in hub network, Appl. Soft Comput., 2022, 114, 108056.Google Scholar
Ertem, M., Ozcelik, F. and Saraç, T. Single machine scheduling problem with stochastic sequence-dependent setup times, Int. J. Prod. Res., 2019, 57, (10), pp 3273–3289.CrossRefGoogle Scholar