×

Integrated airline crew scheduling: a bi-dynamic constraint aggregation method using neighborhoods. (English) Zbl 1237.90127

Summary: The integrated crew scheduling (ICS) problem consists of determining, for a set of available crew members, least-cost schedules that cover all flights and respect various safety and collective agreement rules. A schedule is a sequence of pairings interspersed by rest periods that may contain days off. A pairing is a sequence of flights, connections, and rests starting and ending at the same crew base. Given its high complexity, the ICS problem has been traditionally tackled using a sequential two-stage approach, where a crew pairing problem is solved in the first stage and a crew assignment problem in the second stage. Recently, Saddoune et al. (2010) developed a model and a column generation/dynamic constraint aggregation method for solving the ICS problem in one stage. Their computational results showed that the integrated approach can yield significant savings in total cost and number of schedules, but requires much higher computational times than the sequential approach. In this paper, we enhance this method to obtain lower computational times. In fact, we develop a bi-dynamic constraint aggregation method that exploits a neighborhood structure when generating columns (schedules) in the column generation method. On a set of seven instances derived from real-world flight schedules, this method allows to reduce the computational times by an average factor of 2.3, while improving the quality of the computed solutions.

MSC:

90B70 Theory of organizations, manpower planning in operations research
Full Text: DOI

References:

[1] Barnhart, C.; Shenoi, R. G., An approximate model and solution approach for the long-haul crew pairing problem, Transportation Science, 221-231 (1998) · Zbl 0987.90527
[2] Boubaker, K.; Desaulniers, G.; Elhallaoui, I., Bidline scheduling with equity by heuristic dynamic constraint aggregation, Transportation Research Part B: Methodological, 44, 50-61 (2010)
[3] Campbell, K. W.; Durfee, R. B.; Hines, G. S., FedEx generates bid lines using Simulated Annealing, Interfaces, 27, 2, 1-16 (1997)
[4] Christou, I. T.; Zakarian, A.; Liu, J.; Carter, H., A two-phase genetic algorithm for large-scale bidline-generation problems at Delta Air Lines, Interfaces, 29, 5, 51-65 (1999)
[5] Desaulniers, G.; Desrosiers, J.; Dumas, Y.; Marc, S.; Rioux, B.; Solomon, M. M.; Soumis, F., Crew pairing at Air France, European Journal of Operational Research, 97, 245-259 (1997) · Zbl 0944.90040
[6] Desaulniers, G.; Desrosiers, J.; Gamache, M.; Soumis, F., Crew scheduling in air transportation, (Crainic, T. G.; Laporte, G., Fleet Management and Logistics (1998), Kluwer: Kluwer Boston), 169-185 · Zbl 0964.90018
[7] Desrosiers, J.; Dumas, Y.; Solomon, M. M.; Soumis, F., Time constrained routing and scheduling, (Ball, M. O.; etal., Network Routing. Network Routing, Handbooks in Operations Research and Management Science, vol. 8 (1995), North-Holland: North-Holland Amsterdam), 35-139 · Zbl 0861.90052
[8] Desrosiers, J.; Lübbecke, M. E., A primer in column generation, (Desaulniers, G.; Desrosiers, J.; Solomon, M. M., Column Generation (2005), Springer: Springer New York, NY), 1-32 · Zbl 1246.90093
[9] Elhallaoui, I.; Desaulniers, G.; Metrane, A.; Soumis, F., Bi-dynamic constraint aggregation and subproblem reduction, Computers and Operations Research, 35, 1713-1724 (2008) · Zbl 1211.90118
[10] Elhallaoui, I.; Metrane, A.; Soumis, F.; Desaulniers, G., Multiphase dynamic constraint aggregation for set partitioning type problems, Mathematical Programming A, 123, 2, 345-370 (2010) · Zbl 1189.90099
[11] Elhallaoui, I.; Villeneuve, D.; Soumis, F.; Desaulniers, G., Dynamic aggregation of set partitioning constraints in column generation, Operations Research, 53, 632-645 (2005) · Zbl 1165.90604
[12] Gopalakrishnan, B.; Johnson, E. L., Airline crew scheduling: state-of-the-art, Annals of Operations Research, 140, 1, 305-337 (2005) · Zbl 1091.90019
[13] Irnich, S.; Desaulniers, G., Shortest path problems with resource constraints, (Desaulniers, G.; Desrosiers, J.; Solomon, M. M., Column Generation (2005), Springer: Springer New York), 33-65 · Zbl 1130.90315
[14] Jarrah, A. I.Z.; Diamond, J. T., The problem of generating crew bidlines, Interfaces, 27, 4, 49-64 (1997)
[15] Klabjan, D., Large-scale models in the airline industry, (Desaulniers, G.; Desrosiers, J.; Solomon, M. M., Column Generation (2005), Springer: Springer New York, NY), 163-195 · Zbl 1120.90329
[16] Klabjan, D.; Johnson, E.; Nemhauser, G. L., Solving large airline crew scheduling problems: random pairing generation and strong branching, Computational Optimization and Applications, 20, 73-91 (2001) · Zbl 0983.90041
[17] Mercier, A.; Cordeau, J. F.; Soumis, F., A computational study of Benders decomposition for the integrated aircraft routing and crew scheduling problem, Computers and Operations Research, 32, 6, 1451-1476 (2005) · Zbl 1122.90355
[18] Saddoune, M.; Desaulniers, G.; Soumis, F., Aircrew pairing with possible repetitions of the same flight number, Computers and Operations Research (2010)
[19] Saddoune, M., Desaulniers, G., Elhallaoui, I., Soumis, F., 2010b. Integrated airline crew pairing and crew assignment by dynamic constraint aggregation. Technical report G-2010-05. Les Cahiers du GERAD, HEC Montréal, Montréal, Canada.; Saddoune, M., Desaulniers, G., Elhallaoui, I., Soumis, F., 2010b. Integrated airline crew pairing and crew assignment by dynamic constraint aggregation. Technical report G-2010-05. Les Cahiers du GERAD, HEC Montréal, Montréal, Canada. · Zbl 1237.90127
[20] Subramanian, S.; Sherali, H. D., An effective deflected subgradient optimization scheme for implementing column generation for large-scale airline crew scheduling problems, INFORMS Journal on Computing, 20, 4, 565-578 (2008) · Zbl 1243.90125
[21] Vance, P. H.; Barnhart, C.; Johnson, E. L.; Nemhauser, G. L., Airline crew scheduling: a new formulation and decomposition algorithm, Operations Research, 45, 188-200 (1997) · Zbl 0891.90087
[22] Weir, J. D.; Johnson, E. L., A three-Phase approach to solving the bidline problem, Annals of Operations Research, 127, 283-308 (2004) · Zbl 1116.90358
[23] Zeghal, F. M.; Minoux, M., Modeling and solving a crew assignment problem in air transportation, European Journal of Operational Research, 175, 1, 187-209 (2006) · Zbl 1137.90596
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.