A new approach for crew pairing problems by column generation with an application to air transportation

Lavoie, Sylvie; Minoux, Michel; Odier, Edouard

Lavoie, Sylvie; Minoux, Michel; Odier, Edouard (1988), A new approach for crew pairing problems by column generation with an application to air transportation, European Journal of Operational Research, 35, 1, p. 45-58. http://dx.doi.org/10.1016/0377-2217(88)90377-3

Type

Article accepté pour publication ou publié

Date

1988

Journal name

European Journal of Operational Research

Volume

Number

Publisher

Elsevier

Pages

45-58

Abstract (EN)

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 colums, 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.

Subjects / Keywords

Combinatorial optimization; generalized linear programming; scheduling; air transportation