×

A partially integrated airline crew scheduling approach with time-dependent crew capacities and multiple home bases. (English) Zbl 1116.90046

Summary: Crew scheduling for airlines requires an optimally scheduled coverage of flights with regard to given timetables. We consider the crew scheduling and assignment process for airlines, where crew members are stationed unevenly among home bases. In addition, their availability changes dynamically during the planning period due to pre-scheduled activities, such as office and simulator duties, vacancy, or requested off-duty days.
We propose a partially integrated approach based on two tightly coupled components: the first constructs chains of crew pairings spaced by weekly rests, where crew capacities at different domiciles and time-dependent availabilities are considered. The second component rearranges parts of these pairing chains into individual crew schedules with, e.g., even distribution of flight time. Computational results with real-life data from an European airline are presented.

MSC:

90B35 Deterministic scheduling theory in operations research
90B06 Transportation, logistics and supply chain management
90B10 Deterministic network models in operations research
90B80 Discrete location and assignment

Software:

CPLEX; MOPS
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Arabeyre, J. P.; Feranley, J.; Steiger, F. C.; Teather, W., The airline crew scheduling problem: A survey, Transportation Science, 3, 2, 140-163 (1969)
[2] Barnhart, C.; Johnson, E. L.; Nemhauser, G. L.; Vance, P. H., Crew scheduling, (Hall, R., Handbook of Transportation Science (1999), Kluwer Academic Publisher: Kluwer Academic Publisher Norwell), 493-521
[3] Bertossi, A.; Carraresi, P.; Gallo, G., On some matching problems arising in vehicle scheduling models, Networks, 17, 271-281 (1989) · Zbl 0646.90042
[4] Cohn, A.; Barnhart, C., Improving crew scheduling by incorporating key management routing decisions, Operations Research, 51, 3, 387-396 (2003) · Zbl 1163.90485
[5] Desrochers, M.; Soumis, F., A column generation approach to the urban transit crew scheduling problem, Transportation Science, 23, 1, 1-13 (1989) · Zbl 0668.90043
[6] Desrosiers, J.; Dumas, Y.; Solomon, M. M.; Soumis, F., Time constrained routing and scheduling, (Ball, M.; Magnanti, T.; Monma, C.; Newhauser, G., Network Routing. Network Routing, Handbooks in Operations Research and Management Science, vol. 8 (1995), Elsevier: Elsevier Amsterdam), 35-140 · Zbl 0861.90052
[7] El Moudani, W.; Cosenza, C.; de Coligny, M.; Mora-Camino, F., A bi-criterion approach for the airline crew rostering problem, (Zitzler, E.; Deb, K.; Thiele, L.; Coello, C. A.C.; Corne, D., Proceedings of the First International Conference on Evolutionary Multi-criterion Optimization (EMO 2001) (2001), Springer-Verlag: Springer-Verlag Berlin), 486-500
[8] Ernst, A. T.; Jiang, H.; Krishnamoorthy, M.; Nott, H.; Sier, D., Rail crew scheduling and rostering optimization algorithms, (Voß, S.; Daduna, J., Computer-aided Scheduling of Public Transport (2001), Springer: Springer Berlin), 53-72 · Zbl 0989.90510
[9] Garfinkel, R. S.; Nemhauser, G. L., The set-partitioning problem: Set covering with equality constraints, Operations Research, 17, 5, 848-856 (1969) · Zbl 0184.23101
[10] Hoffman, K. L.; Padberg, M., Solving airline crew scheduling problems by branch-and-cut, Management Science, 39, 6, 657-682 (1993) · Zbl 0783.90051
[11] ILOG, 2002. Cplex v8.0 User’s Manual. ILOG, France.; ILOG, 2002. Cplex v8.0 User’s Manual. ILOG, France.
[12] Klabjan, D.; Johnson, E. L.; Nemhauser, G. L.; Gelman, E.; Ramaswamy, S., Airline crew scheduling with time windows and plane-count constraints, Transportation Science, 36, 3, 337-348 (2002) · Zbl 1134.90386
[13] Kohl, N., Karisch, S.E., 2002. Airline crew rostering: Problem types, modeling, and optimization. Carmens Systems, 3rd. revised version (July 2003). URL http://www.carmen.se/; Kohl, N., Karisch, S.E., 2002. Airline crew rostering: Problem types, modeling, and optimization. Carmens Systems, 3rd. revised version (July 2003). URL http://www.carmen.se/
[14] König, H.; Strauss, C., Rostering-integrated services and crew efficiency, Information Technology and Tourism, 3, 1, 27-39 (2000)
[15] Kress, M.; Golany, B., Optimizing the assignment of aircrews to aircraft in an airlift operation, European Journal of Operational Research, 77, 3, 475-485 (1994) · Zbl 0809.90097
[16] Lavoie, S.; Minoux, M.; Odier, E., A new approach for crew pairing problems by column generation with an application to air transportation, European Journal of Operational Research, 35, 1, 45-58 (1988) · Zbl 0636.90041
[17] Mellouli, T., A network flow approach to crew scheduling based on an analogy to a train/aircraft maintenance routing problem, (Voß, S.; Daduna, J., Computer-Aided Scheduling of Public Transport (2001), Springer: Springer Berlin), 91-120 · Zbl 0989.90519
[18] Mellouli, T., 2003. Scheduling and routing processes in public transport systems. Habilitation Thesis, University of Paderborn, Germany.; Mellouli, T., 2003. Scheduling and routing processes in public transport systems. Habilitation Thesis, University of Paderborn, Germany.
[19] Nicoletti, B., Automatic crew rostering, Transportation Science, 9, 1, 33-42 (1975)
[20] Ryan, D. M., The solution of massive generalized set partitioning problems in aircrew rostering, Journal of the Operational Research Society, 43, 5, 459-567 (1992)
[21] Sanders, P., Takkula, T., Wedelin, D., 1999. High performance integer optimization for crew scheduling. In: HPCN Europe 1999, pp. 3-12.; Sanders, P., Takkula, T., Wedelin, D., 1999. High performance integer optimization for crew scheduling. In: HPCN Europe 1999, pp. 3-12. · Zbl 0990.90074
[22] Subramanian, R.; Scheff, R. P.; Quillinan, J. D.; Wiper, D. S.; Marsten, R. E., Cold-start: Fleet assignment at delta air lines, Interfaces, 24, 1, 104-120 (1994)
[23] Suhl, L., Computer-aided Scheduling-an Airline Perspective (1995), Deutscher Universitats-Verlag (DUV): Deutscher Universitats-Verlag (DUV) Wiesbaden
[24] Suhl, U. H., MOPS: A mathematical optimization system, European Journal of Operational Research, 72, 312-322 (1994) · Zbl 0800.90690
[25] Suhl, U.H., 2000. MOPS—Mathematical OPtimization System. OR News, No. 8, 2000, pp. 11-16.; Suhl, U.H., 2000. MOPS—Mathematical OPtimization System. OR News, No. 8, 2000, pp. 11-16.
[26] Yan, S.; Tu, Y. P., A network model for airline cabin crew scheduling, European Journal of Operational Research, 140, 3, 531-540 (2002) · Zbl 0998.90035
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.