Abstract
The solution of the aircrew-scheduling problem is represented by a set of rotations developed from a given set of flight segments. Once the set of rotations to be made by aircrew members has been determined, the air carrier must solve the aircrew rostering problem that entails the monthly assignment of aircrew members to planned rotations. This paper attempts to solve the aircrew rostering problem, thus constructing personalized monthly schedules using Simulated Annealing, Genetic Algorithms, and Tabu Search techniques. The developed models are tested on numerical examples that consist of constructing schedules for pilots. Dimensions of the considered examples are characteristic of small and medium-sized airlines.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Agard, M. (1970). Monthly assignment of stewards by computer. In AGIFORS symposium proceedings (Vol. 10).
Anantaram, C., Joshi, P., Deshpande, K., & Trivedi, P. (1993). Crew rostering system—an expert system for scheduling crew for Indian airlines. In Proceedings of the ninth conference on artificial intelligence for applications.
Antosik, J. L. (1978). Automatic monthly crew assignment: a new approach. In AGIFORS symposium proceedings (Vol. 18).
Buhr, J. (1978.) Four methods for monthly crew assignment: a comparison of efficiency. In AGIFORS symposium proceedings (Vol. 18).
Burke, E. K., De Causmaecker, P., Petrović, S., & Vanden Berghe, G. (2001). Fitness evaluation for nurse scheduling problems. In Proceedings of the 2001 congress on evolutionary computation—CEC’01 (Vol. 2), 1139–1146.
Burke, E. K., De Causmaecker, P., Petrović, S., & Vanden Berghe, G. (2002). A multi criteria meta-heuristic approach to nurse rostering. In Proceedings of the 2002 congress on evolutionary computation—CEC ’02 (Vol. 2), 1197–1202.
Byrne, J. (1988). A preferential bidding system for technical aircrew. In AGIFORS symposium proceedings (Vol. 28).
Cappanera, P., & Gallo, G. (2004). A multicommodity flow approach to the crew rostering problem. Operations Research, 52(4), 583–596.
Caprara, A., Toth, P., & Vigo, D. et al. (1998). Modeling and solving the crew rostering problem. Operations Research, 46(6), 820–830.
Cherny, V. (1985). Thermodynamic approach to the traveling salesman problem: an efficient simulation algorithm. Journal of Optimization Theory and Applications, 45, 41–51.
Coello Coello, C. A. (2002). Theoretical and numerical constraint-handling techniques used with evolutionary algorithms: a survey of the state of the art. Computer Methods in Applied Mechanics and Engineering, 191, 1245–1287.
Day, P. R., & Ryan, D. M. (1997). Flight attendant rostering for short-haul airline operations. Operations Research, 45, 649–661.
Eglese, R. W. (1990). Simulated annealing: a tool for operational research. European Journal of Operational Research, 46, 271–281.
El Moudani, W., & Mora-Camino, F. (2000). A fuzzy solution approach for the roster planning problem. In Proceedings of the FUZZ IEEE 2000—the ninth IEEE international conference on fuzzy systems (Vol. 1).
El Moudani, W., Cosenza, C. A. N., & Mora-Camino, F. (2001). An intelligent approach for solving the airline crew rostering problem. In Proceedings of the ACS/IEEE international conference on computer systems and applications.
Ernst, A. T., Jiang, H., Krishnamoorthy, M., & Sier, D. (2004a). Staff scheduling and rostering: a review of applications, methods and models. European Journal of Operational Research, 153, 3–27.
Ernst, A. T., Jiang, H., & Krishnamoorthy, M. et al. (2004b). An annotated bibliography of personnel scheduling and rostering. Annals of Operations Research, 127(1–4), 21–144.
Freling, R., Lentink, R. M., & Wagelmans, A. P. M. (2004). A decision support system for crew planning in passenger transportation using a flexible branch-and-price algorithm. Annals of Operations Research, 127(1–4), 203–222.
Gamache, M., & Soumis, F. (1993). A method for optimally solving the rostering problem. Cahier du GERAD, G-90-40, Ecole des Hautes Etudes Commerciales, Montreal, Canada.
Giafierri, J., Hamon, J. P., & Lengline, S. (1982). Automatic monthly assignment of medium-haul cabin crew. In AGIFORS symposium proceedings (Vol. 22).
Glanert, W. (1984). A timetable approach to the assignment of pilots to rotations. In AGIFORS symposium proceedings (Vol. 24).
Glover, F. (1986). Future paths for integer programming and links to artificial intelligence. Computers & Operations Research, 13, 433–549.
Glover, F. (1989). Tabu search—Part I. ORSA Journal of Computing, 1, 190–206.
Glover, F. (1990a). Tabu search—Part II. ORSA Journal of Computing, 2, 4–32.
Glover, F. (1990b). Tabu search—a tutorial. Interfaces, 20, 74–94.
Glover, F., & Laguna, M. (1993). Tabu search. In C. R. Reeves (Ed.), Modern heuristic techniques for combinatorial problems. Oxford: Blackwell Scientific.
Hoffman, K. L., & Padberg, M. (1993). Solving airline crew scheduling problems by branch-and-cut. Management Science, 39, 657–682.
Kirkpatrick, S., Gellat, L., & Vecchi, M. (1983). Optimization by simulated annealing. Science, 220, 671–680.
Klabjan, D., Johnson, E. L., Nemhauser, G. L., Gelman, E., & Ramaswamy, S. (2001). Airline crew scheduling with regularity. Transportation Science, 35, 359–374.
Klabjan, D., Johnson, E. L., Nemhauser, G. L., Gelman, E., & Ramaswamy, S. (2002). Airline crew scheduling with time windows and plane-count constraints. Transportation Science, 36, 337–348.
Kohl, N., & Karisch, S. E. (2004). Airline crew rostering: problem types, modeling, and optimization. Annals of Operations Research, 127(1-4), 223–257.
Lučić, P., & Teodorović, D. (1999). Multi-objective simulated annealing model for aircrew rostering problem. Transportation Research, 33A, 19–45.
Marchettini, F. (1980). Automatic monthly cabin crew rostering procedure. In AGIFORS symposium proceedings (Vol. 20).
Metropolis, N., Rosenbluth, A., Rosenbluth, M., & Teller, M. (1953). Equation of state calculations by fast computing machines. Journal of Chemical Physics, 21, 1087–1092.
Moore, R., Evans, J., & Noo, H. (1978). Computerized tailored blocking. In AGIFORS symposium proceedings (Vol. 18).
Nicoletti, B. (1975). Automatic crew rostering. Transportation Science, 9, 33–42.
Ryan, D. M. (1992). The solution of massive generalized set partitioning problems in air crew rostering. Journal of the Operational Research Society, 43, 459–467.
Ryan, D. M. (2000). The solution of massive generalized set partitioning problems in aircrew rostering. Journal of The Operational Research Society, 51, 459–467.
Sarra, D. (1988). The automatic assignment model. In AGIFORS symposium proceedings (Vol. 28).
Serafini, P. (1994). Simulated annealing for multi objective optimization problems. In G.H.
Teodorović, D. (1988). Airline operations research. London: Gordon and Breach.
Teodorović, D., & Lučić, P. (1998). A fuzzy set theory approach to the aircrew rostering problem. Fuzzy Sets and Systems, 95, 261–271.
Tingley, G. A. (1979). Still another solution method for the monthly aircrew assignment problem. In AGIFORS symposium proceedings (Vol. 19).
Triki, E., Collette, Y., & Siarry, P. (2005). A theoretical study on the behavior of simulated annealing leading to a new cooling schedule. European Journal of Operational Research, 166, 77–92.
Vance, P. H., Barnhart, C., Johnson, E. L., & Nemhauser, J. L. (1997). Airline crew scheduling: a new formulation and decomposition algorithm. Operations Research, 45, 188–200.
Yan, S., Tung, T.-T., & Tu, Y.-P. (2002). Optimal construction of airline individual crew pairings. Computers & Operations Research, 29(4), 341–363.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Lučić, P., Teodorović, D. Metaheuristics approach to the aircrew rostering problem. Ann Oper Res 155, 311–338 (2007). https://doi.org/10.1007/s10479-007-0216-y
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10479-007-0216-y