An integrated model for aircraft routing and crew scheduling: Lagrangian Relaxation and metaheuristic algorithm

Masoumeh Mirjafari, Alireza Rashidi Komijan, Ahmad Shoja


Airline optimization is a significant problem in recent researches and airline industrial as it can determine the level of service, profit and competition status of the airline. Aircraft and crew are expensive resources that need efficient utilization. This paper focuses simultaneously on two major issues including aircraft maintenance routing and crew scheduling. Several key issues such as aircraft replacement, fairly night flights assignment and long-life aircrafts are considered in this model. We used the flight hours as a new framework to control aircraft maintenance. At first, an integrated mathematical model for aircraft routing and crew scheduling problems is developed with the aim of cost minimization. Then, Lagrangian relaxation and Particle Swarm Optimization algorithm (PSO) are used as the solution techniques. To evaluate the efficiency of solution approaches, model is solved with different numerical examples in small, medium and large sizes and compared with GAMS output. The results show that Lagrangian relaxation method provides better solutions comparing to PSO and also has a small gap to optimum solution.


Aircraft maintenance routing; Crew scheduling; Integer Programming; Lagrangian Relaxation; Particle Swarm Optimization

Full Text:



Al-Thani, Nayla Ahmad, Ben Ahmed, Mohamed and Haouari, Mohamed (2016). A model and optimization-based heuristic for the operational aircraft maintenance routing problem, Transportation Research Part C: Emerging Technologies, Volume 72, Pages 29-44.

Azadeh, A., HosseinabadiFarahani, M., Eivazy, H., Nazari-Shirkouhi, S., &Asadipour, G. (2013). A hybrid meta-heuristic algorithm for optimization of crew scheduling, Applied Soft Computing, Volume 13, Pages 158-164.

Barnhart C. and Cohn, A. (2004). Airline schedule planning: Accomplishments and opportunities, Manufacturing & Service Operations Management, 6(1):3-22, 47, 69, 141, 144.

Basdere, Mehmet and Bilge, Umit (2014). Operational aircraft maintenance routing problem with remaining time consideration, European Journal of Operational Research, Volume 235, Pages 315-328.

Bazargan, Massoud (2010). Airline Operations and scheduling second edition, Embry-Riddle Aeronautical University, USA, Ashgate publishing limite.

Belien, Jeroen, Demeulemeester, Eric and Brecht (2010). Integrated staffing and scheduling for an aircraft line maintenance problem, HUB RESEARCH PAPER Economics & Management.

Ben Ahmed, M., Zeghal Mansour, Farah and Haouari, Mohamed (2018). Robust integrated maintenance aircraft routing and crew pairing, Journal of Air Transport Management, Volume 73, Pages 15-31.

Ben Ahmed, M., Zeghal Mansour, F., Haouari, M. (2017). A two-level optimization approach for robust aircraft routing and retiming, Computers and Industrial Engineering, Volume 112, Pages 586-594.

Borndorfer, R., Schelten, U., Schlechte, T., Weider, S. (2006). A column generation approach to airline crew scheduling, Springer Berlin Heidelberg, Pages 343-348.

Clarke, L., E. Johnson, G. Nemhauser, Z. Zhu. (1997). The Aircraft Rotation Problem. Annals of Operations Research, 69, Pages 33-46.

Deveci, Muhammet and ÇetinDemirel, Nihan (2018). Evolutionary algorithms for solving the airline crew pairing problem, Computers & Industrial Engineering, Volume 115, Pages 389-406.

Dozic, S., Kalic, M. (2015). Three-stage airline fleet planning model, J. Air Transport. Manag, 43, Pages 30-39.

Eltoukhy, A.E., Chan, F.T., Chung, S. (2017). Airline schedule planning: a review and future directions, Ind. Manag. Data Syst, 117(6), Pages 1201-1243.

Feo, T. A., J. F. Bard. (1989). Flight Scheduling and Maintenance Base Planning. Management Science, 35(12), Pages 1415-1432.

Goffin, J. L. (1977). On the convergence rates of subgradient optimization methods. Math. Programming, 13, Pages 329-347.

