Integrated Linear Integer Model of a Fleet Allocation and Aircraft Routing Problem with Operational Constraints

Document Type : Original Article

Authors

1 Department of Industrial Engineering, Payame Noor University, Tehran, Iran

2 Department of Industrial Engineering, Faculty of Engineering, Shahed University, Tehran, Iran

3 School of Industrial Engineering, College of Engineering, Tehran University, Tehran, Iran

Abstract

One of the topics that have been studied a lot in the field of airline industry optimization is related to flight planning, and air fleets, and how they relate to each other, which is called airline scheduling. Despite the high importance of this issue in the profitability of airline companies and the proper use of their resources, the high computational complexity of these models has led to considering each of them in a mathematical model separately, and as a result, the accuracy of the final decision will be decreased. So far, many articles have studied various relevant issues, in some cases, efforts to create integration in the process can be observed. However, there is a few operational views of the issue, and some key requirements were neglected due to the simplification of provided models. In this study, an integrated model of the two main stages of airline planning, including fleet allocation and aircraft maintenance routing, is considered simultaneously, and the performance of the developed model is investigated using real data from one of the airlines. Also, a sensitivity analysis of the model to some relevant parameters confirms the validity of the developed mathematical model and the solution algorithm. Then, a comparative study was investigated to compare the performance of the developed model with the operational method, including solving sub-problems stepwise. Also, the results are compared with the developed and similar method from the previous studies. The results confirm the superiority of the developed mathematical model.

Keywords

Main Subjects

