Abstract
Within the complex and dynamic environment of the airline industry, any disturbance to normal operations has dramatic impact, and usually imposes high additional costs. Because of irregular events during day-to-day operations, airline crew schedules are rarely operated as planned in practice. Therefore, disrupted schedules should be recovered with as small changes as possible. In this article, we propose a genetic algorithm (GA) based approach, in which disrupted flights are reassigned within an evolutionary process. Because of the slow convergence rate achieved by conventional GA, a special local improvement procedure is applied in this approach. Computational results are reported for several disruption scenarios on real-life instances from a medium-sized European airline.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Barnhart, C., Johnson, E. L., Nemhauser, G. L., Savelsbergh, M. W. P., Vance, P. H. (1998). Branch-and-price: Column generation for solving huge integer programs. Operations Research 46, 316–329.
Barnhart, C., Johnson, E. L., Nemhauser, G. L., Vance, P. H. (1999). Crew scheduling. In: Hall, R. (Ed.), Handbook of Transportation Science. Kluwer Academic Publisher, Norwell, pp. 493–521.
Beasley, J., Chu, P. (1996). A genetic algorithm for the set covering problem. European Journal of Operational Research 94, 392–404.
Bölte, A., Thonemann, U. W. (1996). Optimizing simulated annealing schedules with genetic programming. European Journal of Operational Research 92 (2), 402–416.
Carmen Systems AB (2004). Carmen integrated operations control. URL http://www.carmen.se/
El Moudani, W., Cosenza, C., de Coligny, M., Mora-Camino, F. (2001). A bicriterion approach for the airline crew rostering problem. In: Zitzler, E., Deb, K., Thiele, L., Coello, C. A. C., Corne, D. (Eds.), Proceedings of the First International Conference on Evolutionary Multi-Criterion Optimization (EMO 2001). Springer-Verlag, Berlin, pp. 486–500.
Fahle, T., Junker, U., Karisch, S., Kohl, N., Sellmann, M., Vaaben, B. (2002). Constraint programming based column generation for crew assignment. Journal of Heuristics 8, 59–81.
Guo, Y., Mellouli, T., Suhl, L., Thiel, M. P. (2003). A partially integrated airline crew scheduling approach with time-dependent crew capacities and multiple home bases. Tech. rep. WP0303, DS&OR Lab., University of Paderborn, Germany, accepted by European Journal of Operational Research.
Hartmann, S. (1998). A competitive genetic algorithm for resource-constrained project scheduling. Naval Research Logistics 45, 733–750.
Hoffman, K. L., Padberg, M. (1993). Solving airline crew scheduling problems by branch-and-cut. Management Science 39 (6), 657–682.
Holland, J. (1975). Adaption in natural and artificial systems. The University of Michigan Press.
ILOG (2002). Cplex v8.0 User’s Manual. ILOG, France.
Irrgang, M. E. (1995). Airline irregular operations. In: Jenkins, D., Ray, C. (Eds.), Handbook of airline economics, 1st Edition. McGrawHill Aviation Week Group, New York, pp. 349–365.
Kohl, N. and Karisch, S. E. (2004). Airline crew rostering: Problem types, modeling, and optimization. Annals of Operations Research, 127: 223–257.
Lettovský, L., Johnson, E. L., Nemhauser, G. L. (2000). Airline crew recovery. Transportation Science 34 (4), 337–348.
Mellouli, T. (2001). A network flow approach to crew scheduling based on an analogy to a train/aircraft maintenance routing problem. In: Voß, S., Daduna, J. (Eds.), Computer-Aided Scheduling of Public Transport. Springer, Berlin, pp. 91–120.
Michalewicz, Z., Fogel, D. B. (2000). How to Solve It: Modern Heuristics. Springer-Verlag.
Reeves, C. R. (1993). Modern heuristic techniques for combinatorial problems. John Wiley & Sons.
Rosenberger, J. M., Johnson, E. L., Nemhauser, G. L. (2003). Rerouting aircraft for airline recovery. Transportation Science 37 (4), 408–421.
Stojković, M., Soumis, F., Desrosiers, J. (1998). The operational airline crew scheduling problem. Transportation Science 32 (3), 232–245.
Suhl, L. (1995). Computer-Aided Scheduling-An Airline Perspective. Deutscher Universitäts-Verlag (DUV), Wiesbaden.
Suhl, U. H. (1994). MOPS: A Mathematical OPtimization System. European Journal of Operational Research 72, 312–322.
Thierens D. and Goldberg D. E. (1994). Convergence models of genetic algorithm selection schemes. In PPSN III: Proceedings of the International Conference on Evolutionary Computation. The Third Conference on Parallel Problem Solving from Nature, pages 119–129, London, UK, Springer-Verlag.
Wei, G., Yu, G., Song, M. (1997). Optimization model and algorithm for crew management during airline irregular operations. Journal of Combinatorial Optimization 1 (3), 305–321.
Yan, S., Lin, C. G. (1997). Airline scheduling for the temporary closure of airports. Transportation Science 31 (1), 72–83.
Yu, G., Argüello, M., Song, G., McCowan, S. M., White, A. (2003). A new era for crew recovery at continental airlines. Interfaces 33 (1), 5–22.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Guo, Y., Suhl, L. & Thiel, M.P. Solving the airline crew recovery problem by a genetic algorithm with local improvement. Oper Res Int J 5, 241–259 (2005). https://doi.org/10.1007/BF02944311
Issue Date:
DOI: https://doi.org/10.1007/BF02944311