Gopalakrishnan, B., Johnson, E. L (2005). Airline crew scheduling, State-of-the-art. Ann. Oper. Res, 140(1), Pages 305-337.

Held, M. and Karp, R.M. (1970). The Traveling-Salesman Problem and Minimum SpanningTrees. Operations Research, 18, 1138-1162.

Held, M. Wolfe, P., Crowder, H. D. (1974). Validation of subgradient optimization, Math. Programming, 6, 62-88.

Jamili, Amin (2017). A robust mathematical model and heuristic algorithms for integrated aircraft routing and scheduling, with consideration of fleet assignment problem, Journal of Air Transport Management, Volume 58, Pages 21-30.

Jiang, H., Barnhart, C. (2009) Dynamic airline scheduling, Transport. Sci, 43(3), Pages 336-354.

Kasirzadeh, A., Saddoune, M., Soumis, F. (2015). Airline crew scheduling: models, algorhitms and data sets, Euro Journal on Transportation and Logistics, 6(2), Pages 111-137.

Lacasse-Guay, E., Desaulniers, G., Soumis, F. (2010). Aircraft routing under different business processes, J. Air Transport. Manag, 16(5), Pages 258-263.

Muter, İbrahim, Birbil, Ş. İlker, Bülbül, Kerem, Şahin, Güvenç,Yenigün, Hüsnü, Taş,Duygu andTüzün, Dilek (2013). Solving a robust airline crew pairing problem with column generation, Computers & Operations Research, Volume 40, Issue 3, Pages 815-830.

Saddoune, Mohammed, Desaulniers, Guy, Elhallaoui, Issmail and François Soumis (2011). Integrated airline crew scheduling: A bi-dynamic constraint aggregation method using neighborhoods, European Journal of Operational Research, Volume 212, Pages 445-454.

Safaei, Nima and K.S.Jardine, Andrew (2018). Aircraft routing with generalized maintenance constraints, Omega, Volume 80, Pages 111-122.

Shao Shengzhi (2012). Integrated Aircraft Fleeting, Routing, and Crew Pairing Models and Algorithms for the Airline Industry, Faculty of the Virginia Polytechnic Institute and State University In Partial Fulfillment of the Requirements for the Degree of Doctor of Philosophy in Industrial and Systems Engineering.

Shao, S., Sherali, H.D., Haouari, M. (2017). A novel model and decomposition approach for the integrated airline fleet assignment, aircraft routing, crew pairing problem, Transport. Sci, 51(1), Pages 233-249.

Sherali, H.D., Bish, E.K., Zhu, X. (2006). Airline fleet assignment concepts, models and algorithms, Eur. J. Oper. Res, 172(1), Pages 1-30.

Warburg, V., Hansen, T.G., Larsen, A., Norman, H., Andersson, E. (2008). Dynamic airline scheduling: an analysis of potentials of refleeting and retiming, J. Air Transport. Manag. 14(4), Pages 163-167.

Yan, C. and Kung, J. (2018). Robust aircraft routing, Transport. Sci, 52(1), Pages 118-133.

Yen, J.W., Birge, J.R., (2006). A stochastic programming approach to the airline crew scheduling problem. Transportation Science, Volume 40, Pages 3-14.

Yu, G. (1998). Operation Research in the Airline Industry. Springer, New York, NY.

Zeren, Bahadir and Ozkol, Ibrahim (2016). A novel column generation strategy foe large scale airline crew pairing problems, Expert system with applications, Volume 55, Pages 133-144.

Zhang, Dong, Lau, H.Y.K. Henry and Yu, Chuhang (2015). A two stage heuristic algorithm for the integrated aircraft and crew schedule recovery problems, Computers and Industrial Engineering, Volume 87, Pages 436-453.

Abstract Views

Metrics Loading ...

Metrics powered by PLOS ALM


  • There are currently no refbacks.

This journal is licensed under a Creative Commons Attribution 4.0 International License.

Universitat Politècnica de València

e-ISSN: 1989-9068