References

  1. Shaw, S., "Airline marketing and management, Routledge, (2016).
  2. Group, A.T.A., "Facts & figures", (2014).
  3. Shaukat, S., Katscher, M., Wu, C.-L., Delgado, F. and Larrain, H., "Aircraft line maintenance scheduling and optimisation", Journal of Air Transport Management, Vol. 89, (2020), 101914. doi: 10.1016/j.jairtraman.2020.101914.
  4. Ball, M., Barnhart, C., Dresner, M., Hansen, M., Neels, K., Odoni, A., Peterson, E., Sherry, L., Trani, A. and Zou, B., "Total delay impact study: A comprehensive assessment of the costs and impacts of flight delay in the united states", (2010). https://rosap.ntl.bts.gov/view/dot/6234
  5. Feo, T.A. and Bard, J.F., "Flight scheduling and maintenance base planning", Management Science, Vol. 35, No. 12, (1989), 1415-1432. doi: 10.1287/mnsc.35.12.1415.
  6. Daskin, M.S. and Panayotopoulos, N.D., "A lagrangian relaxation approach to assigning aircraft to routes in hub and spoke networks", Transportation Science, Vol. 23, No. 2, (1989), 91-99. doi: 10.1287/trsc.23.2.91.
  7. Kabbani, N.M. and Patty, B.W., "Aircraft routing at american airlines", in proceedings of the agifors symposium, (1992).
  8. Clarke, L., Johnson, E., Nemhauser, G. and Zhu, Z., "The aircraft rotation problem", Annals of Operations Research, Vol. 69, (1997), 33-46. doi: 10.1023/A:1018945415148.
  9. Gopalan, R. and Talluri, K.T., "The aircraft maintenance routing problem", Operations research, Vol. 46, No. 2, (1998), 260-271. doi: 10.1287/opre.46.2.260.
  10. Barnhart, C., Boland, N.L., Clarke, L.W., Johnson, E.L., Nemhauser, G.L. and Shenoi, R.G., "Flight string models for aircraft fleeting and routing", Transportation Science, Vol. 32, No. 3, (1998), 208-220. doi: 10.1287/trsc.32.3.208.
  11. Mak, V. and Boland, N., "Heuristic approaches to the asymmetric travelling salesman problem with replenishment arcs", International Transactions in Operational Research, Vol. 7, No. 4‐5, (2000), 431-447. doi: 10.1111/j.1475-3995.2000.tb00209.x.
  12. Sriram, C. and Haghani, A., "An optimization model for aircraft maintenance scheduling and re-assignment", Transportation Research Part A: Policy and Practice, Vol. 37, No. 1, (2003), 29-48. doi: 10.1016/S0965-8564(02)00004-6.
  13. Liang, Z., Chaovalitwongse, W.A., Huang, H.C. and Johnson, E.L., "On a new rotation tour network model for aircraft maintenance routing problem", Transportation Science, Vol. 45, No. 1, (2011), 109-120. doi: 10.1287/trsc.1100.0338.
  14. Liang, Z. and Chaovalitwongse, W., "A network-based model for weekly aircraft maintenance routing with integrated fleet assignment problem", Manuscript, Department of Industrial Engineering and Management, Peking University, Beijing, China, (2011). doi: 10.1287/trsc.1120.0434.
  15. Jamili, A., "A robust mathematical model and heuristic algorithms for integrated aircraft routing and scheduling, with consideration of fleet assignment problem", Journal of Air Transport Management, Vol. 58, (2017), 21-30. doi: 10.1016/j.jairtraman.2016.08.008.
  16. Khanmirza, E., Nazarahari, M. and Haghbeigi, M., "A heuristic approach for optimal integrated airline schedule design and fleet assignment with demand recapture", Applied Soft Computing, Vol. 96, (2020), 106681. doi: 10.1016/j.asoc.2020.106681.
  17. Özkır, V. and Özgür, M.S., "Two-phase heuristic algorithm for integrated airline fleet assignment and routing problem", Energies, Vol. 14, No. 11, (2021), 3327. doi: 10.3390/en14113327.
  18. Sarac, A., Batta, R. and Rump, C.M., "A branch-and-price approach for operational aircraft maintenance routing", European Journal of Operational Research, Vol. 175, No. 3, (2006), 1850-1869. doi: 10.1016/j.ejor.2004.10.033.
  19. Eltoukhy, A.E., Chan, F.T., Chung, S. and Qu, T., "Optimization model and solution method for operational aircraft maintenance routing problem", in Proceedings of the world congress on engineering. Vol. 2, (2017).
  20. Eltoukhy, A.E., Chan, F.T., Chung, S.H. and Niu, B., "A model with a solution algorithm for the operational aircraft maintenance routing problem", Computers & Industrial Engineering, Vol. 120, (2018), 346-359. doi: 10.1016/j.cie.2018.05.002.
  21. Wen, X., Sun, X., Ma, H.-L. and Sun, Y., "A column generation approach for operational flight scheduling and aircraft maintenance routing", Journal of Air Transport Management, Vol. 105, (2022), 102270. doi: 10.1016/j.jairtraman.2022.102270.
  22. Saltzman, R.M. and Stern, H.I., "The multi-day aircraft maintenance routing problem", Journal of Air Transport Management, Vol. 102, (2022), 102224. doi: 10.1016/j.jairtraman.2022.102224.
  23. Pasha, J., Dulebenets, M.A., Fathollahi-Fard, A.M., Tian, G., Lau, Y.-y., Singh, P. and Liang, B., "An integrated optimization method for tactical-level planning in liner shipping with heterogeneous ship fleet and environmental considerations", Advanced Engineering Informatics, Vol. 48, (2021), 101299. doi: 10.1016/j.aei.2021.101299.
  24. Haouari, M., Shao, S. and Sherali, H.D., "A lifted compact formulation for the daily aircraft maintenance routing problem", Transportation Science, Vol. 47, No. 4, (2013), 508-525. doi: 10.1287/trsc.1120.0433.
  25. Al-Thani, N.A., Ahmed, M.B. and Haouari, M., "A model and optimization-based heuristic for the operational aircraft maintenance routing problem", Transportation Research Part C: Emerging Technologies, Vol. 72, (2016), 29-44. doi: 10.1016/j.trc.2016.09.004.
  26. Safaei, N. and Jardine, A.K., "Aircraft routing with generalized maintenance constraints", Omega, Vol. 80, (2018), 111-122. doi: 10.1016/j.omega.2017.08.013.
  27. Kenan, N., Diabat, A. and Jebali, A., "Codeshare agreements in the integrated aircraft routing problem", Transportation Research Part B: Methodological, Vol. 117, (2018), 272-295. doi: 10.1016/j.trb.2018.08.008.
  28. Deng, Q., Santos, B.F. and Curran, R., "A practical dynamic programming based methodology for aircraft maintenance check scheduling optimization", European Journal of Operational Research, Vol. 281, No. 2, (2020), 256-273. doi: 10.1016/j.ejor.2019.08.025.
  29. Ruan, J., Wang, Z., Chan, F.T., Patnaik, S. and Tiwari, M.K., "A reinforcement learning-based algorithm for the aircraft maintenance routing problem", Expert Systems with Applications, Vol. 169, (2021), 114399. doi: 10.1016/j.eswa.2020.114399.
  30. Xu, Y., Wandelt, S. and Sun, X., "Airline integrated robust scheduling with a variable neighborhood search based heuristic", Transportation Research Part B: Methodological, Vol. 149, (2021), 181-203. doi: 10.1016/j.trb.2021.05.005.
  31. Papadakos, N., "Integrated airline scheduling: Decomposition and acceleration techniques", IC-PARC (centre for Planning and Resource Control), (2006), 1-38. doi: 10.1016/j.cor.2007.08.002.
  32. Bazargan, M., "Airline operations and scheduling, Routledge, (2016).
  33. Ahmed, M.B., Mansour, F.Z. and Haouari, M., "Robust integrated maintenance aircraft routing and crew pairing", Journal of Air Transport Management, Vol. 73, (2018), 15-31. doi: 10.1016/j.jairtraman.2018.07.007
  34. Parmentier, A., "Aircraft routing: Complexity and algorithms", Rapport de stage de master, École des Ponts ParisTech, (2013).
International Journal of Engineering
Volume 36, Issue 4
TRANSACTIONS A: Basics
April 2023
Pages 669-681

Files

Share

How to cite

Statistics