Optimization Model for an Airline Crew Rostering Problem: Case of Garuda Indonesia
DOI:
https://doi.org/10.5614/j.math.fund.sci.2013.45.3.2Keywords:
crew pairing, crew labor regulation, crew rostering, crew scheduling, optimization, simulated annealing.Abstract
This paper discusses the cockpit crew rostering problem at Garuda Indonesia, taking into account a number of internal cockpit crew labor regulations. These internal labor regulations are in general more restrictive at Garuda Indonesia than at other airlines, so that modeling the cockpit crew rostering problem for Garuda Indonesia is challenging. We have derived mathematical expressions for the cockpit crew labor regulations and some technical matters. We model a non-linear integer programming for the rostering problem, using the average relative deviation of total flight time to the ideal flight time as the objective function. The optimization model have been tested for all classes of cockpit crews of Garuda Indonesia, using a simulated annealing method for solving the problem. We obtained satisfactory rosters for all crew members in a short amount of computing time. This shows that the optimization problem is well-defined.References
Lucic, P. & Teodorovic, D., Simulated Annealing for Multi-objective Aircrew Rostering Problem, Transportation Research, Part A, 33, pp. 19-45, 1999.
Chang, S.C., A New Aircrew-Scheduling Model for Short-Haul Routes, Journal of Transport Management, 8, pp. 249-260, 2002.
Gamache, M., Hertz, A. & Oullet, J., A Graph Coloring Model for a Feasibility Problem in Monthly Crew Scheduling with Preferential Bidding, Computer and Operations Research, 34(8), pp. 2384-2395, 2007.
Kovari, B., Modern Crew Management Methods in Air Transport, Transportation. Engineering, 31(I-2), pp. 3-16, 2003.
Lederer, P.J. & Nambimadom, R.S., Airline Network Design, Operations Research, 46, pp.785-804, 1999.
Medard, C.P.A. & Sawhney, N., Airline Crew Scheduling from Planning to Operations, European Journal of Operational Research, 183(3), pp. 1013-1027, 2007.
Vance, P.H., Barnhart, C., Johnson, E.L. & Nemhauser, G.L., Airline Crew Scheduling: A New Formulation and Decompotition Algorithm, Operations Research, 45(2), pp. 188-200, 1997.
Yan, S. & Tu, Y., A Network Model for Airline Cabin Crew Scheduling,European Journal of Operational Research, 140, pp. 53-540, 2002.
AhmadBeygi, S., Cohn, A. & Weir, M., An Integer Programming Approach to Generating Airline Crew Pairings, Computer and Operations Research, 36(4), pp. 1284-1298, 2009.
Barnhart, C., Johnson, E.L., Nemhauser, G.L., Savelsbergh, M.W.P. & Vance, P.H., Branch-and-Price: Column Generation for Solving Huge Integer Programs, Operations Research, 46(3), pp. 316-328, 1999.
Deng, G. & Lin, W., Ant Colony Optimization-Base Algorithm for Airline Crew Scheduling Problem, Expert System with Applications, 38(5), pp. 5787-5793, 2011.
Goumopoulos, C. & Housos, E., Efficients Trip Generation with a Rule Modeling System for Crew Scheduling Problems, Journal of System and Software, 69(1-2), pp. 43-56, 2004.
Gamache, M., Soumis, F., Marquis, G. & Desrosiers, J., A Column Generation Approach for Large-Scale Aircrew Rostering Problems, Operations Research, 47(2), pp. 247-260, 1999.
Hoffman, K.L. & Padberg, M., Solving Airline Crew Scheduling Problem by Branch-and-Cut, Management Science, 39(6), pp. 657-682, 1993.
Souai, N. & Teghem, J., Genetic Algorithm Based Approach for Integrated Airline Crew-Pairing/CROPA and Rostering Problem, European Journal of Operational Research, 199(3), pp. 674-683, 2009.
