A new approach for crew pairing problems by column generation with an application to air transportation. (English) Zbl 0636.90041

We propose a new approach to crew-pairing problems arising in the context of airline companies. The problem is first formulated as a large scale set covering problem with many columns, each column representing a valid crew-pairing. We then suggest a solution procedure for the continuous relaxation of this large scale problem, based on generalized linear programming, in which the column generation subproblem is shown to be equivalent to a shortest path problem in an associated graph. Computational results obtained on a series of real problems (involving up to 329 flight segments) are reported, confirming both computational efficiency and practical applicability of the new approach. Indeed not only were the resulting solutions observed to be integral for most test problems, but average savings of about 4 to 5 % over the best available hand-built solutions were shown to be obtained.


90B35 Deterministic scheduling theory in operations research
90C90 Applications of mathematical programming
90C27 Combinatorial optimization
90C06 Large-scale problems in mathematical programming
90C35 Programming involving graphs or networks
65K05 Numerical mathematical programming methods
Full Text: DOI


[1] Agard, J.; Arabeyre, J.P.; Vautier, J., Génération automatique de rotations d’équipages, Rairo, 6, 107-117, (1967)
[2] Balas, E.; Ho, A., Set covering algorithms using cutting planes, heuristics and subgradient optimization—A computational study, Mathematical programming study, 12, 37-60, (1980) · Zbl 0435.90074
[3] Balas, E.; Padberg, M.W., Set partitioning—A survey, (), 151-210
[4] Dantzig, G.B., Linear programming and extensions, (1963), Princeton University Press Princeton, NJ · Zbl 0108.33103
[5] Delorme, J., Contribution à la résolution du problème de recouvrement: Méthodes de troncatures, ()
[6] Desrosiers, J.; Soumis, F.; Desrochers, M., Routing with time windows by column generation, Networks, 14, 545-565, (1984) · Zbl 0571.90088
[7] Dijkstra, E.W., A note on two problems in connection with graphs, Numerische Mathematik, 1, 269-271, (1959) · Zbl 0092.16002
[8] Ford, L.R.; D.R. Fulkerson, D.R., Flows in networks, (1962), Princeton University Press Princeton, NJ · Zbl 0106.34802
[9] Gilmore, P.C.; Gomory, R.E., A linear programming approach to the cutting-stock problem, Operations research, 9, 849-869, (1961) · Zbl 0096.35501
[10] Gondran, M.; Minoux, M., Graphes et algorithmes, (1979), Eyrolles Paris · Zbl 0497.05023
[11] Lavoie, S., Mise en oeuvre d’un algorithme de génération de colonnes pour le problème de rotation des équipages, Final report of the crew-pairing project carried out by air France under the supervision of E. odier and M. minoux, (1984)
[12] Minoux, M., Plus courts chemins avec contraintes: algorithmes et applications, Annales des Télécommunications, 30/11, 12, 383-394, (1975)
[13] Minoux, M., (), English Translation: Wiley, New York, 1986
[14] Minoux, M., Column generation techniques in combinatorial optimization, a new application to crew-pairing problems, ()
[15] Niederer, M., Optimization of Swissair’s crew scheduling by heuristic methods using integer linear programming models, ()
[16] Steiger, F., Optimization of Swissair’s crew scheduling by an integer linear programming model, Swissair O.R. SDK, 3.3.911, (1965)
[17] Thiriez, H., Comprendre et utiliser LES modèles en gestion, (1982), Les Éditions d’Organisation
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.