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

Masoumeh Mirjafari, Alireza Rashidi Komijan, Ahmad Shoja

Abstract

Airline optimization is a significant problem in recent researches and airline industryl 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 very small gap to optimum solution.


Keywords

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

Full Text:

PDF EN

References

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.

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.

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.

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

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.

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.

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

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

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.

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

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.

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.

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

Shao Shengzhi (2012). Integrated Aircraft Fleeting, Routing, and Crew Pairing Models and Algorithms for the Airline Industry.Integrated Aircraft Fleeting, Routing, and Crew Pairing Models and Algorithms for the Airline Industry.

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

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 212, 445–454.

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 13, 158–164.

Yen, J.W., Birge, J.R., (2006).A stochastic programming approach to the airline crew scheduling problem. Transportation Science 40, 3–14.hebalov, andklabjan, (2004)

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.

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

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

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

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

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

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

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

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

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

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.

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

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

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

Held, M. Karp, R. M. (1970).The travelling salesman problem and minimum spanning trees, Oper. Res, 18, Pages 1138-1162.

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

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

Cacchian, Valentina and Salazar-González, Juan-José (2019).Heuristic approaches for flight retiming in an integrated airline scheduling problem of a regional carrier, Omega, 2028.

Eltoukhy, Abdelrahman, Wang, Z. X., T. S. Chan, Felix, Fu, X. (2019). Data analytics in managing aircraft routing and maintenance staffing with price competition by a Stackelberg-Nash game model,Transportation Research Part E: Logistics and Transportation Review, Volume 122, Pages 143-168.

Munari, Pedro and Alvarez, Aldair (2019).Aircraft routing for on-demand air transportation with service upgrade and maintenance events: Compact model and case study, Journal of Air Transport Management, Volume 75, 75-84.

Abstract Views

242
Metrics Loading ...

Metrics powered by PLOS ALM

Refbacks

  • 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   https://doi.org/10.4995/wpom